Problem 495 Fibonacci Freeze，大數費氏級數

此題為大數題，只需用到大數中的加法就可以了。

還是不例外，創建一個結構(struct)來使用：

#define LEN 5001
#define NUMLEN 1050

struct FibNum
{
    int num[NUMLEN];
    int length;
};

struct FibNum FN[LEN];

將第0個索引的num設定為0，第1個索引的num設定為1：

FN[0].num[0] = 0, FN[0].length = 0, 
FN[1].num[0] = 1, FN[1].length = 0;

接著利用Fib(0) = 0、Fib(1) = 1，當n > 2，Fib(n) = Fib(n-1) + Fib(n-2)的觀念，用大數加法算出到5000之內的Fib值，順便紀錄長度：

int i, j, k, n;

for (i = 2; i < LEN; i ++)
{
     for (j = 0; j < NUMLEN; j ++)
     {
         FN[i].num[j] += FN[i - 1].num[j] + FN[i - 2].num[j];
         if (FN[i].num[j] >= 10)
            FN[i].num[j + 1] ++, FN[i].num[j] %= 10;
     }
     for (j = NUMLEN - 1; ; j--)
         if (FN[i].num[j] > 0)
            break;
     FN[i].length = j ;       
}

最後，只須對應輸入值將大數取出就行了：

while (1)
{
     if (scanf("%d", &n) < 1) break;
     printf("The Fibonacci number for %d is ", n);
     for (i = FN[n].length ;i >= 0 ; i--)
          printf("%d", FN[n].num[i]);
     printf("\n");
}

不過成效不太好，用了0.368秒，我相信會有更好的方法。
By David.K

p495題目連結
回ACM題庫目錄
回首頁