ACM暑期培训资料.ppt

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

2、第2页，共29页。大整数加法1、链接地址 2、问题描述求不多于100个不超过100 位的非负整数的之和。输入数据有n行（n212;(11)1i=0;缺位前导补缺位前导补0(21)2i=0;(01)去掉前导数字去掉前导数字0，确定数组当前长度，确定数组当前长度;(0=10)a11k/10;对数值超过对数值超过9的位进行归整处理的位进行归整处理akk%10;(ak0)1;确定数组的最终长度确定数组的最终长度;第7页，共29页。1503 参考程序()10;110210;00;12;10=0;1=1;(1);(00);2();(2-10=0;)2=i-0;(1212);(1-1=0)1i;0;第8页，

3、共29页。大整数乘法1、链接地址 2、问题描述求两个不超过200 位的非负整数的积。输入数据有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。第9页，共29页。输入样例1234567890098765432100输出样例1219326311126352690000 第10页，共29页。大整数乘法(2389)解题思路 在程序中，用在程序中，用 1200和和 2200分别存放两个乘数，分别存放两个乘数，用用400来存放积。计算的中间结果也都存在中。来存放积。计算的中间结果也都存在中。

4、长度取长度取400是因为两个是因为两个200 位的数相乘，积最多位的数相乘，积最多会有会有400 位。位。10,20,0都表示个位。都表示个位。计算的过程基本上和小学生列竖式做乘法相同。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。留待最后统一处理。现以现以 83549 为例来说明程序的计算过程。为例来说明程序的计算过程。第11页，共29页。先算先算8359。59 得到得到45 个个1，39 得到得到27 个个10，89 得到得到72 个个100。由于不急于处理进位，所以由于不急于处理进位，所以8

5、359 算完后，结果如下：算完后，结果如下：大整数乘法(2389)解题思路接下来算接下来算45。此处。此处45 的结果代表的结果代表20 个个10，因此要，因此要 c120，变，变为：为：再下来算再下来算43。此处。此处43 的结果代表的结果代表12 个个100，因此要，因此要 c2 12，变，变为：为：第12页，共29页。大整数乘法(2389)解题思路最后算最后算 48。此处。此处48 的结果代表的结果代表 32 个个1000，因此要，因此要 c3 32，变为：，变为：乘法过程完毕。接下来从乘法过程完毕。接下来从 c0开始向高位逐位处理进位问题。开始向高位逐位处理进位问题。c0留下留下5，把

6、，把4 加到加到c1上，上，c1变为变为51 后，应留下后，应留下1，把，把5 加加到到c2上上最终使得最终使得c 里的每个元素都是里的每个元素都是1 位数，结果就算出位数，结果就算出来了：来了：规律：一个数的第规律：一个数的第i 位和另一个数的第位和另一个数的第j 位相乘所得的数，一定位相乘所得的数，一定是要累加到结果的第是要累加到结果的第 位上。这里位上。这里i,j 都是从右往左，从都是从右往左，从0 开始数。开始数。第13页，共29页。2389 参考程序 ;200+10;a;c2*;12;字符串字符串s转换为整型数组转换为整型数组t(*t);();(0)tm1-0;第14页，共29页。2

7、389 参考程序乘法：输入用字符串表示的长整数乘法：输入用字符串表示的长整数m1、m2返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组c(*m1*m2*);(0)用第二个数乘以第一个数用第二个数乘以第一个数,每次一位每次一位(0)ci*bj;先乘起来先乘起来,后面统一进位后面统一进位(0=10)c11i/10;cii%10;2*1;(ci0 i0)1;跳过高位的跳过高位的0*;第15页，共29页。2389 参考程序();(12)(0)ai=0;bi=0;(1);(2);(0=0)cj;0;第16页，共29页。大整数除法1、链接

8、地址 2、问题描述求两个大的正整数相除的商输入数据 第1 行是测试数据的组数n，每组测试数据占2 行，第1 行是被除数，第2 行是除数。每组测试数据之间有一个空行，每行数据不超过100 个字符输出要求 n 行，每组测试数据有一行输出是相应的整数商第17页，共29页。问题描述问题描述输入样例32405337312963373359009260457742057439230496493930355595797660791082739646298719258531870175258442993116087037290707924897109501250979055088379319789410000

