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

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