ACM培训第十一讲-大数运算课件

ACM程序设计第十一讲-大数运算湖南工学院张新玉[e-mail]各类型的范围•int（16位）-32768～32767（注：现在大多数的编译器的int型是32位的也就是说跟long型的大小一样）•longlong或__int64（64位）-9223372036854775808～9223372036854775807•float（32位）精确到小数点后6～7位•double（64位）精确到小数点后15～16位（注：平时做题时都把浮点型数据定义为double型避免精度不够出错）请计算：1、2的1000次幂2、2的10000次幂3、123456789012345678912345678903453434534534535345434543乘上93874293874928734928734028034820938479288374892733453453534主要内容数字存储的实现1加法运算的实现2减法运算的实现3乘法运算的实现4除法运算的实现5幂运算的实现6数字存储的实现•大数计算的因数和结果精度一般是少则数十位，多则几万位。在C/C++语言中定义的类型中精度最多只有二十多位。一般我们称这种基本数据类型无法表示的整数为大整数。如何表示和存放大整数呢？基本的思想就是：用数组存放和表示大整数。一个数组元素，存放大整数中的一位。比如：166443431801234567891664434318下标加法运算的实现99876543201664434300加数被加数+初始化进位为0，各对应位相加后再加上进位数1、进位为102、进位为163、进位为154、进位为12由低位向高位相加计算，直至所有运算结束应注意问题：1.判断最后数组的长度.2.去掉前导零大数加法voidAdd(chars1[],chars2[])//参数为两个字符串数组{intnum1[M],num2[M];inti,j;len1=strlen(s1);len2=strlen(s2);for(i=len1-1,j=0;i=0;i--)//num1[0]保存的是低位num1[j++]=s1[i]-'0';for(i=len2-1,j=0;i=0;i--)num2[j++]=s2[i]-'0';for(i=0;iM;i++){num1[i]+=num2[i];if(num1[i]9){num1[i]-=10;num1[i+1]++;}}for(i=M-1;(i=0)&&(num1[i]==0);i--);//找到第一个不是0的数的位置if(i=0)//从高位到低位输出每个数for(;i=0;i--)printf(%d,num1[i]);elseprintf(0\n);}减法运算的实现算法也是从低位开始减。先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两数位数长度相等时，最好比那一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。减法运算的实现76876543208975434320减数被减数-初始化借位为0，各对应位相减后再减上借位数1、借位为192、借位为163、借位为004、借位为02由低位向高位相加计算，直至所有运算结束处理中注意问题：1如果被减数大于减数时，交换两个数再相减，最后加个“-”号即可2结果可能会出现前面是一堆0的情况，要处理好，如当减数为112，而被减数为111时，会出现001乘法运算的实现•首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加。得出最后结果。•计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。•ans[i+j]=a[i]*b[j];现以835×49为例来说明程序的计算过。1.先算835×9。5×9得到45个1，3×9得到27个10，8×9得到72个100。由于不急于处理进位，所以835×9算完后，aResult如下：2.接下来算4×5。此处4×5的结果代表20个10，因此要aResult[1]+=20，变为：1.再下来算4×3。此处4×3的结果代表12个100，因此要aResult[2]+=12，变为：2.最后算4×8。此处4×8的结果代表32个1000，因此要aResult[3]+=32，变为：1.乘法过程完毕。接下来从aResult[0]开始向高位逐位处理进位问题。aResult[0]留下5，把4加到aResult[1]上，aResult[1]变为51后，应留下1，把5加到aResult[2]上……最终使得aResult里的每个元素都是1位数，结果就算出来了：•总结一个规律:即一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第i+j位上。这里i,j都是从右往左，从0开始数。•ans[i+j]=a[i]*b[j];处理中注意问题：1另外进位时要处理，当前的值加上进位的值再看本位数字是否又有进位；前导清零。大数乘法voidMulti(charstr1[],charstr2[]){intlen1,len2,i,j;inta[MAX+10],b[MAX+10],c[MAX*2+10];memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));len1=strlen(str1);for(j=0,i=len1-1;i=0;i--)//把数字倒过来a[j++]=str1[i]-'0';len2=strlen(str2);for(j=0,i=len2-1;i=0;i--)//倒转第二个整数b[j++]=str2[i]-'0';for(i=0;ilen2;i++)//用第二个数乘以第一个数,每次一位for(j=0;jlen1;j++)c[i+j]+=b[i]*a[j];//先乘起来,后面统一进位for(i=0;iMAX*2;i++)//循环统一处理进位问题if(c[i]=10){c[i+1]+=c[i]/10;c[i]%=10;}for(i=MAX*2;(c[i]==0)&&(i=0);i--);//跳过高位的0if(i=0)for(;i=0;i--)printf(%d,c[i]);elseprintf(0);pritnf(\n);}除法运算的实现首先说一下我们所要的结果，当除数除不开被除数时，不用除到小数，当除数小于被除数时，除数作为余数既可，不用再向下除了。基本思路•基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。大数除法幂运算的实现•幂的实现是最为简单的了，因为有了前面的算法做铺垫，就是调用乘法函数，来循环去自乘，幂指数相应减1，直到幂指数变为0时结束。相关习题基础题：1042，1047，1060，1087进阶题：1937，5351，5435