1、1 高精度整數(shù)問(wèn)題 組合數(shù)和Catalan的精確計(jì)算福州大學(xué)04(3)班 學(xué)號(hào)：030402332算法與數(shù)據(jù)結(jié)構(gòu)第二次作業(yè)解題報(bào)告2問(wèn)題描述 編一個(gè)大整數(shù)模板類，用來(lái)做高精度整數(shù)（也就是任意位數(shù)的整數(shù)）的四則運(yùn)算，包括 加法（addition） 減法（subtraction） 乘法（multiplication） 除法（division） 利用上面設(shè)計(jì)的大整數(shù)模板類精確地計(jì)算組合數(shù)和Catalan數(shù)。3大整數(shù)的介紹 在某些情況下(如數(shù)據(jù)加密和科學(xué)計(jì)算等方面)，我們要處理很大的整數(shù)，它無(wú)法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。若用浮點(diǎn)數(shù)來(lái)表示它，則只能近似地表示它的大小，計(jì)算結(jié)果中的有效數(shù)字也

2、受到限制(如C+中的Double類型有效位只有15位) 。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字，就必須用軟件的方法來(lái)實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。4需要解決的問(wèn)題 大整數(shù)的表示 在利于編程實(shí)現(xiàn)，同時(shí)便于提高運(yùn)算效率的基礎(chǔ)上選擇數(shù)據(jù)結(jié)構(gòu)。這個(gè)主要是考查數(shù)據(jù)結(jié)構(gòu)。我們將會(huì)發(fā)現(xiàn)，在數(shù)據(jù)結(jié)構(gòu)上的一個(gè)小改進(jìn)對(duì)效率的提高有時(shí)會(huì)有很大幫助的。而數(shù)據(jù)結(jié)構(gòu)在一定程度上是可以彌補(bǔ)算法的不足的。 大整數(shù)的運(yùn)算 利用所選的數(shù)據(jù)結(jié)構(gòu)，正確、高效地實(shí)現(xiàn)整數(shù)的四則運(yùn)算。這主要考查算法。我們可以看到算法的選擇對(duì)程序的效率是有絕對(duì)影響的。算法是決定程序效率的根本。5大整數(shù)的表示 由于大整數(shù)的位數(shù)太多，我們首

3、先要做的是把它“拆”開來(lái)，放在若干個(gè)地方，然后建立不同存儲(chǔ)地址之間的聯(lián)系。很明顯，線性數(shù)組(或者說(shuō)是線性表)是首選。下面的存儲(chǔ)方式很直觀也是最容易想到的。 對(duì)于大整數(shù)1112223334445 我們可以用一維數(shù)組來(lái)表示：數(shù)組下標(biāo)：存儲(chǔ)數(shù)據(jù)：012 3 4 5 6 7 8 9 1011121112 2 2 3 3 3 44456進(jìn)位沒(méi)有存放的位置大整數(shù)的表示但我們可以發(fā)現(xiàn)這種表示方法的一個(gè)不足之處：計(jì)算這個(gè)大整數(shù)加上90的結(jié)果。如果用前面的方式存儲(chǔ)，我們會(huì)發(fā)現(xiàn)進(jìn)位沒(méi)有地方存放了。數(shù)組下標(biāo)：大整數(shù)一：大整數(shù)二：結(jié)果： 1為什么會(huì)出現(xiàn)這種情況？原因在于我們把大整數(shù)的高位存放在數(shù)組的下標(biāo)小的位置。而解

4、決這個(gè)問(wèn)題的方法也很簡(jiǎn)單，就是把整數(shù)反過(guò)來(lái)存放。0 1 2 3 4 5 6 7 8 9 1011121 1 1 2 2 2 3 3 3 44459 0 0 0 0 0 0 0 0 0 0001 1 1 2 2 2 3 3 3 44457這個(gè)進(jìn)位可以通過(guò)擴(kuò)大數(shù)組的方法來(lái)存放大整數(shù)的表示 另一種表示方式數(shù)組下標(biāo)：大整數(shù)一：大整數(shù)二：結(jié)果： 1其實(shí)前一種表示方法還會(huì)有一個(gè)問(wèn)題。就是高位的對(duì)齊，這個(gè)我們可以通過(guò)減法觀察到，這里就不說(shuō)了?；谝陨显?，我們采用線性數(shù)組，同時(shí)把高位存放在下標(biāo)大的地方。雖然這樣子存放我們看起來(lái)不那么直觀，但后面我們會(huì)看到這種存放方式的好處。012 3 4 5 6 7 8 9

