1、第九講,高精度計算,ACM算法與程序設計,2,大整數加法,1、鏈接地址 2、問題描述 求兩個不超過200 位的非負整數的和。 輸入數據 有兩行，每行是一個不超過200 位的非負整數，沒有多余的前導0。,3,問題描述,輸出要求 一行，即相加后的結果。結果里不能有多余的前導0，即如果結果是342，那么就不能 輸出為0342。 輸入樣例 22222222222222222222 33333333333333333333 輸出樣例 Output Sample: 55555555555555555555,4,首先要解決的就是存儲200 位整數的問題。顯然，任何C/C+固有類型的變量都無法保存它。最直觀的

2、想法是可以用一個字符串來保存它。字符串本質上就是一個字符數組，因此為了編程更方便，我們也可以用數組unsigned an200來保存一個200 位的整數，讓an0存放個位數，an1存放十位數，an2存放百位數 那么如何實現兩個大整數相加呢？方法很簡單，就是模擬小學生列豎式做加法，從個位開始逐位相加，超過或達到10 則進位。也就是說，用unsigned an1201保存第一個數，用unsigned an2200表示第二個數，然后逐位相加，相加的結果直接存放在an1 中。要注意處理進位。另外，an1 數組長度定為201，是因為兩個200 位整數相加，結果可能會有201 位。 實際編程時，不一定要費

3、心思去把數組大小定得正好合適，稍微開大點也無所謂，以免不小心沒有算準這個“正好合適”的數值，而導致數組小了，產生越界錯誤。,3、解題思路,5,4、參考程序,#include #include #define MAX_LEN 200 int an1MAX_LEN+10; int an2MAX_LEN+10; char szLine1MAX_LEN+10; char szLine2MAX_LEN+10; int main(void) scanf(%s, szLine1); scanf(%s, szLine2); int i, j; memset( an1, 0, sizeof(an1); mems

4、et( an2, 0, sizeof(an2);,6,4、參考程序,int nLen1 = strlen( szLine1); for( j = 0, i = nLen1 - 1;i = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; for( i = 0;i = 10 ) /看是否要進位 an1i -= 10; an1i+1 +; /進位 for( i = MAX_LEN; (i = 0) ,7,大整

5、數乘法,1、鏈接地址 2、問題描述 求兩個不超過200 位的非負整數的積。輸入數據有兩行，每行是一個不超過200 位的非負整數，沒有多余的前導0。輸出要求一行，即相乘后的結果。結果里不能有多余的前導0，即如果結果是342，那么就不能輸出為0342。,8,問題描述,輸入樣例 12345678900 98765432100 輸出樣例 1219326311126352690000,9,在程序中，用unsigned an1200和unsigned an2200分別存放兩個乘數，用aResult400來存放積。計算的中間結果也都存在aResult中。aResult長度取400是因為兩個200 位的數相乘

6、，積最多會有400 位。an10, an20, aResult0都表示個位。 計算的過程基本上和小學生列豎式做乘法相同。為編程方便，并不急于處理進位，而將進位問題留待最后統一處理。 現以 83549 為例來說明程序的計算過程。,3、解題思路,10,先算8359。59 得到45 個1，39 得到27 個10，89 得到72 個100。由于不急于處理進位，所以8359 算完后，結果如下：,3、解題思路,接下來算45。此處45 的結果代表20 個10，因此要 c1+=20，變?yōu)椋?再下來算43。此處43 的結果代表12 個100，因此要 c2+= 12，變?yōu)椋?11,3、解題思路,最后算 48。此處

7、48 的結果代表 32 個1000，因此要 c3+= 32，變?yōu)椋?乘法過程完畢。接下來從 c0開始向高位逐位處理進位問題。c0留下5，把4 加到c1上，c1變?yōu)?1 后，應留下1，把5 加到c2上最終使得c 里的每個元素都是1 位數，結果就算出來了：,規(guī)律：一個數的第i 位和另一個數的第j 位相乘所得的數，一定是要累加到結果的第i+j 位上。這里i, j 都是從右往左，從0 開始數。,12,4、參考程序,#include #include #define MAX_LEN 200 int main(void) int i, j; int len1,len2; int aMAX_LEN+10,b

