高精度算法ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高精度运算,High-precision Algorithm,高精度运算High-precision Algorithm,1,基本整数类型的取值范围,类型数值范围 占字节数,unsigned char 0.255 1,char -128.127 1,int(long)-2147483648.2147483647 10,9,4,unsigned int(long)0.4294967295 4,long long -9223372036854775808.,9223372036854775807 10,18,8,unsigned 0.18446744073709551615 8,Long long 使用时有限制，例如，不能作为数组的下标等。,基本整数类型的取值范围类型数值范围,2,为什么需要高精度运算,当要处理的数据超过了任何一种数据类型所能容纳的范围,这种数称为高精度数,必须自定义类型来存储.同时还要自行编写高精度数的运算函数(加减乘除等),为什么需要高精度运算当要处理的数据超过了任何一种数据类型所能,3,高精度数的输入和存储,在运算对象的数值范围为任何数据类型所无法容纳的情况下,采用数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）来表示一个数,就称为高精度数。,1、采用字符串形式输入，并将其转化为整数数组。,2、用一个整型变量记录数据的实际长度（即数组的元素个数）,高精度数的输入和存储在运算对象的数值范围为任何数据类型所无法,4,字符串到整数数组的转换,字符串存储时,数的高位被存放在字符串的低位。,7,6,3,2,1,8,0 1 2 3 4 5 6 7,转换成整数数组时，要把高精度数的低位“还原”到数组的低位。,这样才便于后续计算。a1存放最低位，a6存放最高位。,高精度数的位数可存放在a0中。也可以另用一个变量存放。,字符串s,6,8,1,2,3,6,7,0 1 2 3 4 5 6 7,整型a,字符串到整数数组的转换字符串存储时,数的高位被存放在字符串的,5,const int MAXLEN=241;/最大长度为240位,typedef int hpMAXLEN;/定义hp为高精度类型,void Str2hp(string s,hp&a)/s转换后存入a,int i,len;,memset(a,0,sizeof(a);/clear a,len=s.size();,a0=len;/save the length,for(i=0;i=1;i-),cout ai;,cout endl;,输出void Print(hp a),7,高精度加法,问题描述：,输入a，b（10,240,）两个数，输出a+b的值。,样例输入：,99999999999999999999,12345678901234567890,样例输出：,112345678901234567889,高精度加法问题描述：样例输入：,8,算法分析,算法思想类似于竖式加法运算，注意进位处理。,把计算结果存到c中：,(1)先计算：直接将ai和bi相加，结果放在ci中。,.a3 a2 a1,.b3 b2 b1,+,c3 c2 c1,思考：要进行多少位加法呢？,应该取a或b中较长的位数。,对10进制而言，ci中的数可能的取值范围是什么？合要求的取值范围是什么？需要作什么处理？,算法分析算法思想类似于竖式加法运算，注意进位处理。思考：要进,9,算法分析,(2)处理进位,从最低位开始，逐位整理：把本位模10，向高一位进位：,ci+1+=ci/10;,ci =ci%10;,思考：最多要处理多少位呢？,因为两数相加最多向前进一位，所以我们把长度加1。,len+;,for(i=1;ilen;i+)/注意是ilen,写成i1)&(clen=0),len-;,注意，len1的条件是必要的，因为如果和是0的话，想一想该如何保存。,算法分析(3)去掉最高位的0,11,void add(hp a,hp b,hp&c)/Add a,b to c,hp d;,int i,len;,memset(d,0,sizeof(d);/d清0,if(a0 b0)len=a0;/求和的位数,else len=b0;,for(i=1;i=len;i+)/逐位相加,di=ai+bi;,len+;/位数加1,for(i=1;i 1)&(dlen=0)/处理最高位,len-;,d0=len;,memcpy(c,d,sizeof(d);/保存结果,void add(hp a,hp b,hp&c)/,12,思考：能不能不用d，直接让c参与加法运算呢？,提示：结果要保存在a或b中,即Add(a,b,a),不用d,行吗？,高精度算法ppt课件,13,高精度减法运算,问题表述：,输入a，b（10,240,）两个数，输出a-b的值。,样例2输入：,999,1000,样例2输出：,-1,样例1输入：,456,409,样例1输出：,47,高精度减法运算问题表述：样例2输入：样例1输入：,14,算法分析,1、比较a和b的大小，从而确定结果的正负号,2、依照由低位至高位的顺序进行减法运算。在每一次位运算中，若出现不够减的情况(aibi)，则向高位借位。在进行了减运算后，若高位为0，则要减少结果的长度。,在具体计算过程中，仍然用三位走的办法。,算法分析1、比较a和b的大小，从而确定结果的正负号,15,void sub(hp a,hp b,hp&c)/a must be greater than b,int i,len;,hp d;,memset(d,0,sizeof(d);/clear d,len=a0;,for(i=1;i=len;i+),di=ai-bi;,for(i=1;i=len;i+),if(di 1)&(dlen=0)/整理差的长度,len-;,d0=len;,memcpy(c,d,sizeof(d);,void sub(hp a,hp b,hp&c)/,16,写程序的小经验,1、数组的清零：,保存结果的数组使用前一般都要清零：,For(i=0;iMAXLEN;i+),ai=0;,Memset(a,0,sizeof(a),2、变量的使用要规范：,如：循环控制变量一般用 i、j、k，一般不要用m、n等。,长度用len表示。,这样容易找错误。,写程序的小经验For(i=0;ib，返回1；a b0)return 1;,if(a0=1;i-),if(ai bi)return 1;,else if(ai b，返回1；ab,返回-1；a,18,求,Fibonacci数列的第n项,Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。,问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？,已知：N=1000,F(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),求Fibonacci数列的第n项Fibonacci数列的代表,19,/用基本类型就可解决,unsigned long long fibo(int n),unsigned long long f0,f1,t;,int i;,if(n=1)|(n=2)return 1;,f0=1;f1=1;,for(i=3;i=n;i+),t=f0+f1;,f0=f1;,f1=t;,return f1;,当N=93,小结:高精度运算毕竟比基本类型运算麻烦,费时，因此只有在确有必要时才使用,/用基本类型就可解决当N=93小结:高精度运算毕竟比基,20,void fibo(int n,hp&ans),hp f0,f1,t;,int i;,memset(ans,0,sizeof(ans);,f00=1;f01=1;,f10=1;f11=1;,if(n=1)|(n=2),ans0=1;,ans1=1;,return;,f,or(i=3;i93时,void fibo(int n,hp&ans),21,高精度数乘以整型数运算,问题表述：,精确计算n的阶乘n!（7n80）,样例输入：,20,样例输出：,2432902008176640000,高精度数乘以整型数运算问题表述：样例输入：,22,算法分析,估算n!所需的高精度数组长度,被乘数（高精度）从低位向高位逐位乘以乘数（整数）,算法分析估算n!所需的高精度数组长度,23,1、估算n!所需的高精度数组长度,因为80!80,80,100,80,=(10,2,),80,=10,160,所以80！可以用160个数组元素a1,a2,a160来存放，一个数组元素存放一个数位上的数字。,同样的方法，可以估算出100！可以用200位的数组来存放。,n!=1*2*3*k*(k+1)*(n-1)*n,可以知道，当n大于某个数时，n!将无法再用基本类型装下，需要用高精度数来存放，而每次的乘数则是一个基本整型，因此求n!的问题是一个高精度数乘以一个基本整型。,1、估算n!所需的高精度数组长度,24,2.高精度数乘以整型数,void multiply(hp a,int b,hp&c),hp d;,int i,len,t;,memset(d,0,sizeof(d);,len=a0;,for(i=1;i=len;i+),di=ai*b;,for(i=1;i 1),len-;,d0=len;,memcpy(c,d,sizeof(d);,后一个for循环和while循环都是来处理,进位用的。为什么要这么麻烦？,因为我们不知道整数b有多少位。,可以写一个函数去求一个整数的位数。,然后就可以只用一个for循环处理进位了。,可以把两个for循环合在一块，象后一页,的程序一样。,2.高精度数乘以整型数 len+;后一个for循环和,25,2.高精度数乘以整型数,void multiply(hp a,int b,hp&c),hp d;,int i,len,t;,memset(d,0,sizeof(d);,len=a0;,for(i=1;i 1),len-;,d0=len;,memcpy(c,d,sizeof(d);,2.高精度数乘以整型数 len+;,26,int main(),int n,i;,hp ans;,cin n;,ans0=1;,ans1=1;,for(i=2;i=1;i-),cout ansi;,cout endl;,return 0;,int main(),27,高精度数乘以高精度数,样例输入：,12345678900,98765432100,样例输出：,1219326311126352690000,问题表述：,输入a，b（10,100,）两个数，输出a*b的值。,高精度数乘以高精度数样例输入：问题表述：,28,算法分析,1、积的位数为lena+lenb-1或者lena+lenb；,2、如果暂且不考虑进位关系，则ai*bj应该累加在积的第j+i-1位上：ci+j-1:=ai*bj+ci+j-1;,3、可以先乘、后处理进位,算法分析1、积的位数为lena+lenb-1或者lena+l,29,1、不考虑进位关系，ai*bj累加在积的第j+i-1位上，积用c存储。,for(i=1;i=lena;i+),for(j=1;j=lenb;j+),ci+j-1=ci+j-1+ai*bj;,8,3,7,6,4,32,12,28,a,b,c,8,3,7,6,4,48,50,54,28,a,b,c,8,3,7,6,4,5,3,5,6,8,a,b,c,1)b的第1位乘a的各位,2)b的第2位乘a的各位,3)处理c的各位进位,1、不考虑进位关系，ai*bj累加在积的第j+i-1,30,2、从低位到高位逐位向前处理进位,lenc=lena+lenb;,for(