大整数相乘
分治思想解决大整数相乘
1.初始化
将a、b倒序存储在数组a.s[]、b.s[]中
a.L 是长度
a.c是阶数
2.分解
将一个n位的数分解成两个n/2位的数并存储，记录它的长度和阶数
ah---高位 al---低位
bh---高位 bl---低位
3.求解子问题
ah*bh ah*bl al*bh al*bl
4.继续求解子问题
继续分解上述结果
5.合并
合并子问题结果，返回给ah*bh
1 // 2 // Created by alim on 2017/12/21. 3 // 4 5 #include <stdlib.h> 6 #include <cstring> 7 #include <iostream> 8 using namespace std; 9 10 #define M 100 11 12 char sa[1000]; 13 char sb[1000]; 14 15 typedef struct _Node{ 16 int s[M];//数字 17 int l;//数字长度 18 int c;//次幂 19 }Node,*pNode; 20 21 /** 22 * 将n分解成两个n/2的数存储，并记录它的次幂 23 * @param src 待分解的数节点 24 * @param des 分解后得到的数字节点 25 * @param st 从src中取数的开始位置 26 * @param l 取数的长度 27 */ 28 void cp(pNode src, pNode des, int st, int l) 29 { 30 int i, j; 31 for(i=st, j=0; i<st+l; i++, j++)//从src节点数组中st位置开始 32 { 33 des->s[j] = src->s[i];//将这些数放入到des中 34 } 35 des->l = l;//长度等于取数的长度 36 des->c = st + src->c; //des次幂等于从开始位置加上src次幂 37 38 } 39 40 /** 41 * 合并函数 42 * 分治法 大数乘法 43 X = A*10^n + B 44 Y = C*10^m + D 45 X*Y = A*C*10^(n+m) + A*D*10^n + B*C*10^m + B*D 46 * @param pa 47 * @param pb 48 * @param ans 49 */ 50 void add(pNode pa, pNode pb, pNode ans) 51 { 52 int i,cc,k,palen,pblen,len; 53 int ta, tb;//分别记录a，b相加时对应位上的数 54 pNode temp; 55 if((pa->c<pb->c)) //保证Pa的次幂大 56 { 57 temp = pa; 58 pa = pb; 59 pb = temp; 60 } 61 ans->c = pb->c;//结果的次幂为较小的一个的次幂 62 cc = 0;//初始化进位为0 63 palen=pa->l + pa->c;//a数加上次幂的总长度 64 pblen=pb->l + pb->c; 65 if(palen>pblen) 66 len=palen;//取a b 总长度的最大值 67 else 68 len=pblen; 69 k=pa->c - pb->c;//k为左侧补0的个数 70 for(i=0; i<len-ans->c; i++) //结果的长度最长为pa，pb之中的最大长度减去最低次幂 71 { 72 if(i<k) 73 ta = 0; 74 else 75 ta = pa->s[i-k];//次幂高的补0，大于低的长度后与0进行计算 76 if(i<pb->l) 77 tb = pb->s[i]; 78 else 79 tb = 0; 80 if(i>=pa->l+k) 81 ta = 0; 82 ans->s[i] = (ta + tb + cc)%10; 83 cc = (ta + tb + cc)/10; 84 } 85 if(cc) 86 ans->s[i++] = cc; 87 ans->l = i; 88 } 89 90 void mul(pNode pa, pNode pb, pNode ans) 91 { 92 int i, cc, w; 93 int ma = pa->l>>1, mb = pb->l>>1; //长度除2 94 Node ah, al, bh, bl; 95 Node t1, t2, t3, t4, z; 96 pNode temp; 97 98 if(!ma || !mb) //如果其中个数为1 99 { 100 if(!ma) //如果a串的长度为1，pa,pb交换，pa的长度大于等于pb的长度 101 { 102 temp = pa; 103 pa = pb; 104 pb = temp; 105 } 106 ans->c = pa->c + pb->c; 107 w = pb->s[0]; 108 cc = 0; //此时的进位为c 109 for(i=0; i < pa->l; i++) 110 { 111 ans->s[i] = (w*pa->s[i] + cc)%10; 112 cc= (w*pa->s[i] + cc)/10; 113 } 114 if(cc) 115 ans->s[i++] = cc; //如果到最后还有进位，则存入结果 116 ans->l = i; //记录结果的长度 117 return; 118 } 119 //分治的核心 120 cp(pa, &ah, ma, pa->l-ma); //先分成4部分al,ah,bl,bh 121 cp(pa, &al, 0, ma); 122 cp(pb, &bh, mb, pb->l-mb); 123 cp(pb, &bl, 0, mb); 124 125 mul(&ah, &bh, &t1); //分成4部分相乘 126 mul(&ah, &bl, &t2); 127 mul(&al, &bh, &t3); 128 mul(&al, &bl, &t4); 129 130 add(&t3, &t4, ans); 131 add(&t2, ans, &z); 132 add(&t1, &z, ans); 133 } 134 int main() { 135 Node ans,a,b; 136 cout << "请输入大整数 a："<<endl; 137 cin >> sa; 138 cout << "请输入大整数 b：" << endl; 139 cin >> sb; 140 a.l = strlen(sa);//以字符串进行处理，计算长度 141 b.l = strlen(sb); 142 143 //倒向存储 144 int z=0,i; 145 for (int i = a.l-1; i >= 0; i--) { 146 a.s[z++] = sa[i]-'0'; 147 } 148 a.c=0; 149 150 z=0; 151 for (int i = b.l-1; i >= 0; i--) { 152 b.s[z++] = sb[i] - '0'; 153 } 154 b.c = 0; 155 mul(&a, &b, &ans); 156 cout << "最终结果为："; 157 for (i = ans.l-1; i >= 0; i--) { 158 cout<<ans.s[i]; 159 } 160 cout << endl; 161 return 0; 162 }