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

ACM程序設計

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

2減法運算的實現(xiàn)

3乘法運算的實現(xiàn)

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

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

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

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

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

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

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

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

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