大家好，又见面了，我是你们的朋友全栈君。
一.问题
由于编程语言提供的基本数值数据类型表示的数值范围有限，不能满足较大规模的高精度数值计算，因此需要利用其他方法实现高精度数值的计算，于是产生了大数运算。尤其是乘法运算，下面就是大整数的乘法的过程（加 减法都一样的原理）。
二.解决问题的方法
方法一（传统的相乘逐步相加）
乘法规律，一个数的第i位和另一个数的第j位相乘，一定会累加到结果的第i+j位，结果的数组一个数组元素存2位数，最后对结果整除得到进位，mod得到余数就是i+j位的数字，最后打印出来。
对于大整数比较方便的输入方法是，①按字符型处理，存储在字符串数组s1、s2中，计算结果存储在整型数组ans中。 ②通过字符的ASCII码，数字字符可以直接参与运算，i位数字与j位数字相乘的表达式为：(s1[i]-‘0’)*(s2[j]-‘0’)。 ③每一次数字相乘的结果位数是不固定的，而结果数组中每个元素只存储一位数字，所以用变量t暂存结果，对t mod运算得到的就是ans[i+j]的值，若超过1位数则进位，用变量b存储。
这种做法的时间复杂度为o(n^2)
c语言源码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int max(int a,int b){
return a>b?a:b;
}
int main()
{
char s1[205], s2[205],ans[1000];
int str1[205],str2[205]；
int len1, len2,i;
while( scanf("%s%s", s1, s2)!=EOF){
len1 = strlen(s1), len2 = strlen(s2);
memset(str1,0,205);//初始化0
memset(str2,0,205);
memset(ans,0,1000);
int len = 0;
for(i = 0; i < len1; ++ i)
str1[i] = s1[len1 - 1 - i] - '0';
for(i = 0; i < len2; ++ i)
str2[i] = s2[len2 - 1 - i] - '0';
for( i = 0; i < len1; ++ i)
{
int b = 0; //每遍历完数组a的一个数，进位b都要初始化为0
for(int j = 0; j < len2 || b; ++ j)//当str[j]没遍历完，或者最高位满十需要进位，进位不为0
{
int t = ans[i + j] + str1[i]*str2[j] + b;
ans[i + j] = t%10; //余数就是该ans[i+j]位置的数
b = t/10;//进位
//len = max(len, j + i);
}
len = i+j-1 //最终的位数
}
for( i = len; i >= 0; -- i) //倒置输出
printf("%d", ans[i]);
printf("\n");
}
return 0;
}方法二（分治法）
分治算法解题的一般步骤：
- 分解：将要解决的问题划分为若干个规模较小的同类问题
- 求解：当子问题划分的足够小时，用较简单的方法解决
- 合并：按原问题的要求，将子问题的解逐层合并构成原问题的解
①两个大整数在理想状态下：就是两个大整数的位数相同
现在有两个大整数X,Y; 设X, Y是n位十进制整数，分段表示如下:
即 X=A*10^(n/2)+B, Y=C*10^(n/2)+D 则:
本来可以直接算AD+BC，但是这样效率变低了，所以对AD+BC进行分解优化后得：
计算成本：3次n/2位乘法，6次不超过n位加减法，2次移位，所有加法和移位共计O(n)次运算。由此可得
理想状态下c语言代码：（不超过long long 型，后面做法会用字符串接收大整数）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)
//_int64等同于long long
//%I64d等同于%lld
_int64 mutipy(_int64 a,_int64 b,int num){ //两个long long 类型的大整数相乘，后面会用字符串做法解决
int s=sign(a)*sign(b);
a=(a>0)?a:-a ;
b=(b>0)?b:-b ;
if(num==0) //递归出口，
return 0;
else if(num==1){ //当a,b只有一位数时，直接相乘
return s*a*b;
}
else{
_int64 A=a/(int)pow(10,(int)(num/2)); //分离大整数a的高位
_int64 B=a%(int)pow(10,(int)(num/2)); //分离大整数a的低位
_int64 C=b/(int)pow(10,(int)(num/2)); //分离大整数b的高位
_int64 D=b%(int)pow(10,(int)(num/2)); //分离大整数b的低位
_int64 AC=mutipy(A,C,(int)(num/2)); //分治计算AC
_int64 BD=mutipy(B,D,(int)(num/2)); //分治计算BD
_int64 ABCD=mutipy((A-B),(D-C),(int)(num/2))+AC+BD; //计算(A-B)(D-C)+AC+BD
return s*(_int64)(AC*pow(10,(int)(num/2)+(int)(num/2))+ABCD*pow(10,(int)(num/2))+BD); //返回结果
}
}
int main()
{
_int64 a,b,c,temp; //long long a,b,c;
int len1=0,len2=0;
while(scanf("%I64d %I64d",&a,&b)){
temp=a;
while(temp){ //计算a的位数
len1++;
temp=temp/10;
}
c=mutipy(a,b,len1);
printf("%I64d\n",c);
}
return 0;
}其实上述有个缺陷：那就是只能是long long 类型的大整数相乘，超出了long long 型就会报错。解决方法看下面的做法
②两个大整数在非理想状态下：就是两个大整数的位数不相同
我们还是假设有两个大整数X、Y，它们的位数不相同，现在要求X*Y的乘法，我们采用分治的算法，将X、Y分别拆分为A与B、C与D，如下图:
上式一共需要进行2次xn0的乘法（AC、AD各一次）、2次yn0的乘法（AC、BC各一次）和3次加法，因而该算法的时间复杂度为
跟上面一样，对AD+BC进行分解优化得：
修改后的时间复杂度：
由于T(min(m,n))<T(m)+T(n),所以修改后的算法更好，时间复杂度：T(m+n)=O(nlog3)=O(n1.59)
非理想状态下的c语言代码：（不超过long long 型，后面做法会用字符串接收大整数）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define sign(x) ((x>0)?1:-1)
//_int64等同于long long
//%I64d等同于%lld
_int64 mutipy(_int64 a,int numa,_int64 b,int numb){ //两个long long 类型的大整数相乘，后面会用字符串做法解决
int s=sign(a)*sign(b);
a=(a>0)?a:-a ;
b=(b>0)?b:-b ;
if(numa==0||numb==0) //递归出口，
return 0;
else if((numa==1&&numb==1)||numa==1||numb==1){ //当a,b只有一位数时，直接相乘
return s*a*b;
}
else{
int num1=numa/2; //定义了大整数a的低位的位数x0
int num2=numa-num1; //定义了大整数a的高位的位数x1
int num3=numb/2; //定义了大整数b的低位的位数x2
int num4=numb-num3; //定义了大整数b的高位的位数x3
_int64 A=a/(int)pow(10,num1); //分离大整数a的高位
_int64 B=a%(int)pow(10,num1); //分离大整数a的低位
_int64 C=b/(int)pow(10,num3); //分离大整数b的高位
_int64 D=b%(int)pow(10,num3); //分离大整数b的低位
_int64 AC=mutipy(A,num2,C,num4); //分治计算AC
_int64 BD=mutipy(B,num1,D,num3); //分治计算BD
_int64 ABCD=mutipy(((_int64)(A*pow(10,num1))-B),num2,(D-(_int64)(C*pow(10,num1))),num4); //计算(A*10^num1-B)(D-C*10^num3)
return s*(_int64)(2*AC*pow(10,(num1+num3))+ABCD+2*BD); //返回结果
}
}
int main()
{
_int64 a,b,c,temp; //long long a,b,c;
int len1=0,len2=0;
while(scanf("%I64d %I64d",&a,&b)){
temp=a;
while(temp){ //计算a的位数
len1++;
temp=temp/10;
}
temp=b;
while(temp){ //计算b的位数
len2++;
temp=temp/10;
}
c=mutipy(a,len1,b,len2);
printf("%I64d\n",c);
}
return 0;
}非理想状态下的c语言代码：（任意位数相乘，可以超出longlong类型）
#include<stdio.h>
#include<string.h>
int result[255];
void cal( char a[],int numa,char b[],int numb,int s){
int num1=numa/2; //num1为B的位数，B属于低位的那一部分
int num2=numa-num1; //num2为A的位数，A属于高位的那一部分
int num3=numb/2; //num3为D的位数，D属于低位的那一部分
int num4=numb-num3; //num4为C的位数，C属于高位的那一部分
char A[255],B[255],C[255],D[255];
int k=0;
if(numa==0||numb==0) //当位数为0时
return ;
else if(numa==1&&numb==1){ //分治递归到当数组a和b的位数全为1时
result[s]+=(a[0]-'0')*(b[0]-'0'); //直接计算，把他的结果直接加到对应数组result的位置
return;
}
else{ //当数组a和b的位数至少有一个不为1时
for(int i=0;i<num2;i++) //获取数组a的高位部分A
A[k++]=a[i];
k=0;
for(i=num2;i<numa;i++) //获取数组a的低位部分B
B[k++]=a[i];
k=0;
for(i=0;i<num4;i++) //获取数组b的高位部分C
C[k++]=b[i];
k=0;
for(i=num4;i<numb;i++) //获取数组b的高位部分D
D[k++]=b[i];
cal(A,num2,C,num4,s+num1+num3); //AC ,在result[s+num1+num3]的位置存储AC，也是说偏移s+num1+num3位，s初始化为0
cal(B,num1,C,num4,num3+s); //BC，偏移num3+s位
cal(A,num2,D,num3,num1+s); //AD,偏移num1+s位
cal(B,num1,D,num3,s); //BD，偏移s位
}
}
void exchange(int result[],int len){ //将result数组中的值进行整理，转化输出
int i = 0;
int t,p1,p2;
while(i<=len){ //以特殊数最大位数为终止条件
if(result[i] < 10); //当result[i]的值小于10，就不处理，直接保存在result[i]中
else if(result[i] < 100){ //当0<=result[i]<100时
t = result[i] % 10; //余数就是该位置result[i]的值
p1 = result[i] / 10; //result[i]进位
result[i] = t; //将余数t保存至result[i]中
result[i+1] += p1; //进位把他加到result[i+1]中
}
else{ //当result[i]>=100时
t = result[i] % 10; //余数就是该位置result[i]的值
p1 = result[i] / 10 % 10; //这是result[i]满十进位
p2 = result[i] / 100; //这是result[i+1]满十进位
result[i] = t; //将余数t保存至result[i]中
result[i+1] += p1; //进位把他加到result[i+1]中
result[i+2] += p2; //进位把他加到result[i+2]中
}
i++; //位数加1
}
}
int main(){
char a[100],b[100];
int j,i=0,len1,len2;
while(scanf("%s %s",a,b)!=EOF){
len1=strlen(a);
len2=strlen(b);
cal(a,len1,b,len2,0);
exchange(result,len1+len2);
for(i=len1+len2-1;i>=0;){ //去高位的0去掉
if(result[i]==0){
while(result[i]==0){
i--;
}
}
else
break;
}
for(j=i;j>=0;j--) //从非零的位置打印
printf("%d",result[j]);
printf("\n");
}
return 0;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/136978.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
