大數問題二

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

題目：按這裡。

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

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

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

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

Input() 函數的圖解：

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

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

二、#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! 之前的圖解：

接下來我們看到 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]); 一行程式就解決了。

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