9、0000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345第18页，共29页。基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546 除以23 为例来看一下：开始商为

10、0。先减去23 的100 倍，就是2300，发现够减3 次，余下646。于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用186 减去23，够减8 次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10 倍、100 倍的时候，不用做乘法，直接在除数后面补0 即可。解题思路解题思路第19页，共29页。参考程序参考程序n n n 200n 1+10;n 2+10;n 1+10;被除数被除数,10对应于个位对应于个位n 2+10;除数除数,20对应于个位对应于个位n +10;存放商，存放

11、商，0对应于个位对应于个位n长度为长度为 1 的大整数的大整数p1 减去长度为减去长度为2 的大整数的大整数p2n结果放在结果放在p1 里，返回值代表结果的长度里，返回值代表结果的长度n如不够减返回如不够减返回-1，正好减完返回，正好减完返回 0n(*p1,*p2,1,2)nn i;n (1=0;i )n n (p1i p2i);1p2n (p1i p2i)-1;1p2n n n (i=0;i 2 时，时，p2i 0n p1i p2i;n (p1i=0;)n (p1i)找到最高位第一个不为找到最高位第一个不为0n i+1;n 0全部为全部为0，说明两者相等，说明两者相等n第21页，共29页。参

12、考程序参考程序n()nn t,n;n n;n (t=0;t 1;n 2;n i,j;n 1=(1);n (1,0,(1);n (2,0,(2);n (,0,();n (j=0,i=1-1=0;i)n 1=1i-0;n 2=(2);n (j=0,i=2-1=0;i)n 2=2i-0;n (1 2)n n 0)n n (i=1-1;i=;i )n 2i=2朝高位移动朝高位移动n (;i=0;)低位补低位补0n 2i=0;n 2=1;n n (j=0;j=0)n n 1=;n ;每成功减一次，则将商的相应位加每成功减一次，则将商的相应位加1n n 第23页，共29页。参考程序参考程序n 下面输出结果

13、，先跳过高位下面输出结果，先跳过高位0n (i=;(i=0)(i 0);i );n (i=0)n (;i=0;)n i;n n 0;n ;n n 0;n第24页，共29页。课堂练习-八进制小数 链接：链接：描述描述 八进制小数可以用十进制小数精确的表示。比如，八进制里面的八进制小数可以用十进制小数精确的表示。比如，八进制里面的0.75等于等于十进制里面的十进制里面的0.963125(7/8+5/64)。所有小数点后位数为。所有小数点后位数为n的八进制小数的八进制小数都可以表示成小数点后位数不多于都可以表示成小数点后位数不多于3n的十进制小数。的十进制小数。你的任务是写一个程序，把你的任务是写一

14、个程序，把(0,1)中的八进制小数转化成十进制小数。中的八进制小数转化成十进制小数。输入输入 输入包括若干八进制小数，每个小数占用一行。每个小数的形式是输入包括若干八进制小数，每个小数占用一行。每个小数的形式是01d2d3.，这里是八进制数，这里是八进制数0.7，而且已知，而且已知0 k ).第26页，共29页。暑期练习暑期练习 1001 难度一般难度一般英文链接英文链接中文链接中文链接 2413 英文链接英文链接题意是给出两个长整数题意是给出两个长整数a和和b（可达（可达100位），求位），求a和和b之间斐波那契之间斐波那契数的个数。数的个数。其中：其中：f(1)=1;f(2)=2(n)(1)(2);斐波数列从斐波数列从1开始开始算法：算法：这题就是求斐波那契数列，然后在一定范围内查找斐波那契数的个这题就是求斐波那契数列，然后在一定范围内查找斐波那契数的个数。但由于范围可达数。但由于范围可达100位，位，c或的长整型是不够用的。只能用长整或的长整型是不够用的。只能用长整数加法来求斐波那契数列了。数加法来求斐波那契数列了。第27页，共29页。Day Day Up Thank you第28页，共29页。演讲完毕，谢谢观看！第29页，共29页。