C语言超大数四则运算PPT课件.ppt

,超大数的四则运算,2,各类型的范围,int（16位）-3276832767（注：现在大多数的编译器的int型是32位的也就是说跟long型的大小一样）longlong或_int64（64位）-92233720368547758089223372036854775807float（32位）精确到小数点后67位double（64位）精确到小数点后1516位（注：平时做题时都把浮点型数据定义为double型避免精度不够出错）,3,请计算：1、2的1000次幂2、2的10000次幂3、123456789012345678912345678903453434534534535345434543乘上93874293874928734928734028034820938479288374892733453453534,4,主要内容,5,数字存储的实现,大数计算的因数和结果精度一般是少则数十位，多则几万位。在C/C+语言中定义的类型中精度最多只有二十多位。一般我们称这种基本数据类型无法表示的整数为大整数。如何表示和存放大整数呢？基本的思想就是：用数组存放和表示大整数。一个数组元素，存放大整数中的一位。比如：1664434318,下标,6,加法运算的实现,加数,被加数,+,初始化进位为0，各对应位相加后再加上进位数,1、进位为1,0,3、进位为1,5,4、进位为1,2,由低位向高位相加计算，直至所有运算结束,7,理中注意问题：,判断最后数组的长度.去掉前导零,8,大数加法,voidAdd(chars1,chars2)/参数为两个字符串数组intnum1M,num2M;inti,j;len1=strlen(s1);len2=strlen(s2);for(i=len1-1,j=0;i=0;i-)/num10保存的是低位num1j+=s1i-0;for(i=len2-1,j=0;i=0;i-)num2j+=s2i-0;for(i=0;i9)num1i-=10;num1i+1+;,9,for(i=M-1;(i=0),10,减法运算的实现,算法也是从低位开始减。先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两数位数长度相等时，最好比那一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。,11,减法运算的实现,减数,被减数,-,初始化借位为0，各对应位相减后再减上借位数,1、借位为1,9,2、借位为1,6,3、借位为0,0,4、借位为0,2,由低位向高位相加计算，直至所有运算结束,12,处理中注意问题：,13,乘法运算的实现,首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加。得出最后结果。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。ansi+j=ai*bj;,14,现以83549为例来说明程序的计算过。,先算8359。59得到45个1，39得到27个10，89得到72个100。由于不急于处理进位，所以8359算完后，aResult如下：接下来算45。此处45的结果代表20个10，因此要aResult1+=20，变为：,15,再下来算43。此处43的结果代表12个100，因此要aResult2+=12，变为：最后算48。此处48的结果代表32个1000，因此要aResult3+=32，变为：,16,乘法过程完毕。接下来从aResult0开始向高位逐位处理进位问题。aResult0留下5，把4加到aResult1上，aResult1变为51后，应留下1，把5加到aResult2上最终使得aResult里的每个元素都是1位数，结果就算出来了：,17,总结一个规律:即一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第i+j位上。这里i,j都是从右往左，从0开始数。ansi+j=ai*bj;,18,处理中注意问题：,19,大数乘法,voidMulti(charstr1,charstr2)intlen1,len2,i,j;intaMAX+10,bMAX+10,cMAX*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-)/把数字倒过来aj+=str1i-0;len2=strlen(str2);for(j=0,i=len2-1;i=0;i-)/倒转第二个整数bj+=str2i-0;for(i=0;ilen2;i+)/用第二个数乘以第一个数,每次一位for(j=0;jlen1;j+)ci+j+=bi*aj;/先乘起来,后面统一进位,20,for(i=0;i=10)ci+1+=ci/10;ci%=10;for(i=MAX*2;(ci=0),21,除法运算的实现,首先说一下我们所要的结果，当除数除不开被子除数时，不用除到小数，当除数小于被除数时，除数作为余数既可，不用再向下除了。,22,基本思路,基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次