5、 1011125 4 4 4 3 3 3 2 2 21110 0 0 0 0 0 0 0 0 00095 4 4 4 3 3 3 2 2 21108高精度加法運(yùn)算 在確立了使用線性數(shù)組表示的大前提后，我們可以很容易地解決高精度加法。(這里為了簡(jiǎn)便，我就不用類實(shí)現(xiàn)了，同時(shí)假設(shè)那兩個(gè)大整數(shù)都為正數(shù)。) 1.初始化數(shù)組，數(shù)組全部元素置為0 2.用字符串讀入大整數(shù)，同時(shí)以反向存儲(chǔ)的方式 存放在數(shù)組中 3.進(jìn)位標(biāo)志flag置為0。從數(shù)組低位開始進(jìn)行加 法運(yùn)算。這里只要注意flag的更新就行了。 4.反向輸出結(jié)果9高精度加法運(yùn)算高精度加法舉例 這里我們假設(shè)我們已讀入兩個(gè)大整數(shù)，并且也已經(jīng)被分別反向存放在數(shù)

6、組a和數(shù)組b中了。 加數(shù)a 8 7 4 2 5 9 7 80 0 加數(shù)b 4 8 3 1 4 8 5 1 9 0 結(jié)果c 2 6 8 3 9 7 3 00 1 進(jìn)位e 1 1 0 0 0 1 1 1 1 0 上面的過(guò)程表示為 87952478+915841384=1003793862減法亦可用相同的方法實(shí)現(xiàn)，只是現(xiàn)在標(biāo)志換成借位標(biāo)記而已。前面補(bǔ)0的原因是為了對(duì)齊10高精度加、減法小結(jié)及其改進(jìn)我們首先要明確的一點(diǎn)是，選擇線性數(shù)組及反向存儲(chǔ)的方式并不是偶然的。我們可以列一個(gè)豎式，用手工模擬854+87的加法就會(huì)理解為什么要這樣子處理了。而我們同時(shí)會(huì)發(fā)現(xiàn)，一個(gè)數(shù)組元素只存儲(chǔ)一個(gè)位的方式有點(diǎn)浪費(fèi)，雖然

7、這很合乎我們的習(xí)慣。但可不可以通過(guò)增加存儲(chǔ)位數(shù)的方法來(lái)提高效率呢？畢竟我們需要的這個(gè)一個(gè)位計(jì)算機(jī)只要4個(gè)二進(jìn)制位就可以表示了，而VC給我們分配的一個(gè)int卻有32位。11大整數(shù)的運(yùn)算之加、減法的改進(jìn)我們來(lái)分析只存儲(chǔ)一個(gè)位的大整數(shù)加法是怎樣進(jìn)行的。加數(shù)a 8 7 4 2 5 9 7 80 0加數(shù)b 4 8 3 1 4 8 5 1 9 0結(jié)果c 2 6 8 3 9 7 3 00 1進(jìn)位e 1 1 0 0 0 1 1 1 1 0設(shè)i表示數(shù)組第i位數(shù)，則ci = (ai + bi + e) % 10;e = (ai + bi + e) / 10;12大整數(shù)的運(yùn)算之加、減法的改進(jìn)所以我們?nèi)绻M(jìn)行多位存

8、儲(chǔ)的話，我們只要把上面的計(jì)算式子改成ci = (ai + bi + e) % M;e = (ai + bi + e) / M;其中M為10的n次方，n為規(guī)定的位數(shù)。如，每個(gè)數(shù)組元素都存儲(chǔ)4個(gè)位，則M=10000。這個(gè)改進(jìn)并沒(méi)有引起程序上大的變動(dòng)，但它的對(duì)運(yùn)算次數(shù)的減少是很有用的。做每個(gè)元素存儲(chǔ)n位的加法，其加法的次數(shù)為只存儲(chǔ)一位的1/n。這是因?yàn)樗龃罅舜鎯?chǔ)密度，所以運(yùn)算速度也隨之提升了。13高精度加法程序 flag = 0; n = min(a的位數(shù)，b的位數(shù)); M= 10000; For (i=0; in | flag; i+) ci = (ai + bi + flag) % M; fl

