C语言_超大数四则运算.ppt

1、,超大数的四则运算,2,各类型的范围,int （16位） -3276832767 （注：现在大多数的编译器的int型是32位的 也就是说跟long型的大小一样） long long或_int64（64位） -92233720368547758089223372036854775807 float（32位） 精确到小数点后67位 double （64位） 精确到小数点后1516位 （注：平时做题时 都把浮点型数据定义为double型 避免精度不够出错）,3,请计算： 1、 2 的 1000次幂 2、 2 的 10000次幂 3、 123456789012345678912345678903453

2、434534534535345434543 乘上 93874293874928734928734028034820938479288374892733453453534,4,主要内容,5,数字存储的实现,大数计算的因数和结果精度一般是少则数十位，多则几万位。在C/C+语言中定义的类型中精度最多只有二十多位。一般我们称这种基本数据类型无法表示的整数为大整数。如何表示和存放大整数呢？基本的思想就是：用数组存放和表示大整数。一个数组元素，存放大整数中的一位。 比如：1664434318,下标,6,加法运算的实现,加数,被加数,+,初始化进位为0，各对应位相加后再加上进位数,1、进位为1,0,3、进位

3、为1,5,4、进位为1,2,由低位向高位相加计算，直至所有运算结束,7,理中注意问题：,判断最后数组的长度. 去掉前导零,8,大数加法,void Add(char s1,char s2)/参数为两个字符串数组 int num1M,num2M; int i,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;

4、 i 9) num1i -= 10; num1i+1 +; ,9,for (i = M-1; (i = 0) ,10,减法运算的实现,算法也是从低位开始减。先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两数位数长度相等时，最好比那一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。,11,减法运算的实现,减数,被减数,-,初始化借位为0，各对应位相减后再减上借位数,1、借位为1,9,2、借位为1,6

5、,3、借位为0,0,4、借位为0,2,由低位向高位相加计算，直至所有运算结束,12,处理中注意问题：,13,乘法运算的实现,首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加。得出最后结果。 计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。 ansi+j = ai*bj;,14,现以 83549 为例来说明程序的计算过。,先算8359。59 得到45 个1，39 得到27 个10，89 得到72 个

6、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

7、 位数，结果就算出来了：,17,总结一个规律:即一个数的第i 位和另一个数的第j 位相乘所得的数，一定是要累加到结果的第i+j 位上。这里i, j 都是从右往左，从0 开始数。 ansi+j = ai*bj;,18,处理中注意问题：,19,大数乘法,void Multi(char str1,char str2) int len1,len2,i,j; int aMAX+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

8、=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