/************************分治法求大数乘,这种方法是比较好的,听说还有快的算法,我一定可以找到的 思路 : 123 * 456 分治如下 第一次拆分: 12 45 (拆分方法 设 char *a = "123" ,*b = "456" 对 a: t = strlen(a) t/2 得 12(0,1位置) 余者 3(2位置)为 3 6 ( 另一部分,对 b 亦同,即拆分为 45 6,如左) 递归求: 12 * 45 ( 求得 12 * 45 的解果左移两位补0右边,因为其实是 120 * 450 ) 12 * 6 ( 同上左移一位其实是120 * 6 ) 3 * 45 ( 3 * 450 ) 3 * 6 ( 3 * 6 解果不移动 ) 第二次拆分(12 * 45 ) ( 如下 ) 1 4 ( 交叉相乘并将结果相加 1 * 4 左移两位 400 ,1 * 5 左移一位 50 ,2 * 4 左移一位 80 ,2 * 5 不移为 10) 2 5 ( 相加得400 + 50 + 80 + 10 = 540 ) 另外几个不需要拆分 得 72 , 135 , 18 所以: 54000 + 720 + 1350 + 18 = 56088 难点是对分治的理解,以及结果的调整,对结果的合并. 编译环境: VC ++ 6.0 Author : 江南孤峰 Time : 2006--10--26 *************************/ #include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h> char *result = '\0';int pr = 1; void getFill(char *a,char *b,int ia,int ja,int ib,int jb,int tbool,int move){ int r,m,n,s,j,t; char *stack; m = a[ia] - 48; if( tbool ){// 直接从结果数组的标志位填入,这里用了堆栈思想 r = (jb - ib > ja - ia) ? (jb - ib) : (ja - ia); stack = (char *)malloc(r + 4); for(r = j = 0,s = jb; s >= ib; r ++,s --){ n = b[s] - 48; stack[r] = (m * n + j) % 10; j = (m * n + j) / 10; } if( j ){ stack[r] = j; r ++; } for(r --; r >= 0; r --,pr ++) result[pr] = stack[r]; free(stack); for(move = move + pr; pr < move; pr ++) result[pr] = '\0'; } else{ //与结果的某几位相加,这里不改变标志位 pr 的值 r = pr - move - 1; for(s = jb,j = 0; s >= ib; r --,s --){ n = b[s] - 48; t = m * n + j + result[r]; result[r] = t % 10; j = t / 10; } for( ; j ; r -- ){ t = j + result[r]; result[r] = t % 10; j = t / 10; } } } int get(char *a,char *b,int ia,int ja,int ib,int jb,int t,int move){ int m,n,s,j; if(ia == ja){ getFill(a,b,ia,ja,ib,jb,t,move); return 1; } else if(ib == jb){ getFill(b,a,ib,jb,ia,ja,t,move); return 1; } else{ m = (ja + ia) / 2; n = (jb + ib) / 2; s = ja - m; j = jb - n; get(a,b,ia,m,ib,n,t,s + j + move); get(a,b,ia,m,n + 1,jb,0,s + move); get(a,b,m + 1,ja,ib,n,0,j + move); get(a,b,m + 1,ja,n + 1,jb,0,0 + move); } return 0;} int main(){ char *a,*b; int n,flag; a = (char *)malloc(1000); b = (char *)malloc(1000); printf("The program will computer a*b\n"); printf("Enter a b:"); scanf("%s %s",a,b); result = (char *)malloc(strlen(a) + strlen(b) + 2); flag = pr = 1; result[0] = '\0'; if(a[0] == '-' && b[0] == '-') get(a,b,1,strlen(a)-1,1,strlen(b)-1,1,0); if(a[0] == '-' && b[0] != '-'){ flag = 0; get(a,b,1,strlen(a)-1,0,strlen(b)-1,1,0); } if(a[0] != '-' && b[0] == '-'){ flag = 0; get(a,b,0,strlen(a)-1,1,strlen(b)-1,1,0); } if(a[0] != '-' && b[0] != '-') get(a,b,0,strlen(a)-1,0,strlen(b)-1,1,0); if(!flag) printf("-"); if( result[0] ) printf("%d",result[0]); for(n = 1; n < pr ; n ++) printf("%d",result[n]); printf("\n"); free(a); free(b); free(result); system("pause"); return 0;} /**************对 get() 函数参数的解释：计算：123*435:int get(char *a,char *b,int ia,int ja,int ib,int jb,int t,int move); a: 存储数 m的字符数组(123)b: 存储数 n的字符数组(435)(ia,ja)： 决定当前分治的数，最开始为(0,strlen(a)-1),即123(ib,jb)： 决定当前分治的数，最开始为(0,strlen(b)-1),即435t: 标志值，1，0代表不同的填充方式，举例： 123 * 435 ，拆分顺序如下： 12 * 43 get(a,b,0,1,0,1,1,2); （t 为1，表示本次结果直接填入） 12 * 5 get(a,b,0,1,,2,2,0,1); 3 * 43 get(a,b,2,2,0,1,0,1); 3 * 5 get(a,b,2,2,2,2,0,0); .... move: 结果的移动值如： 12*43 的最后结果为516，实际是120*430 所以左移2位即将 51600填入 result 求 123*435 的简要顺序： 12*43 = 516 左移两位得 51600 直接填入: result = "51600" 12*5 = 60 左移一位得 600 间接填入: result = "52200" 3*43 = 129 左移一位得 1290 间接填入: result = "53490" 3*5 = 15 不需要移动，将15 间接填入: result = "53505" 所以123*435 = 53505****************/
评论