7第七章 高精度计算.ppt

《7第七章 高精度计算.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高精度计算北大李文新《在线程序设计….》第七章基本类型的表示范围大整数加法大整数减法大整数乘法基本类型的表示范围int类型32位：能表示的十进制数不超过10位double类型64位有效数字15-16位如果需要100位甚至1000位整数，或要求精确到小数点后100位，如何解决？用数组存储，模拟手工计算我们一般称这种基本类型无法表示的整数为大整数7.1例题：大整数加法问题描述求两个不超过200位的非负整数的和。输入数据有两行，每行是一个不超过200位的非负整，没有多余的前导0。输出要求一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。输入样例222

2、2222222222222222233333333333333333333输出样例55555555555555555555解题思路首先要解决的就是存储200位整数的问题。显然，任何C/C++固有类型的变量都无法保存它。最直观的想法是可以用一个字符串来保存它。用str[200]来保存一个200位的整数，让str[0]存放个位数，str[1]存放十位数，str[2]存放百位数……那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。大整数加法_实现过程voidadd(charstr_a[N],charstr_b[N],charstr_

3、c[N]){（1）把str_a,str_b的各位转变成对应整数，个位从下标0开始存入a,b（2）用变量len_a,len_b分别存储a,b中最高位的下标（3）从低位到高位，对应位相加，左对齐存入c,注意进位（4）把c转化为字符串str_c}（1）把str_a,str_b的各位转变成对应整数，个位从下标0开始存入a[],b[](1)将str_a复制给a;将str_b复制给b;(2)将a,b逆转(3)将a,b的每个元素都由字符变成对应整数a[i]是字符，a[i]-48或a[i]=‘0’为其对应整数（1）把str_a,str_b的各位转变成对应整数，个位从下标0开始存入a[],b[](1)st

4、rcpy(a,str_a);strcpy(b,str_b);(2)strrev(a);strrev(b);(3)for(i=0;str[i]!=‘’;i++)a[i]=a[i]-’0’;for(i=0;str[i]!=‘’;i++)b[i]=b[i]-’0’;（2）用变量len_a,len_b分别存储a,b中最高位的下标Len_a=strlen(str_a);Len_b=strlen(str_b);(3)从低位到高位，对应位相加，左对齐存入c,注意进位4567938165432106543210carry0804190311(3)从低位到高位，对应位相加，左对齐存入c,注意进位(

5、1)求len_a,len_b的最大值存入len(2)进位carry初始化为0（3）for(i=0;i

6、若最高位有进位{c[i]=carry;i++;}len=i;for(i=0;ib（1）把str_a,str_b的各位转变成对应整数，个位从下标0开始存入a,b（2）用变量len_a,len_b分别存储a,b中最高

7、位的下标（3）从低位到高位，对应位相减，注意借位，注意去掉结果高位的0（4）把c转化为字符串str_c}(3)从低位到高位，对应位相减，注意借位938145676543210654321041831减去7,不够减，向高位借1,8-1=711-7=473减去5,不够减，向高位借1,9-1=813-5=88大数乘法问题描述求两个不超过200位的非负整数的积。输入数据有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求一