6 模擬與高精度計算

1、第六講模擬與高精度計算ACM算法與程序設(shè)計現(xiàn)實中的有些問題難以找到公式或規(guī)律來解決。只能按照一定步驟不停地做下去，最后才能得到答案。這樣的問題，用計算機來解決十分合適，只要能讓計算機模擬人在解決問題時的行為即可。這一類的問題可以稱之為“模擬題”。摘花生 問題描述 魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費品嘗我種的花生！熊字”。 魯賓遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。 有經(jīng)驗的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓練

2、多多的算術(shù)，魯賓遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊。” 我們假定多多在每個單位時間內(nèi)，可以做下列四件事情中的一件： (1) 從路邊跳到最靠近路邊（即第一行）的某棵花生植株；(2) 從一棵植株跳到前后左右與之相鄰的另一棵植株； (3) 采摘一棵植株下的花生； (4) 從最靠近路邊（即第一行）的某棵花生植株跳回路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布，請問在限定時間內(nèi)，多多最多可以采到多少個花生？注意可能只有部分植株下面長有花生，假設(shè)這些植株下的花生個數(shù)各不相同。 例如在圖2所示的

3、花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下長有花生，個數(shù)分別為13, 7, 15, 9。沿著圖示的路線，多多在21個單位時間內(nèi)，最多可以采到37個花生。 輸入格式 輸入的第一行包括一個整數(shù)T，表示數(shù)據(jù)組數(shù)。 每組輸入的第一行包括三個整數(shù)，M, N和K，用空格隔開；表示花生田的大小為M * N（1 = M, N = 50），多多采花生的限定時間為K（0 = K = 1000）個單位時間。接下來的M行，每行包括N個非負整數(shù)，也用空格隔開；第i + 1行的第j個整數(shù)Pij（0 = Pij = 500）表示花生田里植株(i, j)下花生的數(shù)目，0表示該植株下

4、沒有花生。 輸出要求 輸出包括T行，每一行只包含一個整數(shù)，即在限定時間內(nèi)，多多最多可以采到花生的個數(shù)。 樣例輸入 6 7 21 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 樣例輸出 37 找規(guī)律得到一個以花生矩陣作為自變量的公式來解決這個問題，是不現(xiàn)實的。 結(jié)果只能是做了才知道。即走進花生地每次要采下一株花生之前，先計算一下剩下的時間夠不夠走到那株花生，采摘，并從那株花生走回到路上。如果時問夠則走過去采摘；如果時間不夠，則采摘活動到此結(jié)束。 設(shè)二維數(shù)組aField存放

5、花生地的信息。然而，用aField00還是aField11對應(yīng)花生地的左上角是值得思考一下的。因為從地里到路上還需要1個單位時間，題目中的坐標又都是從1開始。所以若aField11對應(yīng)花生地的左上角，則從aFieldij點回到路上所需時間就是i，這樣更為方便和自然，不易出錯。解題思路參考程序#include #include#include#includeint T, M, N, K;#define MAX_NUM 55int aFieldMAX_NUM MAX_NUM;main() scanf(“%d, &T); for(int t=0; tT; t+) scanf(“%d%dd”, &M,

6、 &N, &K); /花生地的左上角對應(yīng)的數(shù)組元素是aField11，路的縱坐標是0 for(int m=1; m=M; m+) for(int n=1; n=N; n+) scanf(“d”，&afieldmn); int nTotalPeanuts=0; /摘到的花生總數(shù) int nTotalTime=O; /已經(jīng)花去的時問 int nCuri=0，nCurj; /當前位置坐標， /nCuri代表縱坐標，開始是在路上，所以初值為0 while(nTotalTimeK) /如果還有時間 int nMax=0, nMaxi, nMaxj; /最大的花生數(shù)目， /及其所處的位置 for(int

7、i=1; i=M; i+) /下面這個循環(huán)尋找下一個 /最大花生數(shù)目及其位置 for(int j=1; j=N; j+) if(nMaxaFieIdij) nMax=aFieIdij; nMaxi=i; nMaxj=j; if(nMax = = 0) /地里已經(jīng)沒有花生了 break; if(nCuri = = 0) nCurj=nMaxj; /如果當前位置是在路上，那么 /應(yīng)走到橫坐標nMaxj處，再進人花生地 / 下一行看剩余時間是否足夠走到(nMaxi，nMaxj)處， /摘取花生，并回到路上 if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri) +abs(nMa

8、xj-nCurj) =K) / 下一行加上走到新位置，以及摘花生的時問 nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置 nTotaiPeanuts+=aFieldnMaxinMaxj; aFieldnMaxinMaxj=0; /摘走花生 else break； printf(“%dn”, nTotalPeanuts); 常見問題這個題目應(yīng)該仔細閱讀。往往沒有看到每次只能拿剩下花生株中最大的，而是希望找到一種在規(guī)定時間內(nèi)能夠拿最多花生的組合，把題目變成了另外一道題。沒有讀到?jīng)]有兩

