ACM暑期培训(共29张).pptx

《ACM暑期培训(共29张).pptx》由会员分享，可在线阅读，更多相关《ACM暑期培训(共29张).pptx（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、年余积多少 大整数加法1、链接地址 http:/poj.org/problem?id=15032、问题描述 求不多于100个不超过100 位的非负整数的之和。输入数据 有n行（nlen2?len1:len2;for(i=len1;ilen+1;i+) an1i=0;/缺位前导补缺位前导补0for(i=len2;ilen+1;i+) an2i=0;for(i=0;i1) /去掉前导数字去掉前导数字0，确定数组当前长度，确定数组当前长度len-;for(k=0;k=10)ak+1=ak+1+ak/10;/对数值超过对数值超过9的位进行归整处理的位进行归整处理ak=ak%10;if(ak!=0) l

3、en=k+1;/确定数组的最终长度确定数组的最终长度return len;POJ1503 参考程序int main()char szLineMAXLEN+10;int an1MAXLEN+10,an2MAXLEN+10;int k=0,i,j=0;int len1,len2;an10=0;len1=1;while(1)cinszLine;if(szLine0=0) break;len2=strlen(szLine);for(i=len2-1,j=0;i=0; i-)an2j+ = szLinei - 0;addition(an1,an2,len1,len2);for(i=len1-1;i=0;

4、i-)coutan1i;return 0;大整数乘法1、链接地址 http:/poj.org/problem?id=23892、问题描述 求两个不超过200 位的非负整数的积。输入数据有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例1234567890098765432100输出样例1219326311126352690000 大整数乘法(POJ2389) 解题思路 在程序中，用在程序中，用unsigned an1200和和unsigned an2200分别存放两个乘数

5、，用分别存放两个乘数，用aResult400来来存放积。计算的中间结果也都存在存放积。计算的中间结果也都存在aResult中。中。aResult长度取长度取400是因为两个是因为两个200 位的数相乘，位的数相乘，积最多会有积最多会有400 位。位。an10, an20, aResult0都表示个位。都表示个位。 计算的过程基本上和小学生列竖式做乘法相同。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。留待最后统一处理。 现以现以 83549 为例来说明程序的计算过程。为例来说明程序的计算过程。先算

6、先算8359。59 得到得到45 个个1，39 得到得到27 个个10，89 得得到到72 个个100。由于不急于处理进位，所以。由于不急于处理进位，所以8359 算完后，结算完后，结果如下：果如下：大整数乘法(POJ2389) 解题思路接下来算接下来算45。此处。此处45 的结果代表的结果代表20 个个10，因此要，因此要 c1+=20，变为：，变为：再下来算再下来算43。此处。此处43 的结果代表的结果代表12 个个100，因此要，因此要 c2+= 12，变为：，变为：大整数乘法(POJ2389) 解题思路最后算最后算 48。此处。此处48 的结果代表的结果代表 32 个个1000，因此要

7、，因此要 c3+= 32，变为：，变为：乘法过程完毕。接下来从乘法过程完毕。接下来从 c0开始向高位逐位处理进位问题。开始向高位逐位处理进位问题。c0留下留下5，把，把4 加到加到c1上，上，c1变为变为51 后，应留下后，应留下1，把，把5 加到加到c2上上最终使得最终使得c 里的每个元素都是里的每个元素都是1 位数，结果就位数，结果就算出来了：算出来了：规律：一个数的第规律：一个数的第i 位和另一个数的第位和另一个数的第j 位相乘所得的数，一位相乘所得的数，一定是要累加到结果的第定是要累加到结果的第i+j 位上。这里位上。这里i, j 都是从右往左，从都是从右往左，从0 开始数。开始数。P

8、OJ2389 参考程序#include#includeusing namespace std;const int MAXLEN=200+10;int aMAXLEN,bMAXLEN;int c2*MAXLEN;string st1,st2;int i,j,k;/字符串字符串s转换为整型数组转换为整型数组tvoid tran(string s,int *t)int m,l;l=s.length();for(m=0;ml;m+)tm=sl-1-m-0;POJ2389 参考程序/乘法：输入用字符串表示的长整数乘法：输入用字符串表示的长整数m1、m2/返回一个表示两个数乘积长度的指针，及表示乘积的一个

9、整型数组返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组cvoid mul(int *m1,int *m2,int *len)int i,j;for(i=0;iMAXLEN;i+)/用第二个数乘以第一个数用第二个数乘以第一个数,每次一位每次一位 for(j=0;jMAXLEN;j+)ci+j=ci+j+ai*bj;/先乘起来先乘起来,后面统一进位后面统一进位for(i=0;i=10)ci+1=ci+1+ci/10;ci=ci%10;i=2*MAXLEN-1;while(ci=0 & i0) i=i-1;/跳过高位的跳过高位的0*len=i;POJ2389 参考程序int main()

