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

1、ACM程序設(shè)計(jì)第十一講-大數(shù)運(yùn)算湖南工學(xué)院 張新玉各類型的范圍 int （16位） -3276832767（注：現(xiàn)在大多數(shù)的編譯器的int型是32位的 也就是說跟long型的大小一樣） long long或_int64（64位） -92233720368547758089223372036854775807 float（32位） 精確到小數(shù)點(diǎn)后67位 double （64位） 精確到小數(shù)點(diǎn)后1516位（注：平時(shí)做題時(shí) 都把浮點(diǎn)型數(shù)據(jù)定義為double型 避免精度不夠出錯(cuò)）請(qǐng)計(jì)算：請(qǐng)計(jì)算：1 1、 2 2 的的 10001000次冪次冪2 2、 2 2 的的 1000010000次冪次冪3 3、

2、 1234567890123456789123456789034123456789012345678912345678903453434534534535345434543 53434534534535345434543 乘上乘上9387429387492873492873402803482938742938749287349287340280348209384792883748927334534535340938479288374892733453453534主要內(nèi)容數(shù)字存儲(chǔ)的實(shí)現(xiàn)數(shù)字存儲(chǔ)的實(shí)現(xiàn)1加法運(yùn)算的實(shí)現(xiàn)加法運(yùn)算的實(shí)現(xiàn) 2減法運(yùn)算的實(shí)現(xiàn)減法運(yùn)算的實(shí)現(xiàn) 3乘法運(yùn)算的實(shí)現(xiàn)乘法運(yùn)算的實(shí)現(xiàn) 4

3、除法運(yùn)算的實(shí)現(xiàn)除法運(yùn)算的實(shí)現(xiàn) 5冪運(yùn)算的實(shí)現(xiàn)冪運(yùn)算的實(shí)現(xiàn)6數(shù)字存儲(chǔ)的實(shí)現(xiàn) 大數(shù)計(jì)算的因數(shù)和結(jié)果精度一般是少則數(shù)十位，多則幾萬位。在C/C+語言中定義的類型中精度最多只有二十多位。一般我們稱這種基本數(shù)據(jù)類型無法表示的整數(shù)為大整數(shù)。如何表示和存放大整數(shù)呢？基本的思想就是：用數(shù)組存放和表示大整數(shù)。一個(gè)數(shù)組元素，存放大整數(shù)中的一位。比如：166443431801234567891664434318下標(biāo)下標(biāo)加法運(yùn)算的實(shí)現(xiàn)99876543201664434300加數(shù)加數(shù)被加數(shù)被加數(shù)+初始化進(jìn)位為初始化進(jìn)位為0 0，各對(duì)應(yīng)，各對(duì)應(yīng)位相加后再加上進(jìn)位數(shù)位相加后再加上進(jìn)位數(shù)1 1、進(jìn)位為、進(jìn)位為1 102 2、

4、進(jìn)位為、進(jìn)位為1 163 3、進(jìn)位為、進(jìn)位為1 154 4、進(jìn)位為、進(jìn)位為1 12由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束應(yīng)注意問題： 1. 判斷最后數(shù)組的長(zhǎng)度.2. 去掉前導(dǎo)零大數(shù)加法void Add(char s1,char s2)/參數(shù)為兩個(gè)字符串?dāng)?shù)組 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

5、; i = 0; i -) num2j+ = s2i - 0; for (i = 0; i 9) num1i -= 10; num1i+1 +; for (i = M-1; (i = 0)&(num1i = 0); i -) ;/找到第一個(gè)不是 0的數(shù)的位置 if (i = 0) /從高位到低位輸出每個(gè)數(shù) for (; i = 0; i -) printf (%d,num1i); else printf (0n);減法運(yùn)算的實(shí)現(xiàn) v算法也是從低位開始減。先要判斷減數(shù)和被減數(shù)那一個(gè)位數(shù)長(zhǎng)，減數(shù)位數(shù)長(zhǎng)是正常減；被減數(shù)位數(shù)長(zhǎng)，則被減數(shù)減減數(shù)，最后還要加上負(fù)號(hào)；兩數(shù)位數(shù)長(zhǎng)度相等時(shí)，最好比那一個(gè)