9、株花生株的花生數(shù)目相同”的條件，因此把題目復雜化了。這個題目是假設(shè)猴子在取花生的過程中不會回到大路上，而有些同學思考是否可能在中間回到大路上，因為題目沒說在大路上移動要花時間，所以有可能中途出來再進去摘的花生更多。本題的解法雖然直觀但是有一個弊端就是每次在尋找下一個最大花生植株時，都要遍歷整個矩陣，效率不高。用什么辦法才能高效率地找到下一個最大花生植株?顯示器1、鏈接地址 2、問題描述 你的一個朋友買了一臺電腦。他以前只用過計算器，因為電腦的顯示器上顯示的數(shù)字的樣子和計算器是不一樣，所以當他使用電腦的時候會比較郁悶。為了幫助他，你決定寫一個程序把在電腦上的數(shù)字顯示得像計算器上一樣。 輸入數(shù)據(jù)

10、輸入包括若干行，每行表示一個要顯示的數(shù)。每行有兩個整數(shù)s 和n (1 = s = 10, 0 =n= 99999999)，這里n 是要顯示的數(shù)，s 是要顯示的數(shù)的尺寸。如果某行輸入包括兩個0，表示輸入結(jié)束。這行不需要處理。 輸出要求 顯示的方式是：用s 個-表示一個水平線段，用s 個|表示一個垂直線段。這種情況下，每一個數(shù)字需要占用s+2 列和2s+3 行。另外，在兩個數(shù)字之間要輸出一個空白的列。在輸出完每一個數(shù)之后，輸出一個空白的行。注意：輸出中空白的地方都要用空格來填充。 輸入樣例2 123453 678900 0 輸出樣例一個計算器上的數(shù)字顯示單元，可以看作由以下編號從1 到7 的7 個

11、筆畫組成： 3、解題思路 那么，我們可以說，數(shù)字8 覆蓋了所有的筆畫，數(shù)字7 覆蓋筆畫1、3 和6，而數(shù)字1覆蓋筆畫3、6。注意，每個筆畫都是由s 個-或s 個|組成。 輸出時，先輸出第1 行，即整數(shù)n 中所有數(shù)字里的筆畫1，然后輸出第2 行到第s+1 行，即所有數(shù)字的筆畫2 和筆畫3，接下來是第s+2 行，即所有數(shù)字的筆畫4，再接下來是第s+3行到2s+2 行，就是所有數(shù)字的筆畫 5 和筆畫6，最后的第2s+3 行，是所有數(shù)字的筆畫7。如果某個數(shù)字d 沒有覆蓋某個筆畫m (m = 17)，那么，輸出數(shù)字d 的筆畫m 的時候，就應(yīng)該都輸出空格；如果覆蓋了筆畫m，則輸出s 個-或s 個|，這取決

12、于筆畫m 是橫的還是豎的。解題思路由上思路，解決這道題目的關(guān)鍵，就在于如何記錄每個數(shù)字都覆蓋了哪些筆畫。實際上，如果我們記錄的是每個筆畫都被哪些數(shù)字覆蓋，則程序?qū)崿F(xiàn)起來更為容易。一個筆畫被哪些數(shù)字所覆蓋，可以用一個數(shù)組來記錄，比如記錄筆畫1 覆蓋情況的數(shù)組如下：char n111 = - - -;其中，n1i(i = 09) 代表筆畫1 是否被數(shù)字i 覆蓋。如果是，則n1i 為-，如果否，則n1i為空格。上面的數(shù)組的值體現(xiàn)了筆畫1 被數(shù)字0, 2, 3, 5, 6, 7, 8, 9 覆蓋。對于豎向的筆畫2，由字符 | 組成，則記錄其覆蓋情況的數(shù)組如下：char n211 = | | |;該數(shù)組