9、ag = (ai + bi + flag) / M;14習(xí)題 四川大學(xué)Online Judge 1001和1002 第二屆福州大學(xué)程序設(shè)計(jì)大賽Fibonacci數(shù)列 15高精度乘法 我們先來(lái)看一個(gè)小整數(shù)乘以大整數(shù)的乘法運(yùn)算是如何進(jìn)行的。我們模擬一下587414251047*56的執(zhí)行過(guò)程。這里為了提高效率，56并沒(méi)有必要被分成兩個(gè)位去算，而是利用多位存儲(chǔ)的思想來(lái)運(yùn)算。大整數(shù)：7 4 0 1 5 2 4 1 4 7 8 5乘數(shù)： 56進(jìn)位： 39 26 2 5 28 14 23 7 23 41 48 32 3 0結(jié)果： 2 3 6 8 5 0 8 9 1 5 9 8 2 3所以乘法的最后結(jié)果就是

10、32895198058632這里的關(guān)鍵就是進(jìn)位不一定是一位的。其原理和加法多位存儲(chǔ)的運(yùn)算是一樣的。16高精度乘法現(xiàn)在我們來(lái)看看大整數(shù)乘以大整數(shù)是怎樣進(jìn)行的。還是先做手工模擬一下516541*4845412是怎么算的。我們發(fā)現(xiàn)它的原型就是先進(jìn)行小整數(shù)乘以大整數(shù)，再把它們的和加起來(lái)的過(guò)程。其根本思想就是：設(shè)兩個(gè)大整數(shù)分別為a，b(都已反向存儲(chǔ)了)。將b按10進(jìn)制展開，b=b0+10*b1+100*b2+bn*10n。其中bi為小于10的非負(fù)整數(shù)。則a*b=a*b0+a*b1*10+a*b2*100+a*bn*10n。而a*bi就是小整數(shù)乘以大整數(shù)。(后面乘10k，只要進(jìn)行移位就可以實(shí)現(xiàn)了)17高精

11、度乘法高精度乘法算法流程如下：讀入被乘數(shù)s1，乘數(shù)s2把s1、s2分成n位一段，轉(zhuǎn)成數(shù)值反向存在數(shù)組a,b中；記下b的長(zhǎng)度mi=0;從b中取出第i位與a相乘，累加到另一數(shù)組c中；（注意：累加時(shí)錯(cuò)開的位數(shù)應(yīng)是多少位）i+；檢測(cè)i值：大于m則轉(zhuǎn),否則轉(zhuǎn)打印結(jié)果18為什么結(jié)果存放在這一位？高精度乘法程序M = 10000;p = 大整數(shù)a的“位數(shù)”;/這里的位數(shù)是指多位存儲(chǔ)時(shí)的位數(shù)q =大整數(shù)b的“位數(shù)”;for (i=0; ip; i+) flag = 0; for (j=0; j=0)?在R后面加上bj，轉(zhuǎn)4：轉(zhuǎn)7；1. 輸出商數(shù)Q及余數(shù)R。20高精度除法這里就不給出除法的程序了。但在實(shí)現(xiàn)時(shí)需要