10、int len;while(cinst1st2)for(i=0;iMAXLEN;i+)ai=0; bi=0;tran(st1,a);tran(st2,b);for(i=0;i=0;j-)coutcj;coutendl;return 0;大整数除法1、链接地址 http:/ 2、问题描述 求两个大的正整数相除的商输入数据 第1 行是测试数据的组数n，每组测试数据占2 行，第1 行是被除数，第2 行是除数。每组测试数据之间有一个空行，每行数据不超过100 个字符输出要求 n 行，每组测试数据有一行输出是相应的整数商问题描述问题描述输入样例324053373129633733590092604577

11、420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例01000000000000000000000000000000540965677509785089568705679

12、8068970934546546575676768678435435345 基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546 除以23 为例来看一下：开始商为0。先减去23 的100 倍，就是2300，发现够减3 次，余下646。于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用186 减去23，够减8 次，因此最终商就是328。 所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。 计算除数的10 倍、100 倍的时候，不用做乘法，直接在除数后

13、面补0 即可。解题思路解题思路参考程序参考程序n#include n#include n#define MAX_LEN 200nchar szLine1MAX_LEN + 10;nchar szLine2MAX_LEN + 10;nint an1MAX_LEN + 10; /被除数被除数, an10对应于个位对应于个位nint an2MAX_LEN + 10; /除数除数, an20对应于个位对应于个位nint aResultMAX_LEN + 10; /存放商，存放商，aResult0对应于个位对应于个位n/长度为长度为 nLen1 的大整数的大整数p1 减去长度为减去长度为nLen2 的大

14、整数的大整数p2n/结果放在结果放在p1 里，返回值代表结果的长度里，返回值代表结果的长度n/如不够减返回如不够减返回-1，正好减完返回，正好减完返回 0nint Substract( int * p1, int * p2, int nLen1, int nLen2)nn int i;n if( nLen1 = 0; i - ) n n if( p1i p2i ) break; /p1p2n else if( p1i p2i ) return -1; /p1p2n n n for( i = 0; i =nLen2 时，时，p2i 0n p1i -= p2i; n if( p1i = 0 ; i

15、- )n if( p1i )/找到最高位第一个不为找到最高位第一个不为0n return i + 1;n return 0;/全部为全部为0，说明两者相等，说明两者相等n参考程序参考程序nint main()nn int t, n;n cinn;n for( t = 0; t szLine1;n cin szLine2;n int i, j;n int nLen1 = strlen( szLine1);n memset( an1, 0, sizeof(an1);n memset( an2, 0, sizeof(an2);n memset( aResult, 0, sizeof(aResult)

16、;n for( j = 0, i = nLen1 - 1;i = 0 ; i -)n an1j+ = szLine1i - 0;n int nLen2 = strlen(szLine2);n for( j = 0, i = nLen2 - 1;i = 0 ; i -)n an2j+ = szLine2i - 0;n if( nLen1 nLen2 ) n n cout 0)n n for( i = nLen1 -1; i = nTimes; i - ) n an2i = an2i-nTimes;/朝高位移动朝高位移动n for( ; i = 0; i-)/低位补低位补0n an2i = 0;n

17、 nLen2 = nLen1;n n for( j = 0 ; j = 0) n n nLen1 = nTmp;n aResultnTimes-j+; /每成功减一次，则将商的相应位加每成功减一次，则将商的相应位加1n n 参考程序参考程序n /下面输出结果，先跳过高位下面输出结果，先跳过高位0n for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - );n if( i = 0)n for( ; i=0; i-)n cout aResulti;n elsen cout0;n coutendl;n n return 0;n课堂练习-八进制小数 链接：链

18、接：http:/poj.org/problem?id=1131描述描述 八进制小数可以用十进制小数精确的表示。比如，八进制里面的八进制小数可以用十进制小数精确的表示。比如，八进制里面的0.75等等于十进制里面的于十进制里面的0.963125 (7/8 + 5/64)。所有小数点后位数为。所有小数点后位数为n的八进制的八进制小数都可以表示成小数点后位数不多于小数都可以表示成小数点后位数不多于3n的十进制小数。的十进制小数。你的任务是写一个程序，把你的任务是写一个程序，把(0, 1)中的八进制小数转化成十进制小数。中的八进制小数转化成十进制小数。 输入输入 输入包括若干八进制小数，每个小数占用一行

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