《高精度与字符串》PPT课件

《《高精度与字符串》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲人：张波ID：AC_mm信息工程学院ACM团队高精度运算字符串AND主要内容：高精度加法高精度乘法字符串中空格的处理字符串处理函数高精度篇C/C++中的int类型能表示的范围是：-2^31到2^31-1;unsigned类型能表示的范围是：0到2^32-1;即：0-4294967295所以int和unsigned类型变量，都不能保存超过10位的整数。又如longlong和__int64能表示的范围是：-2^63到2^63-1即：-9223372036854775808到9223372036854775807所以即便是longlong和_

2、_int64最多也只能保存19位的数字。有时我们需要参与运算的数，可能会远远不止10位或19位。例如，可能需要保留小数点后面100位（比如pi值）。那么，即便使用能表示很大数值范围的double变量（double变量只有64位），仍然不能到达精确到小数点后面100位这样的精度。一般我们称这种基本数据类型无法表示的整数为大整数。那么如何表示和存放大整数呢？基本思想就是：用数组存放和表示大整数。一个数组元素存放大整数中的一位。那么，如何解决类似大整数这样的高精度计算问题呢？这就是我们今天学习的内容。例题1分析首先给一个最简单的例子。问题描述：求

3、两个不超过200位的正整数的和。输入数据：有两行，每行是一个不超过200位的正整数，并且没有多余的前导0.输出要求：输出相加后的结果。结果里面不能有多余的前导0，即如果结果是342，那么就不能输出0342。例题1分析例题1分析输入样例：2222222222222222222233333333333333333333输出样例：55555555555555555555例题1分析首先要解决的就是存储200位整数的问题。显然，任何C/C++固有类型的变量都无法保存它。最直观的想法就是可以用一个字符串来保存它。字符串本质上就是一个字符数组，因此为了编

4、程更方便，我们也可以用数组A[200]来保存一个200位的整数。例题1分析让A[0]存放个位数，A[1]存放十位数，A[2]存放百位数，依次类推。。那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。比如计算4567+91354567+9135-------------------=136912=136912----------------------=136102----------------------=13702----------------------=13702现在我

5、们来写例题1的代码。首先开2个数组来保存2个大数分别为数组A[210],B[210];然后再开一个数组ans[210]来保存相加的结果。这里为了让大家更容易理解，我们最后统一进位。例题1分析1#include2#include3#defineM2104intmain()5{6charstr1[M],str2[M];7intA[M],B[M],ans[M],i,j;8while(scanf("%s%s",str1,str2)!=EOF)9{10memset(A,0,sizeof(A));11memset(

6、B,0,sizeof(B));12memset(ans,0,sizeof(ans));13intlen1=strlen(str1);14intlen2=strlen(str2);15for(j=0,i=len1-1;i>=0;i--)16A[j++]=str1[i]-'0';17for(j=0,i=len2-1;i>=0;i--)18B[j++]=str2[i]-'0';19for(i=0;i=10)24{25ans[i+1

7、]+=ans[i]/10;26ans[i]%=10;27}28}29for(i=M-1;i>=0;i--)30if(ans[i])break;31for(j=i;j>=0;j--)32printf("%d",ans[j]);33printf("");34}35return0;36}高精度乘法例题2：题目描述：计算2个不超过40位的正整数的积.输入数据：输入为2行,每一行代表一个数输出数据：输出一行,为2个数的乘积.高精度乘法输入样例：111111111111111111111111输出样例：1234567901111098765432

8、1例题2分析有了刚才的高精度加法，现在我们应该比较容易想到怎样处理。我们用一个简单的例子来推断。我们来模拟835*49的过程。这个过程和小学生列竖式做乘法相同。83549----