《acm暑期培训资料》由会员分享，可在线阅读，更多相关《acm暑期培训资料（28页珍藏版）》请在金锄头文库上搜索。
1、高精度运算,理学院计算机系 姚娟,计算机能做的和不能做的,计算机的限制：精度、范围(int： -231 231-1, 即 -2 147 483 648 2 147 483 647) 计算机：突破了人的运算速度极限 对运算的数据进行了“合理”的假设 要解决假设之外的事情，它们的数量不多、但常常极其重大。比如中国的粮食安全问题： 13亿人口、人均需要多少 多少耕地、亩产多少、上年余积多少 ,大整数加法,1、链接地址 http:/poj.org/problem?id=1503 2、问题描述 求不多于100个不超过100 位的非负整数的之和。 输入数据 有n行（n=101），前n-1行，每行是一个不超
2、过100 位的非负整数，最后一行0表示输入结束。 输出数据 1行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。,输入样例 123456789012345678901234567890 123456789012345678901234567890 123456789012345678901234567890 0 输出样例 370370367037037036703703703670,大整数加法 (POJ1503) 解题思路,用字符型或整型数组来存放大整数 an0存放个位数，an1存放十位数，an2存放百位数 模拟小学生列竖式做加法，从个位开始逐位相加，
3、超过或达到10则进位。 unsigned an1101保存第一个数，用unsigned an2100表示第二个数，然后逐位相加，相加的结果直接存放在an1中。要注意处理进位。 为什么 ？an1 数组长度定为101 数组定义稍微大点,从左到右计算的好处： 最高位加法进位时，只需往后面加1位；假如依旧从右到左进行加法，那么最后需要进位是需要把后面的数字都往后移一位，比较难以复杂和掌握。,POJ1503 参考程序,void addition(int an1,int an2,int ,POJ1503 参考程序,/归整 int check(int *a,int n) int k=0,len=n; whi
4、le(alen-1=0 ,POJ1503 参考程序,int main() char szLineMAXLEN+10; int an1MAXLEN+10,an2MAXLEN+10; int k=0,i,j=0; int len1,len2; an10=0; len1=1; while(1) cinszLine; if(szLine0=0) break; len2=strlen(szLine); for(i=len2-1,j=0;i=0; i-) an2j+ = szLinei - 0; addition(an1,an2,len1,len2); for(i=len1-1;i=0;i-) couta
5、n1i; return 0; ,大整数乘法,1、链接地址 http:/poj.org/problem?id=2389 2、问题描述 求两个不超过200 位的非负整数的积。输入数据有两行，每行是一个不超过200 位的非负整数，没有多余的前导0。输出要求一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。,输入样例 12345678900 98765432100 输出样例 1219326311126352690000,大整数乘法(POJ2389) 解题思路,在程序中，用unsigned an1200和unsigned an2200分别存放两个乘数，用aRe
6、sult400来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200 位的数相乘，积最多会有400 位。an10, an20, aResult0都表示个位。 计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。 现以 83549 为例来说明程序的计算过程。,先算8359。59 得到45 个1，39 得到27 个10，89 得到72 个100。由于不急于处理进位，所以8359 算完后，结果如下：,大整数乘法(POJ2389) 解题思路,接下来算45。此处45 的结果代表20 个10，因此要 c1+=20，变为
7、：,再下来算43。此处43 的结果代表12 个100，因此要 c2+= 12，变为：,大整数乘法(POJ2389) 解题思路,最后算 48。此处48 的结果代表 32 个1000，因此要 c3+= 32，变为：,乘法过程完毕。接下来从 c0开始向高位逐位处理进位问题。c0留下5，把4 加到c1上，c1变为51 后，应留下1，把5 加到c2上最终使得c 里的每个元素都是1 位数，结果就算出来了：,规律：一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i+j 位上。这里i, j 都是从右往左，从0 开始数。,POJ2389 参考程序,#include #include us
8、ing namespace std; const int MAXLEN=200+10; int aMAXLEN,bMAXLEN; int c2*MAXLEN; string st1,st2; int i,j,k; /字符串s转换为整型数组t void tran(string s,int *t) int m,l; l=s.length(); for(m=0;ml;m+) tm=sl-1-m-0; ,POJ2389 参考程序,/乘法：输入用字符串表示的长整数m1、m2 /返回一个表示两个数乘积长度的指针，及表示乘积的一个整型数组c void mul(int *m1,int *m2,int *len
9、) int i,j; for(i=0;i=10) ci+1=ci+1+ci/10; ci=ci%10; i=2*MAXLEN-1; while(ci=0 ,POJ2389 参考程序,int main() int len; while(cinst1st2) for(i=0;i=0;j-) coutcj; coutendl; return 0; ,大整数除法,1、链接地址 http:/ 2、问题描述 求两个大的正整数相除的商 输入数据 第1 行是测试数据的组数n，每组测试数据占2 行，第1 行是被除数，第2 行是除数。每组测试数据之间有一个空行，每行数据不超过100 个字符 输出要求 n 行，每组
10、测试数据有一行输出是相应的整数商,问题描述,输入样例 3 2405337312963373359009260457742057439230496493930355595797660791082739646 2987192585318701752584429931160870372907079248971095012509790550883793197894 10000000000000000000000000000000000000000 10000000000 5409656775097850895687056798068970934546546575676768678435435345 1
11、 输出样例 0 1000000000000000000000000000000 5409656775097850895687056798068970934546546575676768678435435345,基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546 除以23 为例来看一下：开始商为0。先减去23 的100 倍，就是2300，发现够减3 次，余下646。于是商的值就增加300。然后用646 减去230，发现够减2 次，余下186，于是商的值增加20。最后用186 减去23，够减8 次，因此最终商就是328。 所以
12、本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。 计算除数的10 倍、100 倍的时候，不用做乘法，直接在除数后面补0 即可。,解题思路,参考程序,#include #include #define MAX_LEN 200 char szLine1MAX_LEN + 10; char szLine2MAX_LEN + 10; int an1MAX_LEN + 10; /被除数, an10对应于个位 int an2MAX_LEN + 10; /除数, an20对应于个位 int aResultMAX_LEN + 10; /存放商，aResult0对应于个位 /长度为 nLe
13、n1 的大整数p1 减去长度为nLen2 的大整数p2 /结果放在p1 里，返回值代表结果的长度 /如不够减返回-1，正好减完返回 0 int Substract( int * p1, int * p2, int nLen1, int nLen2) int i; if( nLen1 nLen2 ) return -1;,4、参考程序,/下面判断p1 是否比p2 大，如果不是，返回-1 if( nLen1 = nLen2 ) for( i = nLen1-1; i = 0; i - ) if( p1i p2i ) break; /p1p2 else if( p1i =nLen2 时，p2i 0
14、p1i -= p2i; if( p1i = 0 ; i- ) if( p1i )/找到最高位第一个不为0 return i + 1; return 0;/全部为0，说明两者相等 ,参考程序,int main() int t, n; cinn; for( t = 0; t szLine1; cin szLine2; int i, j; int nLen1 = strlen( szLine1); memset( an1, 0, sizeof(an1); memset( an2, 0, sizeof(an2); memset( aResult, 0, sizeof(aResult); for( j
15、= 0, i = nLen1 - 1;i = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; if( nLen1 nLen2 ) cout“0n“; continue; ,参考程序,int nTimes = nLen1 - nLen2; if(nTimes 0) for( i = nLen1 -1; i = nTimes; i - ) an2i = an2i-nTimes;/朝高位移动 for( ; i = 0; i-)/低位补0 an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; /每成功减一次，则将商的相应位加1 ,参考程序,/下面输出结果，先跳过高位0 for( i = MAX_LEN ; (i = 0) ,课堂练习-八进制小数,链接：http:/poj.org/proble