13、的值體現(xiàn)了筆畫2 被數(shù)字0, 4, 5, 6, 8, 9 覆蓋。解題思路4、參考程序#include #include char n111=- - -;/筆畫1 被數(shù)字0,2,3,5,6,7,8,9 覆蓋char n211=| | |;/筆畫2 被數(shù)字0,4,5,6,8,9 覆蓋char n311=| |;/筆畫3 被數(shù)字0,1,2,3,4,7,8,9 覆蓋char n411= - -;/筆畫4 被數(shù)字2,3,4,5,6,8,9 覆蓋char n511=| | | | ;/筆畫5 被數(shù)字0,2,6,8覆蓋char n611=| |;/筆畫6 被數(shù)字0,1,3,4,5,6,7,8,9 覆蓋cha

14、r n711=- - - -;/筆畫7 被數(shù)字0,2,3,5,6,8,9 覆蓋int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k; while(1) scanf( %d%s, &s, szNumber); if (s = 0) break; nLength = strlen(szNumber); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫1 nDigit = szNumberi - 0; printf( ); for (j = 0 ; j s ; j+) /一個筆畫由s

15、 個字符組成 printf(%c, n1nDigit); printf( );/兩個空格 printf(n);4、參考程序 for (i = 0 ; i s ; i+) /輸出所有數(shù)字的筆畫2 和筆畫3 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n2nDigit); for (k = 0 ; k s ; k+) printf( ); /筆畫2 和筆畫3 之間的空格 printf(%c , n3nDigit);/有一個空格 printf(n); for (i = 0 ; i nLength ; i+) /輸出所

