ACM暑期培训

高精度运算理学院计算机系姚娟计算机能做的和不能做的•计算机的限制：精度、范围(int：-2^31~2^31-1,即-2147483648~2147483647)•计算机：突破了人的运算速度极限–对运算的数据进行了“合理”的假设•要解决假设之外的事情，它们的数量不多、但常常极其重大。比如中国的粮食安全问题：–13亿人口、人均需要多少–多少耕地、亩产多少、上年余积多少–……大整数加法1、链接地址=15032、问题描述–求不多于100个不超过100位的非负整数的之和。输入数据–有n行（n=101），前n-1行，每行是一个不超过100位的非负整数，最后一行0表示输入结束。输出数据–1行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678900输出样例370370367037037036703703703670大整数加法(POJ1503)解题思路•用字符型或整型数组来存放大整数–an[0]存放个位数，an[1]存放十位数，an[2]存放百位数……•模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。–unsignedan1[101]保存第一个数，用unsignedan2[100]表示第二个数，然后逐位相加，相加的结果直接存放在an1中。要注意处理进位。–为什么？an1数组长度定为101–数组定义稍微大点例如：189+23运算过程那么从左到右189981+023320+212212从左到右计算的好处：最高位加法进位时，只需往后面加1位；假如依旧从右到左进行加法，那么最后需要进位是需要把后面的数字都往后移一位，比较难以复杂和掌握。POJ1503参考程序voidaddition(intan1[],intan2[],int&len1,intlen2){intcheck(int*,int);inti,len,c=0;len=len1len2?len1:len2;for(i=len1;ilen+1;i++)an1[i]=0;//缺位前导补0for(i=len2;ilen+1;i++)an2[i]=0;for(i=0;ilen;i++)an1[i]=an1[i]+an2[i];len1=check(an1,len);}POJ1503参考程序//归整intcheck(int*a,intn){intk=0,len=n;while(a[len-1]==0&&len1)//去掉前导数字0，确定数组当前长度len--;for(k=0;klen;k++){if(a[k]=10){a[k+1]=a[k+1]+a[k]/10;//对数值超过9的位进行归整处理a[k]=a[k]%10;}}if(a[k]!=0)len=k+1;//确定数组的最终长度returnlen;}POJ1503参考程序intmain(){charszLine[MAXLEN+10];intan1[MAXLEN+10],an2[MAXLEN+10];intk=0,i,j=0;intlen1,len2;an1[0]=0;len1=1;while(1){cinszLine;if(szLine[0]=='0')break;len2=strlen(szLine);for(i=len2-1,j=0;i=0;i--)an2[j++]=szLine[i]-'0';addition(an1,an2,len1,len2);}for(i=len1-1;i=0;i--)coutan1[i];return0;}大整数乘法1、链接地址=23892、问题描述–求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例1234567890098765432100输出样例1219326311126352690000大整数乘法(POJ2389)解题思路•在程序中，用unsignedan1[200]和unsignedan2[200]分别存放两个乘数，用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200位的数相乘，积最多会有400位。an1[0],an2[0],aResult[0]都表示个位。•计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。•现以835×49为例来说明程序的计算过程。先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，结果如下：大整数乘法(POJ2389)解题思路接下来算4×5。此处4×5的结果代表20个10，因此要c[1]+=20，变为：再下来算4×3。此处4×3的结果代表12个100，因此要c[2]+=12，变为：大整数乘法(POJ2389)解题思路最后算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位上。这里i,j都是从右往左，从0开始数。POJ2389参考程序#includeiostream#includestringusingnamespacestd;constintMAXLEN=200+10;inta[MAXLEN],b[MAXLEN];intc[2*MAXLEN];stringst1,st2;inti,j,k;//字符串s转换为整型数组tvoidtran(strings,int*t){intm,l;l=s.length();for(m=0;ml;m++)t[m]=s[l-1-m]-'0';}POJ2389参考程序//乘法：输入用字符串表示的长整数m1、m2//返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组cvoidmul(int*m1,int*m2,int*len){inti,j;for(i=0;iMAXLEN;i++)//用第二个数乘以第一个数,每次一位for(j=0;jMAXLEN;j++)c[i+j]=c[i+j]+a[i]*b[j];//先乘起来,后面统一进位for(i=0;iMAXLEN*2-1;i++)//循环统一处理进位问题if(c[i]=10){c[i+1]=c[i+1]+c[i]/10;c[i]=c[i]%10;}i=2*MAXLEN-1;while(c[i]==0&&i0)i=i-1;//跳过高位的0*len=i;}POJ2389参考程序intmain(){intlen;while(cinst1st2){for(i=0;iMAXLEN;i++){a[i]=0;b[i]=0;}tran(st1,a);tran(st2,b);for(i=0;i2*MAXLEN;i++)c[i]=0;mul(a,b,&len);for(j=len;j=0;j--)coutc[j];coutendl;}return0;}大整数除法1、链接地址=27372、问题描述–求两个大的正整数相除的商输入数据第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符输出要求n行，每组测试数据有一行输出是相应的整数商问题描述输入样例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345•基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。•所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。解题思路参考程序#includeiostream.h#includestring.h#defineMAX_LEN200charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intan1[MAX_LEN+10];//被除数,an1[0]对应于个位intan2[MAX_LEN+10];//除数,an2[0]对应于个位intaResult[MAX_LEN+10];//存放商，aResult[0]对应于个位//长度为nLen1的大整数p1减去长度为nLen2的大整数p2//结果放在p1里，返回值代表结果的长度//如不够减返回-1，正好减完返回0intSubstract(int*p1,int*p2,intnLen1,intnLen2){inti;if(nLen1nLen2)return-1;4、参考程序//下面判断p1是否比p2大，如果不是，返回-1if(nLen1==nLen2){for(i=nLen1-1;i=0;i--){if(p1[i]p2[i])break;//p1p2elseif(p1[i]p2[i])return-1;//p1p2}}for(i=0;inLen1;i++){//要求调用本函数确保当i=nLen2时，p2[i]＝0p1[i]-=p2[i];if(p1[i]0){p1[i]+=10;p1[i+1]--;}}for(i=nLen1-1;i=0;i--)if(p1[i])//找到最高位第一个不为0returni+1;return0;//全部为0，说明两者相等}参考程序intmain(){intt,n;cinn;for(t=0;tn;t++){cinszLine1;cinszLine2;inti,j;intnLen1=strlen(szLine1);memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));memset(aResult,0,sizeof(aResult));for(j=0,i=nLen1-1;i=0;i--)an1[j++]=szLine1[i]-'0';intnLen2=strlen(szLine2);fo