大数问题是指操作数超过了计算机常用数据类型的存储范围,常常是用字符串来模仿整数相加和相乘运算来实现的,在模拟的过程中要注意考虑进位和边界条件。
1、大整数相加
先看一下加法的计算过程,如456+56789
456
56789
---------
57245
计算过程是从低位往高位开始计算,计算过程要加上进位,如,计算到5+8的时候要加上前面的进位1,得到14,然后14对10取余作为对应结果的第2位,进位为14对10取正,这样一直计算,直到有一个字符串结束,然后考虑进位和没计算完的另一个字符串相加。
边界条件:
两个大整数相加,结果的长度可能与两个数中长度较大的一个相等,也可能比其大1(进位造成),如123+12=135,123长度为3,12长度为2,结果长度为3,再如99+1=100,结果长度为3比99的长度还大1。
考虑到这样的边界条件,在申请内存的时候需要对结果至少申请长度较大的那个还要大1。
代码如下:
#include<iostream>
#include<string>
using namespace std;
//字符串倒置
void reverse(char *str)
{
int len=strlen(str);
for(int i=0;i<len/2;i++)
{
char temp=str[i];
str[i]=str[len-i-1];
str[len-i-1]=temp;
}
}
//大数求和
void bignumsum(char * ope1,char * ope2,char * result)
{
reverse(ope1);
reverse(ope2);
int len1=strlen(ope1);
int len2=strlen(ope2);
int max=len1;
if(max<len2)
{
max=len2;
}
memset(result,'0',max+1);
result[max+1]='\0';
int acc=0;
int i=0;
while(i<len1 && i<len2)
{
int temp=ope1[i]-'0'+ope2[i]-'0'+acc;
acc=temp/10;
result[i]=temp%10+'0';
i++;
}
if(i<len1)
{
while(i<len1)
{
int temp=ope1[i]-'0'+acc;
acc=temp/10;
result[i]=temp%10+'0';
i++;
}
}
if(i<len2)
{
while(i<len2)
{
int temp=ope2[i]-'0'+acc;
acc=temp/10;
result[i]=temp%10+'0';
i++;
}
}
//考虑到进位,所以result的长度有可能比ope1和ope2中最大的数据长度还多出一位
if(acc)
{
result[i]=acc+'0';
}
else
{
result[i]='\0';
}
reverse(result);
}
int main()
{
char num1[4]="456";
char num2[5]="5678";
char num3[6];
bignumsum(num1,num2,num3);
cout<<num3<<endl;
char num4[4]="456";
char num5[5]="678";
char num6[6];
bignumsum(num4,num5,num6);
cout<<num6<<endl;
char num7[4]="111";
char num8[5]="2";
char num9[6];
bignumsum(num7,num8,num9);
cout<<num9<<endl;
return 0;
}
2、大整数相乘
乘法相对于加法稍微复杂一点,需要同时考虑乘法进位和加法进位,还要注意一下计算过程和结果中的对应关系。
如计算123*45
123
45
------
615
492
-------
5535
计算过程是从低位往高位计算,第2个操作数中每一位都与第一个操作数中的所有的位计算一次,而每这样计算一次都进行一次结果的更新,结果先被初始化成全0。而计算过程和结果的规律是,每次计算的时候影响的结果位数是两个操作数位数的和,如上述例子中1是123中的第2位(从低位算起,个位按0位来算),4是45中的第1位,那么这两个数的计算过程将会产生影响的是结果中的第3位,计算过程是1*4+0(上一次乘法的进位)=4,4%10=4,这样就确定了492位置上的那个4,然后再利用加法进位和上一轮的结果来更新结果,结果为0(原来结果对应该位的值)+4(此轮乘法计算之后该位置上对应的值)+1(上一轮加法的进位值)=5
边界条件:
两个大整数相乘结果的长度最大为两个操作数长度之和,所以申请内存的时候要注意至少申请两个操作数长度之和的内存。
代码如下:
#include<iostream>
#include<string>
using namespace std;
void reverse(char *str)
{
int len=strlen(str);
for(int i=0;i<len/2;i++)
{
char temp=str[i];
str[i]=str[len-i-1];
str[len-i-1]=temp;
}
}
void bignummultiply(char *ope1,char *ope2,char *result)
{
reverse(ope1);
reverse(ope2);
int len1=strlen(ope1);
int len2=strlen(ope2);
memset(result,'0',len1+len2);//因为len1和len2两个长度的整数相乘结果最大为len1+len2
result[len1+len2]='\0';
int acc=0;//加法进位
int mcc=0;//乘法进位
for(int i=0;i<len2;i++)
{
acc=0;
mcc=0;
for(int j=0;j<len1;j++)
{
int temp1=(ope1[j]-'0')*(ope2[i]-'0')+mcc;
mcc=temp1/10;
temp1=temp1%10;
int temp2=result[i+j]-'0'+temp1+acc;
acc=temp2/10;
result[i+j]=temp2%10+'0';
}
result[i+len1]=acc+mcc+'0';
}
//这里有一个去除后面0的程序,如78900\0将变成789\0,这样倒过来之后就会使987,而不是00987
int k=len1+len2-1;
while('0'==result[k] && k>=0)
{
result[k--]='\0';
}
//最后经result倒置回来得到最终结果
reverse(result);
}
int main()
{
char n1[5]="12";
char n2[5]="2";
char n3[10];
bignummultiply(n1,n2,n3);
cout<<n3<<endl;
char n4[5]="9";
char n5[5]="9";
char n6[10];
bignummultiply(n4,n5,n6);
cout<<n6<<endl;
char n7[5]="888";
char n8[5]="66";
char n9[10];
bignummultiply(n7,n8,n9);
cout<<n9<<endl;
return 0;
}
以上加法和乘法的计算过程都先使用reverse将字符串倒置,然后再将结果倒置回来计算的,这样是为了更直观的计算,但是,这样会使程序运行效率稍低。实际可以不用倒置,而靠逻辑去写。