算法设计与分析（第四周）大整数相乘 分治法【不能解决溢出问题】

思路

二进制

分成两半，先算左边，再算右边

结果：

2344344 110101

直接相乘：258114618744

优化算法：258114618744

请按任意键继续. . .

代码

同理写了一个十进制算法，如下：

代码只是模拟，不是实际运算过程

此算法不能解决溢出问题，只能降低时间复杂度

没有解决奇数位数问题

#include<iostream>#include<math.h>#define DIGIT 6//两个DIGIT位十进制大整数乘法运算using namespace std;int main(){long long int num1;long long int num2;cin >> num1 >> num2;long long int num1Left, num1Right;long long int num2Left, num2Right;num1Left = num1 / pow(10, DIGIT / 2);//Anum1Right = num1 - num1Left * pow(10, DIGIT / 2);//Bnum2Left = num2 / pow(10, DIGIT / 2);//Cnum2Right = num2 - num2Left * pow(10, DIGIT / 2);//Dlong long int res;//XY = AC 2n + ((A - B)(D - C) + AC + BD) 2n / 2 + BDlong long int AC = num1Left * num2Left;long long int BD = num1Right * num2Right;res = AC * pow(10, DIGIT) + ((num1Left - num1Right)*(num2Right - num2Left) + AC + BD)*pow(10, DIGIT / 2) + BD;cout << "直接相乘：" << num1 * num2 << endl;cout << "优化算法：" << res << endl;system("pause");}