高精度算法解析

高精度运算High-precisionAlgorithm基本整数类型的取值范围类型数值范围占字节数unsignedchar0..2551char-128..1271int(long)-2147483648..21474836471094unsignedint(long)0..42949672954longlong-9223372036854775808..922337203685477580710188unsigned0..184467440737095516158Longlong使用时有限制，例如，不能作为数组的下标等。为什么需要高精度运算•当要处理的数据超过了任何一种数据类型所能容纳的范围,这种数称为高精度数,必须自定义类型来存储.同时还要自行编写高精度数的运算函数(加\减\乘\除等)高精度数的输入和存储•在运算对象的数值范围为任何数据类型所无法容纳的情况下,采用数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）来表示一个数,就称为高精度数。1、采用字符串形式输入，并将其转化为整数数组。2、用一个整型变量记录数据的实际长度（即数组的元素个数）字符串到整数数组的转换•字符串存储时,数的高位被存放在字符串的低位。76321801234567转换成整数数组时，要把高精度数的低位“还原”到数组的低位。这样才便于后续计算。a[1]存放最低位，a[6]存放最高位。高精度数的位数可存放在a[0]中。也可以另用一个变量存放。字符串s681236701234567整型aconstintMAXLEN=241;//最大长度为240位typedefinthp[MAXLEN];//定义hp为高精度类型voidStr2hp(strings,hp&a)//s转换后存入a{inti,len;memset(a,0,sizeof(a));//clearalen=s.size();a[0]=len;//savethelengthfor(i=0;ilen;i++)//converta[len-i]=s[i]-'0';}高精度数类型定义与读入输出voidPrint(hpa){inti,len;len=a[0];//getthelengthfor(i=len;i=1;i--)couta[i];coutendl;}高精度加法问题描述：输入a，b（10240）两个数，输出a+b的值。样例输入：9999999999999999999912345678901234567890样例输出：112345678901234567889算法分析•算法思想类似于竖式加法运算，注意进位处理。把计算结果存到c中：(1)先计算：直接将a[i]和b[i]相加，结果放在c[i]中。…….a[3]a[2]a[1]…….b[3]b[2]b[1]+……c[3]c[2]c[1]思考：要进行多少位加法呢？应该取a或b中较长的位数。对10进制而言，c[i]中的数可能的取值范围是什么？合要求的取值范围是什么？需要作什么处理？算法分析(2)处理进位从最低位开始，逐位整理：把本位模10，向高一位进位：c[i+1]+=c[i]/10;c[i]=c[i]%10;思考：最多要处理多少位呢？因为两数相加最多向前进一位，所以我们把长度加1。len++;for(i=1;ilen;i++)//注意是ilen,写成i=len结果不错，但道理不对{c[i+1]+=c[i]/10;c[i]=c[i]%10;}算法分析(3)去掉最高位的0因为两数相加,也可能不产生进位，因此要把这种情况下最高位的0去掉，其实就是减小和的长度len的值。While((len1)&&(c[len]==0))len--;注意，len1的条件是必要的，因为如果和是0的话，想一想该如何保存。voidadd(hpa,hpb,hp&c)//Adda,btoc{hpd;inti,len;memset(d,0,sizeof(d));//d清0if(a[0]b[0])len=a[0];//求和的位数elselen=b[0];for(i=1;i=len;i++)//逐位相加d[i]=a[i]+b[i];len++;//位数加1for(i=1;ilen;i++)//处理进位{d[i+1]+=d[i]/10;d[i]%=10;}while((len1)&&(d[len]==0))//处理最高位len--;d[0]=len;memcpy(c,d,sizeof(d));//保存结果}思考：能不能不用d，直接让c参与加法运算呢？提示：结果要保存在a或b中,即Add(a,b,a),不用d行吗？高精度减法运算问题表述：输入a，b（10240）两个数，输出a-b的值。样例2输入：9991000样例2输出：-1样例1输入：456409样例1输出：47算法分析1、比较a和b的大小，从而确定结果的正负号2、依照由低位至高位的顺序进行减法运算。在每一次位运算中，若出现不够减的情况(a[i]b[i])，则向高位借位。在进行了减运算后，若高位为0，则要减少结果的长度。在具体计算过程中，仍然用三位走的办法。voidsub(hpa,hpb,hp&c)//amustbegreaterthanb{inti,len;hpd;memset(d,0,sizeof(d));//cleardlen=a[0];for(i=1;i=len;i++)d[i]=a[i]-b[i];for(i=1;i=len;i++)if(d[i]0)//处理借位{d[i]+=10;d[i+1]-=1;}while((len1)&&(d[len]==0))//整理差的长度len--;d[0]=len;memcpy(c,d,sizeof(d));}写程序的小经验1、数组的清零：保存结果的数组使用前一般都要清零：For(i=0;iMAXLEN;i++)a[i]=0;Memset(a,0,sizeof(a))2、变量的使用要规范：如：循环控制变量一般用i、j、k，一般不要用m、n等。长度用len表示。这样容易找错误。比较两个高精度数大小当ab，返回1；ab,返回-1；a==b，返回0intcompare(hpa,hpb){inti;if(a[0]b[0])return1;if(a[0]b[0])return-1;for(i=a[0];i=1;i--)if(a[i]b[i])return1;elseif(a[i]b[i])return-1;return0;}求Fibonacci数列的第n项Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？已知：N=1000F(i):第i个月后共有的兔子对数。F(1)=1;F(2)=1;f(3)=2;f(4)=3;f(5)=5;f(6)=8;递推公式F(i)=f(i-2)+f(i-1)//用基本类型就可解决unsignedlonglongfibo(intn){unsignedlonglongf0,f1,t;inti;if((n==1)||(n==2))return1;f0=1;f1=1;for(i=3;i=n;i++){t=f0+f1;f0=f1;f1=t;}returnf1;}当N=93小结:高精度运算毕竟比基本类型运算麻烦,费时，因此只有在确有必要时才使用voidfibo(intn,hp&ans){hpf0,f1,t;inti;memset(ans,0,sizeof(ans));f0[0]=1;f0[1]=1;f1[0]=1;f1[1]=1;if((n==1)||(n==2)){ans[0]=1;ans[1]=1;return;}for(i=3;i=n;i++){add(f0,f1,t);memcpy(f0,f1,sizeof(f1));memcpy(f1,t,sizeof(t));}memcpy(ans,f1,sizeof(f1));}小结：高精度数不一定非要经过“输入-转换”过程。也可能是通过计算直接产生。当N93时高精度数乘以整型数运算问题表述：精确计算n的阶乘n!（7n80）样例输入：20样例输出：2432902008176640000算法分析1.估算n!所需的高精度数组长度2.被乘数（高精度）从低位向高位逐位乘以乘数（整数）1、估算n!所需的高精度数组长度因为80!808010080=(102)80=10160所以80！可以用160个数组元素a[1],a[2],…,a[160]来存放，一个数组元素存放一个数位上的数字。同样的方法，可以估算出100！可以用200位的数组来存放。n!=1*2*3*…*k*(k+1)*…(n-1)*n可以知道，当n大于某个数时，n!将无法再用基本类型装下，需要用高精度数来存放，而每次的乘数则是一个基本整型，因此求n!的问题是一个高精度数乘以一个基本整型。2.高精度数乘以整型数voidmultiply(hpa,intb,hp&c){hpd;inti,len,t;memset(d,0,sizeof(d));len=a[0];for(i=1;i=len;i++)d[i]=a[i]*b;for(i=1;i=len;i++){d[i+1]+=d[i]/10;d[i]%=10;}len++;while(d[len]){d[len+1]=d[len]/10;d[len]%=10;len++;}while((d[len]==0)&&(len1))len--;d[0]=len;memcpy(c,d,sizeof(d));}后一个for循环和while循环都是来处理进位用的。为什么要这么麻烦？因为我们不知道整数b有多少位。可以写一个函数去求一个整数的位数。然后就可以只用一个for循环处理进位了。可以把两个for循环合在一块，象后一页的程序一样。2.高精度数乘以整型数voidmultiply(hpa,intb,hp&c){hpd;inti,len,t;memset(d,0,sizeof(d));len=a[0];for(i=1;i=len;i++){t=a[i]*b+d[i];d[i]=t%10;d[i+1]=t/10;}len++;while(d[len]){d[len+1]=d[len]/10;d[len]%=10;len++;}while((d[len]==0)&&(len1))len--;d[0]=len;memcpy(c,d,sizeof(d));}intmain(){intn,i;hpans;cinn;ans[0]=1;ans[1]=1;for(i=2;i=n;i++)multiply(ans,i,ans);for(i=ans[0];i=1;i--)coutans[i];coutendl;return0;}高精度数乘以高精度数样例输入：1234567890098765432100样例输出：1219326311126352690000问题表述：输入a，b（10100）两个数，输出a*b的值。算法分析1、积的位数为lena+lenb-1或者lena+lenb；2、如果暂且不考虑进位关系，则ai*bj应该累加在积的第j+i-1位上：c[i+j-1]:=a[i]*b[j]+c[i+j-1];3、可以先乘、后处理进位1、不考虑进位关系，a[i]*b[j]累加在积的第j+i-1位上，积用c存储。for(i=1;i=lena;i++)for(j=1;j=lenb;j++)c[i+j-1]=c[i+j-1]+a[i]*b[j];83764321228abc8376448505428abc8376453568abc1)b的第1位乘a的各位2)b的第2位乘a的各位3)处理c的各位进位2、从低位到高位逐位向前处理进位lenc=lena+lenb;for(i=1;i=lenc;i++)