8、MAX_LEN+10,cMAX_LEN*2+10; char str1MAX_LEN+10,str2MAX_LEN+10; for(i=0;i=0; i-)/把數字倒過來 aj+=str1i-0; len2=strlen(str2); for(j=0,i=len2-1; i=0; i-)/倒轉第二個整數 bj+=str2i-0;,13,4、參考程序,for(i=0; i=10) ci+1+=ci/10; ci%=10; for(i=MAX_LEN*2; (ci=0) ,14,大整數除法,1、鏈接地址 2、問題描述 求兩個大的正整數相除的商 輸入數據 第1 行是測試數據的組數n，每組測試數據占2

9、 行，第1 行是被除數，第2 行是除數。每組測試數據之間有一個空行，每行數據不超過100 個字符 輸出要求 n 行，每組測試數據有一行輸出是相應的整數商,15,問題描述,輸入樣例 3 2405337312963373359009260457742057439230496493930355595797660791082739646 2987192585318701752584429931160870372907079248971095012509790550883793197894 10000000000000000000000000000000000000000 10000000000 540

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

11、646 減去230，發(fā)現夠減2 次，余下186，于是商的值增加20。最后用186 減去23，夠減8 次，因此最終商就是328。 所以本題的核心是要寫一個大整數的減法函數，然后反復調用該函數進行減法操作。 計算除數的10 倍、100 倍的時候，不用做乘法，直接在除數后面補0 即可。,3、解題思路,17,4、參考程序,#include #include #define MAX_LEN 200 char szLine1MAX_LEN + 10; char szLine2MAX_LEN + 10; int an1MAX_LEN + 10; /被除數, an10對應于個位 int an2MAX_LEN

12、+ 10; /除數, an20對應于個位 int aResultMAX_LEN + 10; /存放商，aResult0對應于個位 /長度為 nLen1 的大整數p1 減去長度為nLen2 的大整數p2 /結果放在p1 里，返回值代表結果的長度 /如不夠減返回-1，正好減完返回 0 int Substract( int * p1, int * p2, int nLen1, int nLen2) int i; if( nLen1 nLen2 ) return -1;,18,4、參考程序,/下面判斷p1 是否比p2 大，如果不是，返回-1 if( nLen1 = nLen2 ) for( i = n

13、Len1-1; i=0; i - ) if( p1i p2i ) break; /p1p2 else if( p1i =nLen2 時，p2i 0 p1i -= p2i; if( p1i = 0 ; i- ) if( p1i )/找到最高位第一個不為0 return i + 1; return 0;/全部為0，說明兩者相等 ,19,4、參考程序,int main() int t, n; scanf(%d, ,20,4、參考程序,int nTimes = nLen1 - nLen2; if(nTimes 0) for( i = nLen1 -1; i = nTimes; i - ) an2i =

14、 an2i-nTimes;/朝高位移動 for( ; i = 0; i-)/低位補0 an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; /每成功減一次，則將商的相應位加1 ,21,4、參考程序,/下面輸出結果，先跳過高位0 for( i = MAX_LEN ; (i = 0) ,22,麥森數,1、鏈接地址 2、問題描述 形如2P-1 的素數稱為麥森數，這時P 一定也是個素數。但反過來不一定，即如果P 是個素數。2P-1 不一定也是素數。麥森數有許多重要應用，它與完全數完全數(又稱完備數，是一

15、些特殊的自然數。它所有的真因子（即除了自身以外的約數）的和恰好等于它本身。)密切相關. 你的任務：輸入P (1000P3100000) , 計算2p-1 的位數和最后500 位數字（用十進制高精度數表示）,23,問題描述,輸入數據 只包含一個整數P(1000P3100000) 輸出要求 第1 行：十進制高精度數2p-1 的位數。 第2-11 行：十進制高精度數2p-1 的最后500位數字。（每行輸出50 位，共輸出10 行，不足500 位時高位補0） 不必驗證2p-1 與P 是否為素數。 輸入樣例 1279,24,問題描述,輸出樣例 386 00000000000000000000000000

16、000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547

17、689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087,25,第一個問題，輸出2p-1 有多少位。由于2p 的個位數只可能是2, 4, 6, 8 所以2p-1 和2p的位數相同。使用C/C+標準庫中在math.h 里聲明的，求以10為底的對數的函數double log10(double

18、x) 函數，就能輕松求得2p-1 的位數。 2p 的值需要用一種高效率的辦法來算。 顯然，對于任何p0，考慮p 的二進制形式，則不難得到： 這里，ai 要么是1，要么是0。,3、解題思路,26,因而： 計算2p 的辦法就是：先將結果的值設為1，計算21。如果a0 值為1，則結果乘以21；計算22，如果a1 為1，則結果乘以22；計算24，如果a2 為1，則結果乘以24；總之，第i 步(i 從0 到n，an 是1)就計算22i，如果ai 為1，則結果就乘以22i。每次由22i22i就能算出22(i+1)。由于p可能很大，所以上面的乘法都應該使用高精度計算。由于題目只要求輸出500 位，所以這些乘

19、法都是只須算出末尾的500 即可。,3、解題思路,27,在前面的高精度計算中，我們用數組來存放大整數，數組的一個元素對應于十進制大整數的一位。本題如果也這樣做，就會超時。為了加快計算速度，可以用一個數組元素對應于大整數的4 位，即將大整數表示為10000 進制，而數組中的每一個元素就存放10000 進制數的1 位。例如，用int 型數組 a 來存放整數6373384，那么只需兩個數組元素就可以了，a0=3384, a1=637。 由于只要求結果的最后500 位數字，所以我們不需要計算完整的結果，只需算出最后500 位即可。因為用每個數組元素存放十進制大整數的4 位，所以本題中的數組最多只需要1

20、25 個元素。,3、解題思路,28,4、參考程序,#include #include #define LEN 125 /每數組元素存放4 位，數組最多需要125 個元素 #include /計算高精度乘法 a * b, 結果的末500 位放在a 中 void Multiply(int* a, int* b) int i, j; int nCarry; /存放進位 int nTmp; int cLEN; /存放結果的末500 位 memset(c, 0, sizeof(int) * LEN); for (i=0;iLEN;i+) nCarry=0; for (j=0;jLEN-i;j+) nTm

21、p=ci+j+aj*bi+nCarry; ci+j=nTmp%10000; nCarry=nTmp/10000; memcpy( a, c, LEN*sizeof(int); ,29,4、參考程序,int main(void) int i; int p; int anPowLEN; /存放不斷增長的2 的次冪 int aResultLEN; /存放最終結果的末500 位 scanf(%d, ,30,4、參考程序,aResult0-; /2p-1 /輸出結果 for (i=LEN-1;i=0;i-) if (i%25=12) printf(%02dn%02d, aResulti/100, aRe

22、sulti%100); else printf(%04d, aResulti); if (i%25=0) printf(n); return 0; ,31,練習：Exponentiation,Description (POJ：1001) Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems. This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 R 99.999 ) and n is an integer such that 0 n = 25.,32,Description,Input The input will consist of a set of pairs of values for R and n. The R value will occu