高精度计算

高精度计算Four本讲主要内容•例题：ai2981大整数加法•例题：ai2736大整数减法•例题：ai2980大整数乘法•例题：ai2737大整数除法•例题：ai2952循环数C/C++中数的表示范围•int：-2^31~2^31-1,即-2147483648~2147483647•unsigned：0~2^32-1,即0~4294967295如何处理一个200位的整数？•double：64位如何精确到小数点后100位？用数组来存放和表示，一个数组元素存放大整数的一位。例题：ai2981大整数加法•问题描述求两个不超过200位的非负整数的和。•输入数据–有两行，每行是一个不超过200位的非负整数，没有多余的前导0。•输出要求一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。•输入样例2222222222222222222233333333333333333333•输出样例55555555555555555555例题：ai2981大整数加法解题思路1)用字符型或整型数组来存放大整数an[0]存放个位数，an[1]存放十位数，an[2]存放百位数……2）模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。用intan1[201]保存第一个数，用intan2[200]表示第二个数，然后逐位相加，相加的结果直接存放在an1中。要注意处理进位。#includestdio.h#includestring.h#defineMAX_LEN201intan1[MAX_LEN+10];intan2[MAX_LEN+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intAdd(intnMaxLen,int*an1,int*an2)//将长度最多为nMaxLen的大整数an1和an2相加，结果放在an1,//an1[0],an2[0]对应于个位，返回值为最高位数{intnHighestPos=0;for(inti=0;inMaxLen;i++){an1[i]+=an2[i];//逐位相加if(an1[i]=10){//看是否要进位an1[i]-=10;an1[i+1]++;//进位}if(an1[i])nHighestPos=i;//记录最高位的位置}returnnHighestPos;}intmain(){scanf(%s,szLine1);scanf(%s,szLine2);//库函数memset将地址an1开始的sizeof(an1)字节内容置成0//sizeof(an1)的值就是an1的长度，memset函数在string.h中声明memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));//下面将szLine1中存储的字符串形式的整数转换到an1中去，//an1[0]对应于个位inti,j;intnLen1=strlen(szLine1);j=0;for(i=nLen1-1;i=0;i--){an1[j]=szLine1[i]-'0';j++;}intnLen2=strlen(szLine2);j=0;for(i=nLen2-1;i=0;i--)an2[j++]=szLine2[i]-'0';intnHighestPos=Add(MAX_LEN,an1,an2);for(i=nHighestPos;i=0;i--)printf(%d,an1[i]);return0;}例题：ai2736大整数减法问题描述求2个大的正整数相减的差输入数据第1行是测试数据的组数n，每组测试数据占2行，第1行是被减数a，第2行是减数b(ab)。每组测试数据之间有一个空行，每行数据不超过100个字符输出要求n行，每组测试数据有一行输出是相应的整数差例题：ai2736大整数减法输入样例29999999999999999999999999999999999999999999999999954096567750978508956870567980689709345465465756767686784354353451输出样例99999999999999999999999900000000000005409656775097850895687056798068970934546546575676768678435435344#includestdio.h#includestring.h#defineMAX_LEN110intan1[MAX_LEN];intan2[MAX_LEN];charszLine1[MAX_LEN];charszLine2[MAX_LEN];intSubstract(intnMaxLen,int*an1,int*an2){//两个最多nMaxLen位的大整数an1减去an2,an1保证大于an2intnStartPos=0;for(inti=0;inMaxLen;i++){an1[i]-=an2[i];//逐位减if(an1[i]0){//看是否要借位an1[i]+=10;an1[i+1]--;//借位}if(an1[i])nStartPos=i;//记录最高位的位置}returnnStartPos;//返回值是结果里面最高位的位置}intmain(){intn;scanf(%d,&n);while(n--){scanf(%s,szLine1);scanf(%s,szLine2);inti,j;memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));//下面将szLine1中存储的字符串形式的整数转换到an1中去，//an1[0]对应于个位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';intnStartPos=Substract(MAX_LEN,an1,an2);for(i=nStartPos;i=0;i--)printf(%d,an1[i]);printf(\n);}return0;}例题：ai2980大整数乘法问题描述求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例1234567890098765432100输出样例1219326311126352690000解题思路用unsignedan1[200]和unsignedan2[200]分别存放两个乘数，用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200位的数相乘，积最多会有400位。an1[0],an2[0],aResult[0]都表示个位。一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第i+j位上。这里i,j都是从右往左，从0开始数。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。现以835×49为例来说明程序的计算过程。先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，aResult如下：接下来算5×4。此处5×4的结果代表20个10，因此要aResult[1]+=20，变为：再下来算3×4。此处3×4的结果代表12个100，因此要aResult[2]+=12，变为：最后算8×4。此处8×4的结果代表32个1000，因此要aResult[3]+=32，变为：835×49乘法过程完毕。接下来从aResult[0]开始向高位逐位处理进位问题。835×49aResult[0]留下5，把4加到aResult[1]上，aResult[1]变为51后，应留下1，把5加到aResult[2]上……最终使得aResult里的每个元素都是1位数，结果就算出来了：#includestdio.h#includestring.h#defineMAX_LEN200unsignedan1[MAX_LEN+10];unsignedan2[MAX_LEN+10];unsignedaResult[MAX_LEN*2+10];charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intmain(){gets(szLine1);//gets函数读取一行gets(szLine2);inti,j;memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));memset(aResult,0,sizeof(aResult));intnLen1=strlen(szLine1);j=0;for(i=nLen1-1;i=0;i--)an1[j++]=szLine1[i]-'0';intnLen2=strlen(szLine2);j=0;for(i=nLen2-1;i=0;i--)an2[j++]=szLine2[i]-'0';//每一轮都用an2的一位，去和an1各位相乘，从an2的个位开始for(i=0;inLen2;i++){for(j=0;jnLen1;j++)//两数第i,j位相乘，累加到结果的第i+j位aResult[i+j]+=an2[i]*an1[j];}//下面的循环统一处理进位问题intnHighestPos=0;for(i=0;iMAX_LEN*2;i++){if(aResult[i]=10){aResult[i+1]+=aResult[i]/10;aResult[i]%=10;}if(aResult[i])nHighestPos=i;}for(i=nHighestPos;i=0;i--)printf(%d,aResult[i]);return0;}求2个大的正整数相除的商Input第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符Outputn行，每组测试数据有一行输出是相应的整数商例题：ai2737大整数除法SampleInput324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451SampleOutput010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345例题：ai2737大整数除法求两个大的正整数相除的商基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，