16、有數(shù)字的筆畫4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/兩個空格 printf(n);4、參考程序4、參考程序 for (i = 0 ; i s ; i+) /輸出所有數(shù)字的筆畫5 和筆畫6 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n5nDigit); for (k = 0 ; k s ; k+) printf( ); /筆畫5 和筆畫6 之間的空格 printf(%

17、c , n6nDigit);/有一個空格 printf(n); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫7 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j 1) l-; a0 = l; 當 ai上的數(shù)據(jù)小于 0 的時候，就要由高位退位了。因為該數(shù)組中下標越大，位數(shù)越高，故當 ai位小于 0時，ai + 1位退位的操作 （以十進制為例）為： ai + 1-; ai += 10;如果 aa0位等于 0，在退位的同時就要考慮a0的值的改變了。此時要減小a0，直到達到準確位數(shù)。 while (aa0 = 0 &

18、a0 1) a0-; 高精度數(shù)加整型數(shù)算法： 將整型加到 a1后，再不斷進位，直到 ai小于 10為止。但是如果 a1+x就已經(jīng)溢出整型的范圍的話，就需要a1+x%10，a2+x/10后再進位。 memcpy(tmp, a, sizeof(tmp); /復制a到tmp 中 int l = 1; tmp1 += x; while (tmpl 9) tmpl + 1 += tmpl / 10; tmpl %= 10; l+; /inc(i) if (l tmp0) tmp0 = l; memcpy(b, tmp, sizeof(b); 高精度數(shù)減整型數(shù)，若高精度數(shù)小于整型，把高精度轉(zhuǎn)化為整型直接減

19、。這只討論高精度數(shù)大于整型。 將高精度數(shù)的對應(yīng)位同 x 對應(yīng)位相減，再進行退位。 memcpy(tmp, a, sizeof(tmp); int l = 1; while (x) tmpl -= x % 10, x /= 10, l+; for (int i = 1; i = tmp0; i+) if (tmpi 1) tmp0-; memcpy(b, tmp, sizeof(b); 斐波那契數(shù)列的準確計算 問題描述：試準確求出斐波那契數(shù)列的第n 項。斐波那契數(shù)列的定義：給出n=61時的數(shù)，如下：1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、15

20、97、2584、4181、6765、10946、17711、28657、46368、75025、121393、196418、317811、514229、832040、1346269、2178309、3524578、5702887、9227465、14930352、24157817、39088169、63245986、102334155、165580141、267914296、433494437、701408733、1134903170、1836311903、2971215073、4807526976、7778742049、12586269025、20365011074、32951280099、

21、53316291173、86267571272、5、225851433717、365435296162、591286729879、956722026041、1548008755920、25、41斐波那契數(shù)列的準確計算 來看一個加法過程：1548008755920+ 2541為了作多位準確計算，設(shè)置a、b、c 三個數(shù)組。 a0、b0存相鄰兩項的個位數(shù)字， a1、b1存儲兩項的十位數(shù)字，其余類推。 1、算法分析斐波那契數(shù)列的準確計算 同一位求和: ci=ai+bi+h，其中h 為前一位相加的進位數(shù)。這里得到的數(shù)ci可能超過一位，求出其進位數(shù)h=ci/l 0作為下一位相加的進位數(shù)，并讓ci=ci%1

22、0。從i=0至m求和全部完成后，即得到一個新項，把b數(shù)組賦給a數(shù)組，c 數(shù)組賦給b數(shù)組，為繼續(xù)求下一項作準備。 當己求出第n項，去掉c數(shù)組的高位0后從高位至低位依次打印各位即為求得的數(shù)列第n 項。 高精度數(shù)加高精度數(shù)對應(yīng)位相加，最后統(tǒng)一進位 memset(tmp, 0, sizeof(tmp); int l = max(a0, b0); for (int i = 1; i = l; i+) tmpi = ai + bi; l+; for (int i = 1; i 9) tmpi + 1+;tmpi - = 10; while (tmpl = 0 & l 1) l-; tmp0 = l; me

23、mcpy(c, tmp, sizeof(c);斐波那契數(shù)列的準確計算 #include #include #define N 1000int aN,bN,cN;int main(void) int h,i,j,n,k; while(scanf(%d,&n)=1) memset(a,0,sizeof(a); memset(b,0,sizeof(a); memset(c,0,sizeof(a); a0=b0=1;/賦初值 k=1;/開始時是1位數(shù)，用作循環(huán)上界 for(i=2;i=n;i+)/一個一個運算 h=0; /開始時進位數(shù)為0 for(j=0;j0) /最后一次單獨處理 cj=h; k+;

24、/位數(shù)增加 for(j=0;j=0;j-) /輸出 printf(%d,bj); printf(n); return 0;大整數(shù)乘法 Description 任給兩個長度不超過100位的大整數(shù)，求兩個數(shù)相乘的精確結(jié)果。 Input 本題有多組輸入數(shù)據(jù)。第一行是輸入數(shù)據(jù)的組數(shù)T，每組數(shù)據(jù)有兩行，分別是兩個非負的大整數(shù)，當數(shù)不為0時，不會出現(xiàn)首位為0的情形。1=T=1;i-)/把數(shù)字倒過來，使得高位在下標在的位置 a i=sl-i-0; 在程序中，為了更好的保存大整數(shù)，用了一個結(jié)構(gòu)體： typedef struct int numberLEN; int len; digit; 用結(jié)構(gòu)體a,b表示兩

25、個乘數(shù)，用c表示積。計算的過程基本上和小學生列豎式做乘法相同。為編程方便，個數(shù)存儲在數(shù)組最低位，而不是下標高的位置。在程序中，可以不急于處理進位，而將進位問題留待最后統(tǒng)一處理。 現(xiàn)以 83549 為例來說明程序的計算過程。解題思路先算8359。59 得到45 個1，39 得到27 個10，89 得到72 個100。由于不急于處理進位，所以8359 算完后，結(jié)果如下：接下來算45。此處45 的結(jié)果代表20 個10，因此要 c1+=20，變?yōu)椋涸傧聛硭?3。此處43 的結(jié)果代表12 個100，因此要 c2+= 12，變?yōu)椋鹤詈笏?48。此處48 的結(jié)果代表 32 個1000，因此要 c3+= 32

26、，變?yōu)椋撼朔ㄟ^程完畢。接下來從 c0開始向高位逐位處理進位問題。c0留下5，把4 加到c1上，c1變?yōu)?1 后，應(yīng)留下1，把5 加到c2上最終使得c 里的每個元素都是1 位數(shù)，結(jié)果就算出來了：規(guī)律：一個數(shù)的第i 位和另一個數(shù)的第j 位相乘所得的數(shù)，一定是要累加到結(jié)果的第i+j 位上。這里i, j 都是從右往左，從0 開始數(shù)。4、參考程序#include #include #define LEN 210typedef struct/記錄數(shù)的長度，減少循環(huán) int numberLEN; int len; digit;void multiply(digit *a, digit *b, digit *

27、c);int main(void) char sLEN; int i,k,n,T; digit a,b,c; scanf(%d,&T);/讀入數(shù)據(jù)個數(shù) getchar();/吸收回車符 for(n=0;nT;n+) gets(s); a.len=strlen(s); for(i=0;ia.len;i+)/把數(shù)字倒過來，使得高位在下標在的位置 a.numberi=sa.len-i-1-0;4、參考程序 gets(s); b.len=strlen(s); for(i=0;i=0;i-) printf(%d,c.numberi); printf(n); return 0;/a,b是乘數(shù)，c是積voi

