思路

二進(jìn)制
分成兩半，先算左邊，再算右邊

結(jié)果：

2344344 110101
直接相乘：258114618744
優(yōu)化算法：258114618744
請(qǐng)按任意鍵繼續(xù). . .

代碼

同理寫了一個(gè)十進(jìn)制算法，如下：

代碼只是模擬，不是實(shí)際運(yùn)算過(guò)程
此算法不能解決溢出問(wèn)題，只能降低時(shí)間復(fù)雜度

沒(méi)有解決奇數(shù)位數(shù)問(wèn)題

#include<iostream> #include<math.h> #define DIGIT 6//兩個(gè)DIGIT位十進(jìn)制大整數(shù)乘法運(yùn)算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 << "優(yōu)化算法：" << res << endl;system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析（第四周）大整数相乘 分治法【不能解决溢出问题】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。