ZeroJudge 解題筆記：c121. 00495 - Fibonacci Freeze

作者：王一哲
日期：2026年3月14日


ZeroJudge 題目連結：c121. 00495 - Fibonacci Freeze

解題想法

由於題目要求計算到費氏數列第 5000 項，需要用到大數加法，如果用 Python 解題可以直接算，如果用 C++ 則要自己寫大數加法的函式。

Python 程式碼

使用時間約為 8 ms，記憶體約為 4.1 MB，通過測試。

import sys

fib = [0]*5001
fib[1] = 1
for i in range(2, 5001):
    fib[i] = fib[i-1] + fib[i-2]

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    print(f"The Fibonacci number for {n:d} is {fib[n]:d}")

C++ 程式碼

使用時間約為 17 ms，記憶體約為 4.2 MB，通過測試。

#include <iostream>
#include <algorithm>
using namespace std;

string big_add(string a, string b) {
    int n = (int)a.size(), m = (int)b.size();
    if (n < m) {  // 確保 n 大於 m
        swap(n, m);
        swap(a, b);
    }
    for(int i = 0; i < n-m; i++) {
        b = "0" + b;  // b 前面補 0
    }
    string c;
    int carry = 0;
    for(int i=n-1; i>=0; i--) {
        int d = a[i] - '0' + b[i] - '0' + carry;
        if (d >= 10) {
            carry = 1;
            d -= 10;
        } else {
            carry = 0;
        }
        c += char(d + '0');
    }
    if (carry == 1) {
        c += "1";
    }
    reverse(c.begin(), c.end());
    return c;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string fib[5001];
    fib[0] = "0";
    fib[1] = "1";
    for(int i=2; i<=5000; i++) {
        fib[i] = big_add(fib[i-1], fib[i-2]);
    }

    int n;
    while(cin >> n) {
        cout << "The Fibonacci number for " << n << " is " << fib[n] << "\n";
    }
    return 0;
}