ACM暑期培训资料课件

高精度运算理学院计算机系姚娟高精度运算理学院计算机系姚娟1计算机能做的和不能做的计算机的限制：精度、范围(：-2^31~2^31-1,即-2147483648~2147483647)计算机：突破了人的运算速度极限对运算的数据进行了“合理”的假设要解决假设之外的事情，它们的数量不多、但常常极其重大。比如中国的粮食安全问题：13亿人口、人均需要多少多少耕地、亩产多少、上年余积多少……计算机能做的和不能做的计算机的限制：精度、范围(：-2^32大整数加法1、链接地址

2、问题描述求不多于100个不超过100位的非负整数的之和。输入数据有n行（n<=101），前1行，每行是一个不超过100位的非负整数，最后一行0表示输入结束。输出数据1行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。大整数加法1、链接地址3输入样例1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678900输出样例370370367037037036703703703670输入样例4大整数加法(1503)解题思路用字符型或整型数组来存放大整数[0]存放个位数，[1]存放十位数，[2]存放百位数……模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。1[101]保存第一个数，用2[100]表示第二个数，然后逐位相加，相加的结果直接存放在1中。要注意处理进位。为什么？1数组长度定为101数组定义稍微大点例如：189+23运算过程那么从左到右189981+023320+212212从左到右计算的好处：最高位加法进位时，只需往后面加1位；假如依旧从右到左进行加法，那么最后需要进位是需要把后面的数字都往后移一位，比较难以复杂和掌握。大整数加法(1503)解题思路用字符型或整型数组来存放大51503参考程序(1[]2[]12){ (*); 0; 1>212; (1<1)1[i]=0; 缺位前导补0 (2<1)2[i]=0; (0<) 1[i]1[i]2[i]; 1(1);}1503参考程序(1[]2[]12)61503参考程序归整(*n){ 0; (a[1]0>1) 去掉前导数字0，确定数组当前长度 ; (0<) { (a[k]>=10) { a[1][1][k]/10; 对数值超过9的位进行归整处理 a[k][k]%10; } } (a[k]0)1; 确定数组的最终长度 ;}1503参考程序归整71503参考程序(){ [10]; 1[10]2[10]; 00; 12; 1[0]=0; 1=1; (1) { >>; ([0]'0'); 2(); (2-10>=0;) 2[]=[i]-'0'; (1212); } (1-1>=0) <<1[i]; 0;}1503参考程序()8大整数乘法1、链接地址

2、问题描述求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。大整数乘法1、链接地址9输入样例 12345678900 98765432100输出样例1219326311126352690000输入样例10大整数乘法(2389)解题思路在程序中，用1[200]和2[200]分别存放两个乘数，用[400]来存放积。计算的中间结果也都存在中。长度取400是因为两个200位的数相乘，积最多会有400位。1[0],2[0],[0]都表示个位。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。现以835×49为例来说明程序的计算过程。大整数乘法(2389)解题思路在程序中，用1[200]11先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，结果如下：大整数乘法(2389)解题思路接下来算4×5。此处4×5的结果代表20个10，因此要c[1]20，变为：再下来算4×3。此处4×3的结果代表12个100，因此要c[2]12，变为：先算835×9。5×9得到45个1，3×9得到27个12大整数乘法(2389)解题思路最后算4×8。此处4×8的结果代表32个1000，因此要c[3]32，变为：乘法过程完毕。接下来从c[0]开始向高位逐位处理进位问题。c[0]留下5，把4加到c[1]上，c[1]变为51后，应留下1，把5加到c[2]上……最终使得c里的每个元素都是1位数，结果就算出来了：规律：一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第位上。这里i,j都是从右往左，从0开始数。大整数乘法(2389)解题思路最后算4×8。此处4×8132389参考程序<><>;200+10;a[][];c[2*];12;;字符串s转换为整型数组t(*t){ ; (); (0<) t[m][1]-'0';}2389参考程序<>142389参考程序乘法：输入用字符串表示的长整数m1、m2返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组c(*m1*m2*){ ; (0<) 用第二个数乘以第一个数,每次一位 (0<) c[][][i]*b[j]; 先乘起来,后面统一进位 (0<*2-1) 循环统一处理进位问题 (c[i]>=10) { c[1][1][i]/10; c[i][i]%10; } 2*1; (c[i]0i>0)1; 跳过高位的0 *; }2389参考程序乘法：输入用字符串表示的长整数m1、m2152389参考程序(){ ; (>>1>>2) { (0<) { a[i]=0; b[i]=0; } (1); (2); (0<2*)c[i]=0; (); (>=0) <<c[j]; <<; } 0;}2389参考程序()16大整数除法1、链接地址

2、问题描述求两个大的正整数相除的商输入数据第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符输出要求n行，每组测试数据有一行输出是相应的整数商大整数除法1、链接地址17问题描述输入样例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345问题描述输入样例18基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。解题思路基本的思想是反复做减法，看看从被除数里最多能减去多少个除数19参考程序<><>2001[+10];2[+10];1[+10];被除数,1[0]对应于个位2[+10];除数,2[0]对应于个位[+10];存放商，[0]对应于个位长度为1的大整数p1减去长度为2的大整数p2结果放在p1里，返回值代表结果的长度如不够减返回-1，正好减完返回0(*p1,*p2,1,2){i;(1<2)-1;参考程序<>204、参考程序下面判断p1是否比p2大，如果不是，返回-1(12){(i=1-1;i>=0;i){(p1[i]>p2[i]);1>p2(p1[i]<p2[i])-1;1<p2}}(i=0;i<1;i){要求调用本函数确保当i>2时，p2[i]＝0p1[i]p2[i];(p1[i]<0){p1[i]10;p1[1];}}(i=1-1;i>=0;)(p1[i])找到最高位第一个不为0i+1;0全部为0，说明两者相等}4、参考程序下面判断p1是否比p2大，如果不是，返回-21参考程序(){t,n;>>n;(t=0;t<n;t){>>1;>>2;i,j;1=(1);(1,0,(1));(2,0,(2));(,0,());(j=0,i=1-1>=0;i)1[]=1[i]-'0';2=(2);(j=0,i=2-1>=0;i)2[]=2[i]-'0';(1<2){<<"0\n";;}参考程序()22参考程序=1-2;(>0){(i=1-1;i>=;i)2[i]=2[]朝高位移动(;i>=0;)低位补02[i]=0;2=1;}(j=0;j<=;j){;一直减到不够减为止先减去若干个2×(10的次方)，不够减了，再减去若干个2×(10的1次方)，......((=(1,2,1,2))>=0){1=;[];每成功减一次，则将商的相应位加1}}参考程序=1-2;23参考程序下面输出结果，先跳过高位0(i=;(i>=0)([i]0);i);(i>=0)(;i>=0;)<<[i];

<<"0";<<;}0;}参考程序下面输出结果，先跳过高位024课堂练习-八进制小数链接：描述八进制小数可以用十进制小数精确的表示。比如，八进制里面的0.75等于十进制里面的0.963125(7/8+5/64)。所有小数点后位数为n的八进制小数都可以表示成小数点后位数不多于3n的十进制小数。

你的任务是写一个程序，把(0,1)中的八进制小数转化成十进制小数。输入输入包括若干八进制小数，每个小数占用一行。每个小数的形式是01d2d3...，这里是八进制数0...7，而且已知0<k<15。输出对于每个输入的八进制小数，输入如下形式的一行

01d2d3...[8]=01D2D3...[10]这里左边是输入的八进制小数，右边是相等的十进制小数。输出的小数末尾不能有0，也就是说不等于0。课堂练习-八进制小数链接：25课堂练习-八进制小数样例输入0.750.00010.01234567样例输出0.75[8]=0.953125[10]0.0001[8]=0.000244140625[10]0.01234567[8]=0.020408093929290771484375[10]提示如果你使用字符串读取八进制小数，你可以使用如下的形式中止输入

[100];

(>>){

...

}课堂练习-八进制小数样例输入26暑期练习1001难度一般英文链接中文链接2413英文链接题意是给出两个长整数a和b（可达100位），求a和b之间斐波那契数的个数。其中：f(1)=1;f(2)=2(n)(1)(2);

斐波数列从1开始算法：这题就是求斐波那契数列，然后在一定范围内查找斐波那契数的个数。但由于范围可达100位，c或的长整型是不够用的。只能用长整数加法来求斐波那契数列了。暑期练习1001难度一般27DayDayUp~Thankyou~DayDayUp~Thankyou~28演讲完毕，谢谢观看！演讲完毕，谢谢观看！29高精度运算理学院计算机系姚娟高精度运算理学院计算机系姚娟30计算机能做的和不能做的计算机的限制：精度、范围(：-2^31~2^31-1,即-2147483648~2147483647)计算机：突破了人的运算速度极限对运算的数据进行了“合理”的假设要解决假设之外的事情，它们的数量不多、但常常极其重大。比如中国的粮食安全问题：13亿人口、人均需要多少多少耕地、亩产多少、上年余积多少……计算机能做的和不能做的计算机的限制：精度、范围(：-2^331大整数加法1、链接地址

2、问题描述求不多于100个不超过100位的非负整数的之和。输入数据有n行（n<=101），前1行，每行是一个不超过100位的非负整数，最后一行0表示输入结束。输出数据1行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。大整数加法1、链接地址32输入样例1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678900输出样例370370367037037036703703703670输入样例33大整数加法(1503)解题思路用字符型或整型数组来存放大整数[0]存放个位数，[1]存放十位数，[2]存放百位数……模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。1[101]保存第一个数，用2[100]表示第二个数，然后逐位相加，相加的结果直接存放在1中。要注意处理进位。为什么？1数组长度定为101数组定义稍微大点例如：189+23运算过程那么从左到右189981+023320+212212从左到右计算的好处：最高位加法进位时，只需往后面加1位；假如依旧从右到左进行加法，那么最后需要进位是需要把后面的数字都往后移一位，比较难以复杂和掌握。大整数加法(1503)解题思路用字符型或整型数组来存放大341503参考程序(1[]2[]12){ (*); 0; 1>212; (1<1)1[i]=0; 缺位前导补0 (2<1)2[i]=0; (0<) 1[i]1[i]2[i]; 1(1);}1503参考程序(1[]2[]12)351503参考程序归整(*n){ 0; (a[1]0>1) 去掉前导数字0，确定数组当前长度 ; (0<) { (a[k]>=10) { a[1][1][k]/10; 对数值超过9的位进行归整处理 a[k][k]%10; } } (a[k]0)1; 确定数组的最终长度 ;}1503参考程序归整361503参考程序(){ [10]; 1[10]2[10]; 00; 12; 1[0]=0; 1=1; (1) { >>; ([0]'0'); 2(); (2-10>=0;) 2[]=[i]-'0'; (1212); } (1-1>=0) <<1[i]; 0;}1503参考程序()37大整数乘法1、链接地址

2、问题描述求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。大整数乘法1、链接地址38输入样例 12345678900 98765432100输出样例1219326311126352690000输入样例39大整数乘法(2389)解题思路在程序中，用1[200]和2[200]分别存放两个乘数，用[400]来存放积。计算的中间结果也都存在中。长度取400是因为两个200位的数相乘，积最多会有400位。1[0],2[0],[0]都表示个位。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。现以835×49为例来说明程序的计算过程。大整数乘法(2389)解题思路在程序中，用1[200]40先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，结果如下：大整数乘法(2389)解题思路接下来算4×5。此处4×5的结果代表20个10，因此要c[1]20，变为：再下来算4×3。此处4×3的结果代表12个100，因此要c[2]12，变为：先算835×9。5×9得到45个1，3×9得到27个41大整数乘法(2389)解题思路最后算4×8。此处4×8的结果代表32个1000，因此要c[3]32，变为：乘法过程完毕。接下来从c[0]开始向高位逐位处理进位问题。c[0]留下5，把4加到c[1]上，c[1]变为51后，应留下1，把5加到c[2]上……最终使得c里的每个元素都是1位数，结果就算出来了：规律：一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第位上。这里i,j都是从右往左，从0开始数。大整数乘法(2389)解题思路最后算4×8。此处4×8422389参考程序<><>;200+10;a[][];c[2*];12;;字符串s转换为整型数组t(*t){ ; (); (0<) t[m][1]-'0';}2389参考程序<>432389参考程序乘法：输入用字符串表示的长整数m1、m2返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组c(*m1*m2*){ ; (0<) 用第二个数乘以第一个数,每次一位 (0<) c[][][i]*b[j]; 先乘起来,后面统一进位 (0<*2-1) 循环统一处理进位问题 (c[i]>=10) { c[1][1][i]/10; c[i][i]%10; } 2*1; (c[i]0i>0)1; 跳过高位的0 *; }2389参考程序乘法：输入用字符串表示的长整数m1、m2442389参考程序(){ ; (>>1>>2) { (0<) { a[i]=0; b[i]=0; } (1); (2); (0<2*)c[i]=0; (); (>=0) <<c[j]; <<; } 0;}2389参考程序()45大整数除法1、链接地址

2、问题描述求两个大的正整数相除的商输入数据第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符输出要求n行，每组测试数据有一行输出是相应的整数商大整数除法1、链接地址46问题描述输入样例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345问题描述输入样例47基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。解题思路基本的思想是反复做减法，看看从被除数里最多能减去多少个除数48参考程序<><>2001[+10];2[+10];1[+10];被除数,1[0]对应于个位2[+10];除数,2[0]对应于个位[+10];存放商，[0]对应于个位长度为1的大整数p1减去长度为2的大整数p2结果放在p1里，返回值代表结果的长度如不够减返回-1，正好减完返回0(*p1,*p2,1,2){i;(1<2)-1;参考程序<>494、参考程序下面判断p1是否比p2大，如果不是，返回-1(12){(i=1-1;i>=0;i){(p1[i]>p2[i]);1>p2(p1[i]<p2[i])-1;1<p2}}(i=0;i<1;i){要求调用本函数确保当i>2时，p2[i]＝0p1[i]p2[i];(p1[i]<0){p1[i]10;p1[1];}}(i=1-1;i>=0;)(p1[i])找到最高位第一个不为0i+1;0全部为0，说明两者相等}4、参考程序下面判断p1是否比p2大，如果不是，返回-50参考程序(){t,n;>>n;(t=0;t<n;t){>>1;>>2;i,j;1=(1);(1,0,(1));(2,0,(2));(,0,());(j=0,i=1-1>=0;i)1[]=1[i]-'0';2=(2);(j=0,i=2-1>=0;i)2[]=2[i]-'0';(1<2){<<"0\n";;}参考程序()51参考程序=1-2;(>0){(i=1-1;i>=;i)2[i]=2[]朝高位移动(;i>=0;)低位补02[i]=0;2=1;}(j=0;j<=;j){;一直减到不够减为止