加载中…大整数乘法-分治法
(2015-10-26 12:46:10)
标签：
佛学股票军事教育 |
一、两个整数相乘，需要考虑计算的容量，把大整数划分为多个部分（通常两个部分），则问题规模变小，存储容量变小。
先介绍123456*789问题，按照数学常规思考问题，可以写成下列表格形式：
表一
http://s2/mw690/001wc72cgy6Wv7jQcCde1&690
表二：
http://s6/mw690/001wc72cgy6Wv7JSAU525&690
表三
http://s8/mw690/001wc72cgy6Wv83sUPt67&690
由表三得到：
1.m位整数*n位整数乘积m+n-1位，也可能进位乘积为m+n位
2.进位是表中最后一列和除以进制得到的商，保留位为表中和除以进制得到的余数
3.因为要取得每一位相乘，故采用字符数组存放整数，可以定义三个字符数组分别存储乘数、被乘数、乘积。
算法代码
void f（char *a,char
*b,char * &c）{
int carry=0;//定义进位
for（int i=0;a[i]!='\0';i++）{
a[i]-='0';
}
for（int i=0;b[i]!='\0';i++）{
b[i]-='0';
}
//计算乘积，乘积个位算起
for(int k=i+j;k>0;k--){
sum=carry;
//乘数*被乘数首先是乘数个位乘被乘数高位
for(j=0;str[j]!='\0';j++){
sum+=a[i-j][j];
c[i+1]=sum+'0';
carry=sum/10;
}
if((c[0]=carry+'0')=='0'){
c[0]='\040';//设置为空格
}}
}
效率分析：需要进行m*n次乘法运算，接着在进行m+n次加法即m+n次的取摸运算。
二、接下来改进算法
我们可以将大整数对拆为两个部分。
即a和b相乘就可以写为：a * b = { a1 *
10^(n1/2) +
a0 }
* { b1 *
10^(n2/2) + b0 }
展开后整理得： a * b
= a1*b1 * 10^[ (n1+n2)/2
] + a1*b0 *
10^(n1/2)
+ a0*b1 *
10^(n2/2) + a0*b0 ；
这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解
实现方法：我们定义一个支持方法f(char *a,char *b)，用于在结束递归时（在本例中，我定义有一个数是1位时结束递归，直接用普通乘法）计算两个字符串的乘积（为了表示大数，用字符串来接受参数）。有 了这个支持方法，分治递归实现两个大数乘法的实现如下：
表一
表二：
http://s6/mw690/001wc72cgy6Wv7JSAU525&690
表三
http://s8/mw690/001wc72cgy6Wv83sUPt67&690
由表三得到：
1.m位整数*n位整数乘积m+n-1位，也可能进位乘积为m+n位
2.进位是表中最后一列和除以进制得到的商，保留位为表中和除以进制得到的余数
3.因为要取得每一位相乘，故采用字符数组存放整数，可以定义三个字符数组分别存储乘数、被乘数、乘积。
算法代码
void
int carry=0;//定义进位
for（int i=0;a[i]!='\0';i++）{
a[i]-='0';
}
for（int i=0;b[i]!='\0';i++）{
b[i]-='0';
}
//计算乘积，乘积个位算起
for(int k=i+j;k>0;k--){
carry=sum/10;
}
c[0]='\040';//设置为空格
}}
}
效率分析：需要进行m*n次乘法运算，接着在进行m+n次加法即m+n次的取摸运算。
二、接下来改进算法
我们可以将大整数对拆为两个部分。
即a和b相乘就可以写为：a * b = {
展开后整理得： a
这样就很容易递归的来求a * b，如果你嫌分解后的数还太大，就可以继续分解
实现方法：我们定义一个支持方法f(char *a,char *b)，用于在结束递归时（在本例中，我定义有一个数是1位时结束递归，直接用普通乘法）计算两个字符串的乘积（为了表示大数，用字符串来接受参数）。有 了这个支持方法，分治递归实现两个大数乘法的实现如下：
int f(char *a,char *b)//用字符串读入2个大整数
{
long result = 0;
if(len(a) == 1 || len == 1) //递归结束的条件
result = f(a,b);
else //如果2个字符串的长度都 >= 2
{
char *a1 =a;
*(a1+(len(a)/2))='\0'; //截取前一半的字符串(较短的一半)
char *a0 = a+len(a)/2; //截取后一半的字符串
*(a0+len(a)/2)='\0';
char *b1=b;
*(b1+(len(a)/2))='\0'; //截取前一半的字符串(较短的一半)
char *b0 = a+len(a)/2; //截取后一半的字符串
*(b0+len(b)/2)='\0';
//分治的思想将整数写成这样： a = a1 * 10^(n1/2) + a0, b = b1 * 10^(n2/2)，相乘展开得到以下四项
//其中n1，n2为2个整数a，b的位数
result = (f(a1,b1) * pow(10,len( a0) + len(b0))
+ f(a1,b0) * pow(10, len(a0) +f(a0,b1) * pow(10,len(b0))
+ fy(a0,b0));
}
return result;
}
{
long result = 0;
if(len(a) == 1 || len == 1) //递归结束的条件
result = f(a,b);
else //如果2个字符串的长度都 >= 2
{
*(a1+(len(a)/2))='\0'; //截取前一半的字符串(较短的一半)
char *b1=b;
*(b1+(len(a)/2))='\0'; //截取前一半的字符串(较短的一半)
//分治的思想将整数写成这样： a = a1 * 10^(n1/2) + a0, b = b1 * 10^(n2/2)，相乘展开得到以下四项
//其中n1，n2为2个整数a，b的位数
result = (f(a1,b1) * pow(10,len( a0) + len(b0))
+ f(a1,b0) * pow(10, len(a0) +f(a0,b1) * pow(10,len(b0))
+ fy(a0,b0));
}
return result;
}
喜欢
0
赠金笔
前一篇：递归编程的思考问题方法
后一篇：棋盘覆盖问题