6、數(shù)字大，否則負(fù)號(hào)處理會(huì)很繁瑣；處理每一項(xiàng)時(shí)要，如果前一位相減有借位，就先減去上一位的借位，無則不減，再去判斷是否能夠減開被減數(shù)，如果減不開，就要借位后再去減，同時(shí)置借位為1，否則置借位為0。減法運(yùn)算的實(shí)現(xiàn)76876543208975434320減數(shù)減數(shù)被減數(shù)被減數(shù)-初始化借位為初始化借位為0 0，各對(duì)應(yīng)，各對(duì)應(yīng)位相減后再減上借位數(shù)位相減后再減上借位數(shù)1 1、借位為、借位為1 192 2、借位為、借位為1 163 3、借位為、借位為0 004 4、借位為、借位為0 02由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束由低位向高位相加計(jì)算，直至所有運(yùn)算結(jié)束處理中注意問題： 1如果被減數(shù)大于減數(shù)時(shí)如果被減數(shù)大

7、于減數(shù)時(shí)，交換兩個(gè)數(shù)再相減，交換兩個(gè)數(shù)再相減，最后加個(gè)最后加個(gè)“-”號(hào)即可號(hào)即可2結(jié)果可能會(huì)出現(xiàn)前面是結(jié)果可能會(huì)出現(xiàn)前面是一堆一堆0的情況，要處理好的情況，要處理好，如當(dāng)減數(shù)為，如當(dāng)減數(shù)為112，而被，而被減數(shù)為減數(shù)為111時(shí)，會(huì)出現(xiàn)時(shí)，會(huì)出現(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)一處理。 ansi+j =

8、 ai*bj; 現(xiàn)以 83549 為例來說明程序的計(jì)算過。1. 先算8359。59 得到45 個(gè)1，39 得到27 個(gè)10，89 得到72 個(gè)100。由于不急于處理進(jìn)位，所以8359 算完后，aResult 如下：2. 接下來算45。此處45 的結(jié)果代表20 個(gè)10，因此要 aResult1+=20，變?yōu)椋?.再下來算43。此處43 的結(jié)果代表 12 個(gè)100，因此要 aResult2+= 12，變?yōu)椋?.最后算 48。此處48 的結(jié)果代表 32 個(gè)1000，因此要 aResult3+= 32，變?yōu)椋?. 乘法過程完畢。接下來從 aResult0開始向高位逐位處理進(jìn)位問題。aResult0留下

9、5，把4 加到aResult1上，aResult1變?yōu)?1 后，應(yīng)留下1，把5 加到aResult2上最終使得aResult 里的每個(gè)元素都是1 位數(shù)，結(jié)果就算出來了： 總結(jié)一個(gè)規(guī)律:即一個(gè)數(shù)的第i 位和另一個(gè)數(shù)的第j 位相乘所得的數(shù)，一定是要累加到結(jié)果的第i+j 位上。這里i, j 都是從右往左，從0 開始數(shù)。 ansi+j = ai*bj; 處理中注意問題： 1另外進(jìn)位時(shí)要處理，當(dāng)前的值加另外進(jìn)位時(shí)要處理，當(dāng)前的值加上進(jìn)位的值再看本位數(shù)字是否又上進(jìn)位的值再看本位數(shù)字是否又有進(jìn)位；前導(dǎo)清零。有進(jìn)位；前導(dǎo)清零。大數(shù)乘法void Multi(char str1,char str2) int le

10、n1,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-)/把數(shù)字倒過來 aj+=str1i-0; len2=strlen(str2); for(j=0,i=len2-1; i=0; i-)/倒轉(zhuǎn)第二個(gè)整數(shù) bj+=str2i-0; for(i=0; ilen2; i+)/用第二個(gè)數(shù)乘以第一個(gè)數(shù),每次一位 for(j=0; jlen1; j

11、+) ci+j+= bi*aj; /先乘起來,后面統(tǒng)一進(jìn)位 for(i=0; i=10) ci+1+=ci/10; ci%=10; for(i=MAX*2; (ci=0)&(i=0); i-);/跳過高位的0 if(i=0) for(; i=0; i-) printf(%d, ci); else printf(0); pritnf(n);除法運(yùn)算的實(shí)現(xiàn)除法運(yùn)算的實(shí)現(xiàn)v首先說一下我們所要的結(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