您好,欢迎访问三七文档
1、高精度计算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、数……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;//记录最高位的位置}returnnHighe。
3、stPos;}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大整数减法问题描。
4、述求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,in。
5、t*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(szLi。
6、ne2);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位。
7、相乘所得的数,一定是要累加到结果的第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。
8、#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;jnL。
9、en1;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大整数除法SampleInput324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931。
10、160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451SampleOutput010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345例题:ai2737大整数除法求两个大的正整数相除的商基本的思想是反复做减法,看看从被除数里最多能减去多少个除数,商就是多少。一个一个减显然太慢,如何减得更快一些呢?以7546除以23为例来看一下:开始商为0。先减去23的100倍,就是2300,发现够减3次,余下646。于是商的值就增加300。然后用646减去230,发现够减2次,余下186,于是商的值增加20。最后用186减去23,够减8次,。
本文标题:高精度计算
链接地址:https://www.777doc.com/doc-3144039 .html