ACM培訓(xùn)第十一講-大數(shù)運(yùn)算

ACM程序設(shè)計(jì)

第十一講-大數(shù)運(yùn)算湖南工學(xué)院張新玉zhangxinyu247@163.com各類型的范圍int（16位）-32768～32767（注：現(xiàn)在大多數(shù)的編譯器的int型是32位的也就是說跟long型的大小一樣）longlong或__int64（64位）-9223372036854775808～9223372036854775807float（32位）精確到小數(shù)點(diǎn)后6～7位double（64位）精確到小數(shù)點(diǎn)后15～16位（注：平時(shí)做題時(shí)都把浮點(diǎn)型數(shù)據(jù)定義為double型避免精度不夠出錯(cuò)）請計(jì)算：1、2的1000次冪2、2的10000次冪3、123456789012345678912345678903453434534534535345434543乘上93874293874928734928734028034820938479288374892733453453534主要內(nèi)容數(shù)字存儲的實(shí)現(xiàn)1加法運(yùn)算的實(shí)現(xiàn)

2減法運(yùn)算的實(shí)現(xiàn)

3乘法運(yùn)算的實(shí)現(xiàn)

4除法運(yùn)算的實(shí)現(xiàn)5冪運(yùn)算的實(shí)現(xiàn)6數(shù)字存儲的實(shí)現(xiàn)大數(shù)計(jì)算的因數(shù)和結(jié)果精度一般是少則數(shù)十位，多則幾萬位。在C/C++語言中定義的類型中精度最多只有二十多位。一般我們稱這種基本數(shù)據(jù)類型無法表示的整數(shù)為大整數(shù)。如何表示和存放大整數(shù)呢？基本的思想就是：用數(shù)組存放和表示大整數(shù)。一個(gè)數(shù)組元素，存放大整數(shù)中的一位。比如：166443431801234567891664434318下標(biāo)加法運(yùn)算的實(shí)現(xiàn)99876543201664434300加數(shù)被加數(shù)+初始化進(jìn)位為0，各對應(yīng)位相加后再加上進(jìn)位數(shù)1、進(jìn)位為102、進(jìn)位為163、進(jìn)位為154、進(jìn)位為12由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束應(yīng)注意問題：判斷最后數(shù)組的長度.去掉前導(dǎo)零大數(shù)加法voidAdd(chars1[],chars2[])//參數(shù)為兩個(gè)字符串?dāng)?shù)組{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;i<M;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--);//找到第一個(gè)不是0的數(shù)的位置

if(i>=0)//從高位到低位輸出每個(gè)數(shù)

for(;i>=0;i--)printf("%d",num1[i]);elseprintf("0\n");}減法運(yùn)算的實(shí)現(xiàn)算法也是從低位開始減。先要判斷減數(shù)和被減數(shù)那一個(gè)位數(shù)長，減數(shù)位數(shù)長是正常減；被減數(shù)位數(shù)長，則被減數(shù)減減數(shù)，最后還要加上負(fù)號；兩數(shù)位數(shù)長度相等時(shí)，最好比那一個(gè)數(shù)字大，否則負(fù)號處理會很繁瑣；處理每一項(xiàng)時(shí)要，如果前一位相減有借位，就先減去上一位的借位，無則不減，再去判斷是否能夠減開被減數(shù)，如果減不開，就要借位后再去減，同時(shí)置借位為1，否則置借位為0。減法運(yùn)算的實(shí)現(xiàn)76876543208975434320減數(shù)被減數(shù)-初始化借位為0，各對應(yīng)位相減后再減上借位數(shù)1、借位為192、借位為163、借位為004、借位為02由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束處理中注意問題：1如果被減數(shù)大于減數(shù)時(shí)，交換兩個(gè)數(shù)再相減，最后加個(gè)“-”號即可2結(jié)果可能會出現(xiàn)前面是一堆0的情況，要處理好，如當(dāng)減數(shù)為112，而被減數(shù)為111時(shí)，會出現(xiàn)001乘法運(yùn)算的實(shí)現(xiàn)首先說一下乘法計(jì)算的算法，從低位向高位乘，在豎式計(jì)算中，我們是將乘數(shù)第一位與被乘數(shù)的每一位相乘，記錄結(jié)果，之后，用第二位相乘，記錄結(jié)果并且左移一位，以此類推，直到計(jì)算完最后一位，再將各項(xiàng)結(jié)果相加。得出最后結(jié)果。計(jì)算的過程基本上和小學(xué)生列豎式做乘法相同。為編程方便，并不急于處理進(jìn)位，而將進(jìn)位問題留待最后統(tǒng)一處理。ans[i+j]=a[i]*b[j];現(xiàn)以835×49為例來說明程序的計(jì)算過。先算835×9。5×9得到45個(gè)1，3×9得到27個(gè)10，8×9得到72個(gè)100。由于不急于處理進(jìn)位，所以835×9算完后，aResult如下：接下來算4×5。此處4×5的結(jié)果代表20個(gè)10，因此要aResult[1]+=20，變?yōu)椋?.再下來算4×3。此處4×3的結(jié)果代表12個(gè)100，因此要aResult[2]+=12，變?yōu)椋?.最后算4×8。此處4×8的結(jié)果代表32

個(gè)1000，因此要aResult[3]+=32，變?yōu)椋撼朔ㄟ^程完畢。接下來從aResult[0]開始向高位逐位處理進(jìn)位問題。aResult[0]留下5，把4加到aResult[1]上，aResult[1]變?yōu)?1后，應(yīng)留下1，把5加到aResult[2]上……最終使得aResult里的每個(gè)元素都是1位數(shù)，結(jié)果就算出來了：總結(jié)一個(gè)規(guī)律:即一個(gè)數(shù)的第i位和另一個(gè)數(shù)的第j位相乘所得的數(shù)，一定是要累加到結(jié)果的第i+j位上。這里i,j都是從右往左，從0開始數(shù)。ans[i+j]=a[i]*b[j];處理中注意問題：1另外進(jìn)位時(shí)要處理，當(dāng)前的值加上進(jìn)位的值再看本位數(shù)字是否又有進(jìn)位；前導(dǎo)清零。大數(shù)乘法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--)//把數(shù)字倒過來

a[j++]=str1[i]-'0';len2=strlen(str2);for(j=0,i=len2-1;i>=0;i--)//倒轉(zhuǎn)第二個(gè)整數(shù)

b[j++]=str2[i]-'0';for(i=0;i<len2;i++)//用第二個(gè)數(shù)乘以第一個(gè)數(shù),每次一位

for(j=0;j<len1;j++)c[i+j]+=b[i]*a[j];//先乘起來,后面統(tǒng)一進(jìn)位

for(i=0;i<MAX*2;i++)//循環(huán)統(tǒng)一處理進(jìn)位問題

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");}除法運(yùn)算的實(shí)現(xiàn)首先說一下我們所要的結(jié)果，當(dāng)除數(shù)除不開被除數(shù)時(shí)，不用除到小數(shù)，當(dāng)除數(shù)小于被除數(shù)時(shí)，除數(shù)作為余數(shù)既可，不用再向下除了。

基本思路基本的思想是反復(fù)做減法，看看從被除數(shù)里最多能減去多少個(gè)除數(shù)，商就是多少。一個(gè)一個(gè)減顯然太慢，如何減得更快一些呢？以7546除以23為例來看一下：開始商為0。先減去23的100倍，就是2300，發(fā)現(xiàn)夠減3次，余下646。于是商的值就增加300。然后用646減去230，發(fā)