大數問題二

一、#713 ─ Adding Reversed Numbers (修正版)

題目:按這裡

說明:輸入兩個整數,將兩數分別反轉後再相加,相加後的結果再反轉後輸出。(本題修正為該兩個整數最大可到 200 位數)

這一題之前有寫過,不過這個農曆年期間它的題目做了修正,要求這兩個整數最大可達到 200 位數,於是我們要改用大數的寫法。

我們把之前寫好的大數相加的程式拿出來修改,我們有兩種做法,第一種做法是再寫一個 Rev() 函數來做反轉(Reverse)的處理,另一種做法,則是在 Input()Print() 函數直接在輸入及印出來的時候就做反轉,這一題,就留給各位同學自己思考。

下面舉一個例子給各位做參考: 97581 + 1284 = 432

Input() 函數的圖解:

字串

'9'

'7'

'5'

'8'

'1'

0

0

0

陣列

9

7

5

8

1

0

0

0

Add() 及 Print() 函數的圖解:

A

9

7

5

8

1

0

0

0

0

B

1

2

8

4

0

0

0

0

0

A+B

0

0

4

3

2

0

0

0

0

如果真的想不出來,就按這裡參考老師的程式吧。

 

二、#623 ─ 500!

題目:按這裡

說明:輸入一個正整數 N ( N<=1000 ),輸出兩行,第一行為之前輸入的正整數 N 後面加上 !,第二行印出 N! 的值(最大 2568 位數)。

要計算 N!,可以模仿之前大數相乘的做法,不過幸運的是,我們要乘上的數最大只有 500,因此只要其中一個使用大數即可。因為如果每次輸入一個數字,就讓系統從 1 再算一次,會花上很多時間,甚至會讓系統的時間爆掉。(老師也爆了很多次!!)所以我們先用一個二維陣列來存放 N! 的結果,接下來要求那一個數,皆可以直接把答案印出來,我們用一個 Calc() 函數完成這個動作。因為 9 × 1000 為 9000,所以這一題我們的大數改用 int 來存放,並把它寫在 main() 的外面,這個我們稱之為外部變數,可以讓所有的函數直接使用它:

#include <stdio.h>

#include <string.h>

#define LEN 160

#define MAX 100

int Num[MAX+1][LEN];

上面的 LEN 及 MAX,原本應該是 2600 及 1000,因為 Turbo C++ 無法接受這麼大的陣列,所以我們先以 100! 大約為 158 位數,等程式測試完成後,在 ACM 上傳時再改回 2600 及 1000。下面先看到 Num 陣列在 10! 之前的圖解:

0!

1

0

0

0

0

0

0

0

0

1!

1

0

0

0

0

0

0

0

0

2!

2

0

0

0

0

0

0

0

0

3!

6

0

0

0

0

0

0

0

0

4!

4

2

0

0

0

0

0

0

0

5!

0

2

1

0

0

0

0

0

0

6!

0

2

7

0

0

0

0

0

0

7!

0

4

0

5

0

0

0

0

0

8!

0

2

3

0

4

0

0

0

0

9!

0

8

8

2

6

3

0

0

0

10!

0

0

8

8

2

6

3

0

0

接下來我們看到 Calc() 函數,我們先把 0! 及 1! 設成 1,接下來從 2! 開始,就把它上一格乘上該階乘的倍數(例如 5! 則乘 5),乘完後再從個位數開始往前進位:

void Calc()

{

 int i, j;

 for(i=0; i<MAX; i++)

   for(j=0; j<LEN; j++)

     Num[i][j]=0;

 Num[0][0]=1;

 Num[1][0]=1;

 for(i=2; i<=MAX; i++)

   for(j=0; j<LEN; j++) {

     Num[i][j]+=Num[i-1][j]*i;

     if(Num[i][j]>=10) {

       Num[i][j+1]+=Num[i][j]/10;

       Num[i][j]%=10;

     }

   }

}

接下來,我們希望寫一個傳入一個整數 n,則印出第 n 個大數的值的函數 Print()

void Print(int n)

{

 int i;

 printf("%d!\n", n);

 for(i=LEN-1; i>0; i--)

   if(Num[n][i]!=0) break;

 for(; i>=0; i--)

   printf("%d", Num[n][i]);

 printf("\n");

}

最後我們改寫我們的 main() 函數:

void main()

{

 int n;

 Calc();

 while(1) {

   if(scanf("%d", &n)<1) break;

   Print(n);

 }

}

要上傳到 ACM 之前,記得把一開頭的 LEN 及 MAX 改回 2600 及 1000。

 

三、#10220 ─ I Love Big Numbers!

題目:按這裡

說明:輸入一個正整數 N ( N<=1000 ),輸出 N! 中每個位數的總和。

這一題和上一題很類似,唯一的差別是輸出的是每個位數的總合而不是它的值。最快的方式,就是拿上一題的程式碼,把 Print() 函數改一下就行了。不過,這一題只要有所有位數的和,不需要每一個長整數都記錄下來,所以用之前的二維陣列有點浪費,我們可以把它改成一維陣列,然後修改 Calc() 函數,至於 Print() 函數則可以拿掉,因為只要用 printf("%d\n", Nu[n]); 一行程式就解決了。

這一題同樣留給各位同學自己去想,如果真的想不出來,就按這裡參考老師的程式吧。

 

上一頁

首頁

下一頁