高精度算法课件.ppt

1、High-precision Algorithm基本整数类型的取值范围类型数值范围 占字节数 unsigned char 0.255 1 char -128.127 1 int(long)-2147483648.2147483647 109 4 unsigned int(long)0.4294967295 4 long long -9223372036854775808.9223372036854775807 1018 8 unsigned 0.18446744073709551615 8Long long 使用时有限制，例如，不能作为数组的下标等。为什么需要高精度运算 当要处理的数据超过了任

2、何一种数据类型所能容纳的范围,这种数称为高精度数,必须自定义类型来存储.同时还要自行编写高精度数的运算函数(加减乘除等)高精度数的输入和存储在运算对象的数值范围为任何数据类型所无法容纳的情况下,采用数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）来表示一个数,就称为高精度数。1、采用字符串形式输入，并将其转化为整数数组。2、用一个整型变量记录数据的实际长度（即数组的元素个数）字符串到整数数组的转换 字符串存储时,数的高位被存放在字符串的低位。7632180 1 2 3 4 5 6 7转换成整数数组时，要把高精度数的低位“还原”到数组的低位。这样才便于后续计算。a1存放最低位，a6存放

3、最高位。高精度数的位数可存放在a0中。也可以另用一个变量存放。字符串s68123670 1 2 3 4 5 6 7整型aconst int MAXLEN=241;/最大长度为240位typedef int hpMAXLEN;/定义hp为高精度类型void Str2hp(string s,hp&a)/s转换后存入aint i,len;memset(a,0,sizeof(a);/clear alen=s.size();a0=len;/save the lengthfor(i=0;i=1;i-)cout ai;cout endl;高精度加法问题描述：输入a，b（10240）两个数，输出a+b的值。样

4、例输入：9999999999999999999912345678901234567890样例输出：112345678901234567889算法分析 算法思想类似于竖式加法运算，注意进位处理。把计算结果存到c中：(1)先计算：直接将ai和bi相加，结果放在ci中。.a3 a2 a1 .b3 b2 b1 +c3 c2 c1思考：要进行多少位加法呢？应该取a或b中较长的位数。对10进制而言，ci中的数可能的取值范围是什么？合要求的取值范围是什么？需要作什么处理？算法分析(2)处理进位从最低位开始，逐位整理：把本位模10，向高一位进位：ci+1+=ci/10;ci =ci%10;思考：最多要处理多少

5、位呢？因为两数相加最多向前进一位，所以我们把长度加1。len+;for(i=1;ilen;i+)/注意是ilen,写成i1)&(clen=0)len-;注意，len1的条件是必要的，因为如果和是0的话，想一想该如何保存。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-;

