ACM高精度计算

第九讲高精度计算ACM算法与程序设计2/33大整数加法1、链接地址=29812、问题描述求两个不超过200位的非负整数的和。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。3/33问题描述输出要求一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例2222222222222222222233333333333333333333输出样例OutputSample:555555555555555555554/33首先要解决的就是存储200位整数的问题。显然，任何C/C++固有类型的变量都无法保存它。最直观的想法是可以用一个字符串来保存它。字符串本质上就是一个字符数组，因此为了编程更方便，我们也可以用数组unsignedan[200]来保存一个200位的整数，让an[0]存放个位数，an[1]存放十位数，an[2]存放百位数……那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。也就是说，用unsignedan1[201]保存第一个数，用unsignedan2[200]表示第二个数，然后逐位相加，相加的结果直接存放在an1中。要注意处理进位。另外，an1数组长度定为201，是因为两个200位整数相加，结果可能会有201位。实际编程时，不一定要费心思去把数组大小定得正好合适，稍微开大点也无所谓，以免不小心没有算准这个“正好合适”的数值，而导致数组小了，产生越界错误。3、解题思路5/334、参考程序#includestdio.h#includestring.h#defineMAX_LEN200intan1[MAX_LEN+10];intan2[MAX_LEN+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intmain(void){scanf(%s,szLine1);scanf(%s,szLine2);inti,j;memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));6/334、参考程序intnLen1=strlen(szLine1);for(j=0,i=nLen1-1;i=0;i--)an1[j++]=szLine1[i]-'0';intnLen2=strlen(szLine2);for(j=0,i=nLen2-1;i=0;i--)an2[j++]=szLine2[i]-'0';for(i=0;iMAX_LEN;i++){an1[i]+=an2[i];//逐位相加if(an1[i]=10){//看是否要进位an1[i]-=10;an1[i+1]++;//进位}}for(i=MAX_LEN;(i=0)&&(an1[i]==0);i--);if(i=0)for(;i=0;i--)printf(%d,an1[i]);elseprintf(0);return0;}7/33大整数乘法1、链接地址=29802、问题描述求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。8/33问题描述输入样例1234567890098765432100输出样例12193263111263526900009/33在程序中，用unsignedan1[200]和unsignedan2[200]分别存放两个乘数，用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200位的数相乘，积最多会有400位。an1[0],an2[0],aResult[0]都表示个位。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。现以835×49为例来说明程序的计算过程。3、解题思路10/33先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，结果如下：3、解题思路接下来算4×5。此处4×5的结果代表20个10，因此要c[1]+=20，变为：再下来算4×3。此处4×3的结果代表12个100，因此要c[2]+=12，变为：11/333、解题思路最后算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开始数。12/334、参考程序#includestdio.h#includestring.h#defineMAX_LEN200intmain(void){inti,j;intlen1,len2;inta[MAX_LEN+10],b[MAX_LEN+10],c[MAX_LEN*2+10];charstr1[MAX_LEN+10],str2[MAX_LEN+10];for(i=0;iMAX_LEN+10;i++)a[i]=b[i]=0;for(i=0;iMAX_LEN*2+10;i++)c[i]=0;gets(str1);//按字符串形式读入第一个整数gets(str2);len1=strlen(str1);for(j=0,i=len1-1;i=0;i--)//把数字倒过来a[j++]=str1[i]-'0';len2=strlen(str2);for(j=0,i=len2-1;i=0;i--)//倒转第二个整数b[j++]=str2[i]-'0';13/334、参考程序for(i=0;ilen2;i++)//用第二个数乘以第一个数,每次一位{for(j=0;jlen1;j++)c[i+j]+=b[i]*a[j];//先乘起来,后面统一进位}for(i=0;iMAX_LEN*2;i++)//循环统一处理进位问题{if(c[i]=10){c[i+1]+=c[i]/10;c[i]%=10;}}for(i=MAX_LEN*2;(c[i]==0)&&(i=0);i--);//跳过高位的0if(i=0)for(;i=0;i--)printf(%d,c[i]);elseprintf(0);return0;}14/33大整数除法1、链接地址=27372、问题描述求两个大的正整数相除的商输入数据第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符输出要求n行，每组测试数据有一行输出是相应的整数商15/33问题描述输入样例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例01000000000000000000000000000000540965677509785089568705679806897093454654657567676867843543534516/33基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。3、解题思路17/334、参考程序#includestdio.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;18/334、参考程序//下面判断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，说明两者相等}19/334、参考程序intmain(){intt,n;scanf(%d,&n);for(t=0;tn;t++){scanf(%s,szLine1);scanf(%s,szLine2);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);for(j=0,i=nLen2-1;i=0;i--)an2[j++]=szLine2[i]-'0';if(nLen1nLen2){printf(0\n);continue;}20/334、参考程序intnTimes=nLen1-nLen2;if(nTimes0){for(i=nLen1-1;i=nTimes;i--)an2[i]=an2[i-nTimes];//朝高位移动for(;i=0;i--)//低位补0an2[i]=0;nLen2=nLen1;}for(j=0;j=nTimes;j++){intnTmp;//一直减到不够减为止//先减去若干个an2