12、注意1.除法可以反向除也可以正向存儲(chǔ)，只要做相應(yīng)調(diào)整就可以2.實(shí)現(xiàn)時(shí)需要定義一個(gè)函數(shù)來(lái)比較兩個(gè)大整數(shù)的大小，同時(shí)要用到大整數(shù)減法3.多位存儲(chǔ)還是可以運(yùn)用的。但細(xì)節(jié)上要小心21習(xí)題 四川大學(xué)Online Judge 1003、1004 北京大學(xué)Online Judge 1001 求PI的精度值到10000位 求e的精度值到10000位22組合數(shù)和Catalan的精確計(jì)算由于Catalan函數(shù)本身是一個(gè)組合數(shù)再除以一個(gè)相對(duì)較小的整數(shù)，而除法在前面已經(jīng)提過(guò)了。這里我們就只看組合數(shù)的精確求值。算法一：C(m,n)=C(m-1,n)+C(m-1,n-1)C(m,0)=1利用上面的遞歸式，我們可以在O(n

13、*大整數(shù)位數(shù))輔助空間的基礎(chǔ)上設(shè)計(jì)出一個(gè)只用加法就能算組合數(shù)的算法。但我們看出這在實(shí)際上是不實(shí)際的。當(dāng)m=10000,n=5000時(shí)，輔助空間就要達(dá)到4*5000*3009Bytes約50幾M的內(nèi)存。實(shí)際上，它在時(shí)間效率上也是很不理想的。23組合數(shù)和Catalan的精確計(jì)算算法二：利用C(m,n)=m!/(n!*(m-n)!)對(duì)上式進(jìn)行化簡(jiǎn)可變?yōu)镃(m,n)=m*(m-1)*(m-n+1)/n!在實(shí)現(xiàn)上，我們?nèi)绻劝裮*(m-1)*(m-n+1)算出來(lái)再去除以n!的話，時(shí)間和空間的消耗都是比較大的。我當(dāng)時(shí)的做法是24組合數(shù)和Catalan的精確計(jì)算1.采用多位存儲(chǔ)，數(shù)組每個(gè)元素存儲(chǔ)4位2.從m

14、開始乘到(m-n+1)時(shí)，每乘一個(gè)數(shù)k就相就地除以一個(gè)數(shù)(m-k+1)。這樣即可以保證結(jié)果還是整數(shù)的同時(shí)，減慢空間的消耗。3.等乘數(shù)或除數(shù)夠大時(shí)才進(jìn)行相應(yīng)的計(jì)算。如算100*99*50/50!一開始時(shí)我們沒(méi)必要馬上就把100乘到結(jié)果上去。而是等再乘上99后，再把結(jié)果乘上9900。這樣可以減少很多次計(jì)算。最后我的程序計(jì)算C(5000,2500)和C(10000,5000)/50001差不多要1.7S才能出結(jié)果。對(duì)這個(gè)結(jié)果還是不大滿意。于是我又想了另一種算法。25組合數(shù)和Catalan的精確計(jì)算算法三分析一下算法二，程序運(yùn)行時(shí)間主要花在高精度乘法和高精度除法上。而乘法是必需的，效率也比除法好很多，

15、因此我們的著眼點(diǎn)就變成了，怎么去避免除法或?qū)⒊ㄞD(zhuǎn)換成乘法或干脆就將除法去掉。如果能將除法去掉當(dāng)然是最好的了。但能不能做到呢？答案是可以。還是利用到算法二的那個(gè)化簡(jiǎn)后的式子。別看它挺長(zhǎng)的，但我們可以保證，它的計(jì)算結(jié)果一定是整數(shù)。因?yàn)榻M合數(shù)本身就是一個(gè)整數(shù)，沒(méi)有理由經(jīng)過(guò)化簡(jiǎn)后就變成帶有小數(shù)的實(shí)數(shù)。26組合數(shù)和Catalan的精確計(jì)算利用這點(diǎn)，聯(lián)想到小學(xué)時(shí)經(jīng)常做的分?jǐn)?shù)化簡(jiǎn)，只要先把分子進(jìn)行分解，存放在一個(gè)數(shù)組count中，counti表示分解后因子為i的個(gè)數(shù)。再將分母也進(jìn)行分解，但在分解的過(guò)程中，每次得到一個(gè)因子k，我們只要countk-就可以了。因?yàn)閙的值不可能太大，而count最大只需o(m)的輔助空間，所以在空間是可行的。在時(shí)間效率上，因?yàn)楸苊饬顺ㄟ\(yùn)算，所以效率上肯定會(huì)有大的改進(jìn)的。利用和算法二一樣的一些技巧后，我的程序計(jì)算C(5000,2500)和C(10000,5000)/50001只要0.7S就可以得到結(jié)果了。27總結(jié)其實(shí)算法三還是可以再做改進(jìn)的