6、d0=len;memcpy(c,d,sizeof(d);/保存结果思考：能不能不用d，直接让c参与加法运算呢？提示：结果要保存在a或b中,即Add(a,b,a),不用d行吗？高精度减法运算问题表述：问题表述：输入输入a，b（10240）两个数，输出）两个数，输出a-b的值。的值。样例样例2 2输入：输入：99999910001000样例样例2 2输出：输出：-1-1样例样例1 1输入：输入：456456409409样例样例1 1输出：输出：4747算法分析1、比较a和b的大小，从而确定结果的正负号2、依照由低位至高位的顺序进行减法运算。在每一次位运算中，若出现不够减的情况(aibi)，则向高位

7、借位。在进行了减运算后，若高位为0，则要减少结果的长度。在具体计算过程中，仍然用三位走的办法。void sub(hp a,hp b,hp&c)/a must be greater than bint i,len;hp d;memset(d,0,sizeof(d);/clear dlen=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);写程序的小经验写程序的小经验1、数组的清零：、数组的清零：保存结果的数组使用前一般都要清零：保存结果的数组

8、使用前一般都要清零：For(i=0;ib，返回1；a b0)return 1;if(a0=1;i-)if(ai bi)return 1;else if(ai bi)return-1;return 0;求Fibonacci数列的第n项Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？已知：N=1000F(i):第第i个月后共有的兔子对数。个月后共有的兔子对数。F(1)=1;F(2)=1;f(3)=2;f

9、(4)=3;f(5)=5;f(6)=8;递推公式递推公式F(i)=f(i-2)+f(i-1)/用基本类型就可解决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小结:高精度运算毕竟比基本类型运算麻烦,费时，因此只有在确有必要时才使用void fibo(int n,hp&ans)hp f0,f1,t;int i;memset(ans,0,sizeof(ans

10、);f00=1;f01=1;f10=1;f11=1;if(n=1)|(n=2)ans0=1;ans1=1;return;for(i=3;i93时 高精度数乘以整型数运算问题表述：问题表述：精确计算精确计算n n的阶乘的阶乘n!n!（7n807n80）样例输入：20样例输出：2432902008176640000算法分析1.估算n!所需的高精度数组长度2.被乘数（高精度）从低位向高位逐位乘以乘数（整数）1、估算n!所需的高精度数组长度因为80!808010080=(102)80=10160所以80！可以用160个数组元素a1,a2,a160来存放，一个数组元素存放一个数位上的数字。同样的方法，可

11、以估算出100！可以用200位的数组来存放。n!=1*2*3*k*(k+1)*(n-1)*n可以知道，当n大于某个数时，n!将无法再用基本类型装下，需要用高精度数来存放，而每次的乘数则是一个基本整型，因此求n!的问题是一个高精度数乘以一个基本整型。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循环都是来处

12、理进位用的。为什么要这么麻烦？因为我们不知道整数b有多少位。可以写一个函数去求一个整数的位数。然后就可以只用一个for循环处理进位了。可以把两个for循环合在一块，象后一页的程序一样。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);int main()int n,i;hp ans;cin n;ans0=1;ans1=1;for(i=2;i=1;i-)cout ansi;cout en

13、dl;return 0;高精度数乘以高精度数样例输入：样例输入：1234567890098765432100样例输出：样例输出：1219326311126352690000问题表述：问题表述：输入输入a，b（10100）两个数，输出）两个数，输出a*b的值。的值。算法分析1、积的位数为lena+lenb-1或者lena+lenb；2、如果暂且不考虑进位关系，则ai*bj应该累加在积的第j+i-1位上：ci+j-1:=ai*bj+ci+j-1;3、可以先乘、后处理进位1、不考虑进位关系，ai*bj累加在积的第j+i-1位上，积用c存储。for(i=1;i=lena;i+)for(j=1;j=le

14、nb;j+)ci+j-1=ci+j-1+ai*bj;83764321228abc8376448505428abc8376453568abc1)b的第1位乘a的各位2)b的第2位乘a的各位3)处理c的各位进位2、从低位到高位逐位向前处理进位lenc=lena+lenb;for(i=1;i 1)&(clenc=0)lenc-;C0=lenc;void high_multiply(hp a,hp b,hp&c)hp d;int i,j,len;memset(d,0,sizeof(d);for(i=1;i=a0;i+)for(j=1;j=b0;j+)di+j-1+=ai*bj;len=a0+b0+1;

15、for(i=1;i 1)len-;d0=len;memcpy(c,d,sizeof(d);int main()int i;hp a,b,ans;string s1,s2;cin s1;cin s2;str2hp(s1,a);str2hp(s2,b);high_multiply(a,b,ans);for(i=ans0;i=1;i-)cout ansi;cout endl;return 0;高精度数除以整型数问题表述：输入a（10240），b（=1;i-)r=r*10+ai;di=r/b;r=r%b;while(len 1)&(dlen=0)len-;d0=len;memcpy(c,d,sizeo

16、f(d);上机练习：上机练习：1、阶乘之和，求、阶乘之和，求1！+2！+3！+n！输入数据输入数据(sumfac.in)：一行，一个整数一行，一个整数n（n=100）输出数据输出数据(sumfac.out):一行，一行，1n的阶乘之和。的阶乘之和。输入样例：输入样例：5输出样例：输出样例：1532、回文词问题描述：若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。又如，对于10进制数87：STEP1：87+78=165 STEP2：165+561=726 STEP3：726+627=1353 STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，求最少经过几步可以得到回文数。输入数据(palin.in)：第一行：一个整数N（2N16），表示进制数第二行：N进制数M，M的位数上限为40。输出数据(palin.out)：第一行：步数S。如果在30步以内（包括30步）不可能得到回文数，则输出“impossible”第二行：生成的回文数。输入样例：输入样例：1087输出样例：44884