28、d multiply(digit *a, digit *b, digit *c) int i,j,t; if(a-len=1 & a-number0=0) | (b-len=1 & b-number0=0)/其中一個數(shù)為0 c-len=1; c-number0=0; return; 4、參考程序 c-len=a-len+b-len;/先乘，后進位 memset(c-number,0,c-len*sizeof(int);/清零 for(i = 0; i len; i+) /逐位作乘法 for(j = 0; j len; j+) c-numberi + j += a-numberj * b-num

29、beri; for(i = 0; i len-1; i+)/統(tǒng)一進位 if(c-numberi = 10) c-numberi+1+=c-numberi/10; c-numberi%=10; /積的最大長度為兩數(shù)長度之和，最小為之和減1 if(c-numberi = 0) c-len-;大整數(shù)除法1、鏈接地址 2、問題描述 求兩個大的正整數(shù)相除的商 輸入數(shù)據(jù) 第1 行是測試數(shù)據(jù)的組數(shù)n，每組測試數(shù)據(jù)占2 行，第1 行是被除數(shù)，第2 行是除數(shù)。每組測試數(shù)據(jù)之間有一個空行，每行數(shù)據(jù)不超過100 個字符 輸出要求 n 行，每組測試數(shù)據(jù)有一行輸出是相應(yīng)的整數(shù)商 輸入樣例3243733592649393

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

31、86 減去23，夠減8 次，因此最終商就是328。 所以本題的核心是要寫一個大整數(shù)的減法函數(shù)，然后反復調(diào)用該函數(shù)進行減法操作。 計算除數(shù)的10 倍、100 倍的時候，不用做乘法，直接在除數(shù)后面補0 即可。3、解題思路4、參考程序#include #include #define MAX_LEN 200char szLine1MAX_LEN + 10;char szLine2MAX_LEN + 10;int an1MAX_LEN + 10; /被除數(shù), an10對應(yīng)于個位int an2MAX_LEN + 10; /除數(shù), an20對應(yīng)于個位int aResultMAX_LEN + 10; /存放

32、商，aResult0對應(yīng)于個位/長度為 nLen1 的大整數(shù)p1 減去長度為nLen2 的大整數(shù)p2/結(jié)果放在p1 里，返回值代表結(jié)果的長度/如不夠減返回-1，正好減完返回 0int Substract( int * p1, int * p2, int nLen1, int nLen2) int i; if( nLen1 = 0; i - ) if( p1i p2i ) break; /p1p2 else if( p1i p2i ) return -1; /p1p2 for( i = 0; i =nLen2 時，p2i 0 p1i -= p2i; if( p1i = 0 ; i- ) if(

33、p1i )/找到最高位第一個不為0 return i + 1; return 0;/全部為0，說明兩者相等4、參考程序int main() int t, n; scanf(%d, &n); for( t = 0; t = 0 ; i -) an1j+ = szLine1i - 0; int nLen2 = strlen(szLine2); for( j = 0, i = nLen2 - 1;i = 0 ; i -) an2j+ = szLine2i - 0; if( nLen1 0) for( i = nLen1 -1; i = nTimes; i - ) an2i = an2i-nTimes

34、;/朝高位移動 for( ; i = 0; i-)/低位補0 an2i = 0; nLen2 = nLen1; for( j = 0 ; j = 0) nLen1 = nTmp; aResultnTimes-j+; /每成功減一次，則將商的相應(yīng)位加1 參考程序 /下面輸出結(jié)果，先跳過高位0 for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - ); if( i = 0) for( ; i=0; i-) printf(%d, aResulti); else printf(0); printf(n); return 0;麥森數(shù)1、鏈接地址 2、問題描述

35、形如2P-1 的素數(shù)稱為麥森數(shù)，這時P 一定也是個素數(shù)。但反過來不一定，即如果P 是個素數(shù)。2P-1 不一定也是素數(shù)。到1998 年底，人們已找到了37 個麥森數(shù)。最大的一個是P=3021377，它有909526 位。麥森數(shù)有許多重要應(yīng)用，它與完全數(shù)密切相關(guān)。 你的任務(wù)：輸入P (1000P3100000) , 計算2p-1 的位數(shù)和最后500 位數(shù)字（用十進制高精度數(shù)表示） 輸入數(shù)據(jù) 只包含一個整數(shù)P(1000P0，考慮p 的二進制形式，則不難得到：這里，ai 要么是1，要么是0。3、解題思路 因而： 計算2p 的辦法就是：先將結(jié)果的值設(shè)為1，計算21。如果a0 值為1，則結(jié)果乘以21；計算

36、22，如果a1 為1，則結(jié)果乘以22；計算24，如果a2 為1，則結(jié)果乘以24；總之，第i 步(i 從0 到n，an 是1)就計算22i，如果ai 為1，則結(jié)果就乘以22i。每次由22i22i就能算出22(i+1)。由于p可能很大，所以上面的乘法都應(yīng)該使用高精度計算。由于題目只要求輸出500 位，所以這些乘法都是只須算出末尾的500 即可。解題思路在前面的高精度計算中，我們用數(shù)組來存放大整數(shù)，數(shù)組的一個元素對應(yīng)于十進制大整數(shù)的一位。本題如果也這樣做，就會超時。為了加快計算速度，可以用一個數(shù)組元素對應(yīng)于大整數(shù)的4 位，即將大整數(shù)表示為10000 進制，而數(shù)組中的每一個元素就存放10000 進制數(shù)

37、的1 位。例如，用int 型數(shù)組 a 來存放整數(shù)，那么只需兩個數(shù)組元素就可以了，a0=3384, a1=637。由于只要求結(jié)果的最后500 位數(shù)字，所以我們不需要計算完整的結(jié)果，只需算出最后500 位即可。因為用每個數(shù)組元素存放十進制大整數(shù)的4 位，所以本題中的數(shù)組最多只需要125 個元素。解題思路4、參考程序#include #include #define LEN 125 /每數(shù)組元素存放4 位，數(shù)組最多需要125 個元素#include /計算高精度乘法 a * b, 結(jié)果的末500 位放在a 中void Multiply(int* a, int* b) int i, j; int nC

38、arry; /存放進位 int nTmp; int cLEN; /存放結(jié)果的末500 位 memset(c, 0, sizeof(int) * LEN); for (i=0;iLEN;i+) nCarry=0; for (j=0;jLEN-i;j+) nTmp=ci+j+aj*bi+nCarry; ci+j=nTmp%10000; nCarry=nTmp/10000; memcpy( a, c, LEN*sizeof(int);4、參考程序int main(void) int i; int p; int anPowLEN; /存放不斷增長的2 的次冪 int aResultLEN; /存放最終結(jié)果的末500 位 scanf(%d, & p); printf(“%dn”, (int)(p*log10(2.0)+1); /下面將2 的次冪初始化為2(20)(ab 表示a 的b 次方)， / 最終結(jié)果初始化為1 anPow0=2; aResult0=1; for (i=1;i0) /下面計算2 的p 次方 / p = 0 則說明p 中的有效位都用過了，不需再算下去 if ( p & 1 ) /判斷此時p 中最低位是否為1 Multiply(aResult, anPow); p=1; Multiply(anPow,