前言：

A,B兩個(gè)大數(shù)，都為n位，要計(jì)算A*B，需要將A和B劃分成兩等份，如下圖所示

普通的做法是A*B=a1*b1*10^n+(a1*b0+b1*a0）*10^(2/n)+a0*b0

舉個(gè)例子：

1234*9876=（12*98）*10000+（12*76+98*34）*100+34*76

對(duì)于這個(gè)算法的時(shí)間復(fù)雜度，我們需要做4次n/2級(jí)別的乘法和3加法。即T(n)=4*T(n/2)+O(n),時(shí)間復(fù)雜度是O(n2）.

分治法的算法是A*B=a1*b1*10^n+[(a1+a0)*(b0+b1)-a1*a0-b1*b0]*10^n/2+a0*b0

對(duì)于這個(gè)算法的時(shí)間復(fù)雜度，我們需要做3次n/2級(jí)別的乘法。即T(n)=3*T(n/2)+O(n),時(shí)間復(fù)雜度是T(n) = O(n^log2(3) ) = O(n^1.59 ).

下面上代碼：

#include<iostream> #include<string> #include<algorithm> #include<sstream> using namespace std; //string轉(zhuǎn)換為int int strint(string s) {int num;stringstream ss(s);ss >> num;return num; } //int轉(zhuǎn)換為string string intstr(int num) {string s;stringstream ss;ss << num;ss >> s;return s; } //前置0 ，因?yàn)榇髷?shù)的長(zhǎng)度必須要為2^n的倍數(shù)，才能劃分 void removePrezero(string &s) {if (s.length() == 1)return;int k = 0;for (int i = 0; i < s.length(); i++) {if (s[i] == '0')k++;else break;}if (k == s.length())s = "0";else s = s.substr(k); } //大數(shù)相加 string add(string s1, string s2) {string s = "";removePrezero(s1); //去掉前置0removePrezero(s2);reverse(s1.begin(), s1.end()); //先把字符串顛倒，方便相加reverse(s2.begin(), s2.end());int c = 0;for (int i = 0;c|| i < max(s1.length(), s2.length()); i++) {int t = c;if (i < s1.length())t += s1[i] - '0';if (i < s2.length())t += s2[i] - '0';int d = t % 10;s.insert(0, intstr(d)); c = t / 10;}return s; } //大數(shù)相減 string subtra(string &s1, string &s2) {string s = "";string flag;removePrezero(s1); //去掉前置0removePrezero(s2);int len1 = s1.length();int len2 = s2.length();int len = len1>len2 ? len1 : len2; if (len1 < len2)flag = "-";else if (len1 > len2)flag = "+";else {int i;for (i = 0; i < len1; i++) {if (s1.at(i) > s2.at(i)) {flag = "+"; break;}else if (s1.at(i) < s2.at(i)) {flag = "-"; break;}}if (i == len1)s == "0";}int* num = (int*)malloc(sizeof(int)*len);reverse(s1.begin(), s1.end()); //方便相減reverse(s2.begin(), s2.end());int c = 0;for (int j = 0; j < len; j++) {int n1 = j < len1 ? s1[j] - '0' : 0;int n2 = j < len2 ? s2[j] - '0' : 0;if (flag == "+")num[c++] = n1 - n2;else num[c++] = n2 - n1;}for (int j = 0; j < c; j++) {if (num[j] < 0) {num[j] += 10; num[j + 1] -= 1;}}c--;while (num[c] == 0)c--;for (int j = 0; j <=c; j++){s.insert(0, intstr(num[j]));}if (flag == "-")return flag + s;else return s; } //增加前置0 void addPrezero(string &s, int L) {for (int i = 0; i < L; i++)s = s.insert(0, "0"); } //增加后置0，大數(shù)*10^n 相當(dāng)于在數(shù)的后面加n個(gè)0 string addLastzero(string s, int L) {string s1 = s;for (int i = 0; i < L; i++)s1 += "0";return s1; } //大數(shù)相乘 string multi(string &s1, string &s2) {bool flag1 = false, flag2 = false; string sign; //作用是判斷結(jié)果是正數(shù)還是負(fù)數(shù)if (s1.at(0) == '-') {flag1 = true; s1 = s1.substr(1);}if (s1.at(0) == '-') {flag2 = true; s2 = s2.substr(1);}if (flag1&&flag2)sign = "+";else if (flag1 || flag2) sign = "-";else sign = "+";int L = 4; //將數(shù)前置若干個(gè)0，使其長(zhǎng)度為2^n的倍數(shù)if (s1.length() > 2 || s2.length() > 2) {if (s1.length() >= s2.length()) {while (L < s1.length())L *= 2;if (L != s1.length()) addPrezero(s1, L - s1.length());addPrezero(s2, L - s2.length()); }else {while (L < s2.length())L*=2;if (L != s2.length())addPrezero(s2, L - s2.length());addPrezero(s1, L - s1.length());}}if (s1.length() == 1)addPrezero(s1, 1);if (s2.length() == 1)addPrezero(s2, 1);int n = s1.length();string result, a0, a1, b0, b1;if (n > 1) {a1 = s1.substr(0, n / 2);a0 = s1.substr(n / 2, n);b1 = s2.substr(0, n / 2);b0 = s2.substr(n / 2, n);}if (n == 2) {int x1 = strint(a1);int x2 = strint(a0);int y1 = strint(b1);int y2 = strint(b0);int num = (x1 * 10 + x2)*(y1 * 10 + y2);result = intstr(num);}else {string c2 = multi(a1, b1);string c0 = multi(a0, b0);string temp1 = add(a0, a1);string temp2 = add(b1, b0);string temp3 = add(c2, c0);string temp_c1 = multi(temp1, temp2);string c1 = subtra(temp_c1, temp3);string s1 = addLastzero(c1, n / 2);string s2 =addLastzero(c2, n);result = add(add(s1, s2), c0);}if (sign == "-")result.insert(0, sign);return result; } int main() {//textstring s1 = "-1234999999999999999999999", s2 = "12348976543";cout << multi(s1, s2); }

總結(jié)：算法本身不難，主要是程序有太多需要注意的細(xì)節(jié)。對(duì)代碼有疑問(wèn)或者有些部分不理解的朋友，歡迎留言。

對(duì)了，程序的主要思想?yún)⒖加邳c(diǎn)擊打開(kāi)鏈接，強(qiáng)烈建議大家可以去看一下。

總結(jié)

以上是生活随笔為你收集整理的大数相乘（分治法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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