/************************
分治法求大数乘,这种方法是比较好的,听说还有快的算法,我一定可以找到的
思路 : 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),即435
t: 标志值，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
****************/
评论