高精度计算(加减乘)

高精度计算C/C++中的int类型能表示的范围一般是-231－231–1。unsigned类型能表示的范围是0－232–1，即0－4294967295。所以，int和unsigned类型变量，都不能保存超过10位的整数。我们如何进行大整数的运算？比如如何计算两个100位整数的和？如果有一个长度为100位的大整数，我们如何存储？1大整数加法几个需要考虑的问题：1、如何存储大整数？数组2、如何实现加法？逐位相加3、如何处理进位？向数组的高位进位31022638667678369054+107710512128111008706239111a0a1a2a3a4a5a6a7a8a9a10参考程序：#include<iostream>#include<string>usingnamespacestd;strings1,s2;inta[100],b[100],c[100],jw;intmain(){ cin>>s1; cin>>s2; //把s1的长度，放入到a[0]; a[0]=s1.size(); //把个位放入a[1]，把十位放入a[2],把百位放入a[3] for(inti=a[0]-1;i>=0;i--){ intj=a[0]-i; a[j]=s1[i]-’0’; } //把s2的长度，放入到b[0]; b[0]=s2.size(); //把个位放入b[1]，把十位放入b[2],把百位放入b[3] for(inti=b[0]-1;i>=0;i--){ intj=b[0]-i; b[j]=s2[i]-’0’; }//在c[0]放入，a[0]和b[0]的最大值，和的最少位数 if(a[0]>b[0]) c[0]=a[0]; else c[0]=b[0]; //按位加法 for(inti=1;i<=c[0];i++){ c[i]=(a[i]+b[i]+jw)%10; jw=(a[i]+b[i]+jw)/10; } if(jw>0){ c[0]++; c[c[0]]=jw; } //输出答案 for(inti=c[0];i>=1;i--) { cout<<c[i]; }return0;}2大整数减法#include<iostream>#include<string>usingnamespacestd;strings1,s2,t;inta[100],b[100],c[100];boolflag;intmain(){ cin>>s1;cin>>s2; //预处理 if(s2.size()>s1.size())flag=true; if(s2.size()==s1.size()&&s2>s1)flag=true; if(flag==true){ cout<<‘-’; t=s1; s1=s2; s2=t; } //逆序存入数组 a[0]=s1.size(); for(inti=a[0]-1;i>=0;i--){ intj=a[0]-I; a[j]=s1[i]-’0’; } b[0]=s2.size(); for(inti=b[0]-1;i>=0;i--){ intj=b[0]-I; b[j]=s2[i]-’0’; } //按位减法 c[0]=a[0]; for(inti=1;i<=c[0];i++){ if(a[i]-b[i]<0){ //借位 a[i+1]--; c[i]=10+a[i]-b[i]; } else c[i]=a[i]-b[i]; } //除去多余的0 for(inti=c[0];i>=1;i--){ if(c[i]>0)break; else c[0]--; } if(c[0]==0) c[0]=1;//答案为0 //输出答案 for(inti=c[0];i>=1;i--) cout<<c[i]; return0;}3高精度乘以低精度a[3]a[2]/b[2]a[1]/b[1]a[i]345b×23————————————a[i]×bc[3]c[2]c[1]6992115691035————————————————79353高精度乘以低精度#include<iostream>#include<cstdio>usingnamespacestd;strings1;inta[100],b,c[100];intmain(){ cin>>s1; cin>>b; a[0]=s1.size(); //把个位放入a[1]，把十位放入a[2],把百位放入a[3] for(inti=a[0]-1;i>=0;i--){ intj=a[0]-i; a[j]=s1[i]-’0’; } //被除数位数为最终位数

c[0]=a[0]; //按位计算 for(inti=1;i<=c[0];i++) c[i]=a[i]*b;

//处理进位

，最高位不处理 for(inti=1;i<c[0];i++) if(c[i]>=10) { c[i+1]+=c[i]/10; c[i]=c[i]%10; } //输出 for(inti=c[0];i>=1;i--) { cout<<c[i]; } return0;}4、高精度乘高精度类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进行乘法运算时，必须进行错位相加分析c数组下标的变化规律，可以写出如下关系式：Ci=C'i+C"i+……，其中：C'i由A1*B1、A2*B1、A3*B1、……组成C"i由A1*B2、A2*B2、A3*B2、……组成……我们在计算高精度乘法结果时，通常先计算C'i，再加上C"i,再加上C'"i,……Ci跟a[i]*b[j]乘积有关，跟上次的进位有关，还跟原Ci的值有关，分析下标规律，有：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;A3A2A1×B2B1C'4C'3C'2C'1C"5C"4C"3C"2

C6C5C4C3C2C1

856×

2542801712

21400高精度乘高精度856×

2542801712

21400C[5]C[4]C[3]C[2]C[1]856×25

0+0+6×5856×25

0+3+5×50856×25

0+2+8×580a×b[1]4280856×25

428+0+6×20856×25

42+2+5×200856×25

4+1+8×2400a×b[2]21400a[i]×b[j]对应于c[i+j-1]#include<iostream>#include<cstdio>#include<string>usingnamespacestd;strings1,s2;inta[100],b[100],c[100],jw;intmain(){ cin>>s1>>s2; //a[0]里存入长度，每一