acm暑期培训.ppt

高精度运算 理学院计算机系 姚娟 计算机能做的和不能做的 计算机的限制：精度、范围(int： -2^31 ~ 2^31-1, 即 -2 147 483 648 ~ 2 147 483 647) 计算机：突破了人的运算速度极限 对运算的数据进行了“合理”的假设 要解决假设之外的事情，它们的数量不多、但常常极其重大。比如中国的粮食安全问题： 13亿人口、人均需要多少 多少耕地、亩产多少、上年余积多少 …… 大整数加法 1、链接地址 /problem?id=1503 2、问题描述 求不多于100个不超过100 位的非负整数的之和。 输入数据 有n行（n=101），前n-1行，每行是一个不超过100 位的非负整数，最后一行0表示输入结束。 输出数据 1行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 输入样例 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 0 输出样例 370370367037037036703703703670 大整数加法 (POJ1503) 解题思路 用字符型或整型数组来存放大整数 an[0]存放个位数，an[1]存放十位数，an[2]存放百位数…… 模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。 unsigned an1[101]保存第一个数，用unsigned an2[100]表示第二个数，然后逐位相加，相加的结果直接存放在an1中。要注意处理进位。 为什么 ？an1 数组长度定为101 数组定义稍微大点 POJ1503 参考程序 void addition(int an1[],int an2[],int len1,int len2) { int check(int *,int); int i,len,c=0; len=len1len2?len1:len2; for(i=len1;ilen+1;i++) an1[i]=0; //缺位前导补0 for(i=len2;ilen+1;i++) an2[i]=0; for(i=0;ilen;i++) an1[i]=an1[i]+an2[i]; len1=check(an1,len); } POJ1503 参考程序 //归整 int check(int *a,int n) { int k=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; //确定数组的最终长度 return len; } POJ1503 参考程序 int main() { char szLine[MAXLEN+10]; int an1[MAXLEN+10],an2[MAXLEN+10]; int k=0,i,j=0; int len1,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]; return 0; } 大整数乘法 1、链接地址 /problem?id=2389 2、问题描述 求两个不超过200 位的非负整数的积。输入数据有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 输入样例 12345678900 98765432100 输出样例 1219326311126352690000 大整数乘法(POJ2389) 解题思路 在程序中，用unsigned an1[200]和unsigned an2[200]分别存放两个乘数，用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200 位的数相乘，积最多会有400 位。an1[