高中生程式解題系統：c121: 00495 - Fibonacci Freeze

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 http://zerojudge.tw/ShowProblem?problemid=c121。

此題需要用到大數運算的做法，程式碼是用字串來處理。

程式碼：

#include <iostream>
#include <string>

// Fibonacci

using namespace std;

string addition(string s, string s2)                    // 加法
{
    int len, lenS, MaxL, i, a, b, c = 0;
    string BNstr(s2);

    // 去掉多餘的數字０
    len = BNstr.length();                // 讀取被加數的長度
    lenS = s.length();                    // 讀取加數的長度
    for (i = 0; i < len-1; i++)
       if (BNstr[0] == '0')
           BNstr.erase(BNstr.begin());
       else
           break;
    for (i = 0; i < lenS-1; i++)
       if (s[0] == '0')
           s.erase(s.begin());
       else
           break;

    len = BNstr.length();
    lenS = s.length();
    MaxL = (len > lenS)?len:lenS;

    for (i = 0; i < MaxL; i++) {
       if (i < len) a = BNstr[len-1-i]-'0';
               else a = 0;
       if (i < lenS) b = s[lenS-1-i]-'0';
                else b = 0;
       if (i < len) BNstr[len-1-i] = (a+b+c)%10+'0';
               else BNstr.insert(BNstr.begin(),(a+b+c)%10+'0');
       c = (a+b+c)/10;
    }
    BNstr.insert(BNstr.begin(),c+'0');

    // 去掉多餘的數字０
    len = BNstr.length();
    for (i = 0; i < len-1; i++)
       if (BNstr[0] == '0')
           BNstr.erase(BNstr.begin());
       else
           break;

    return BNstr;
}

int main(void){
    const int SIZE = 5001;
    string Fibonaccinum[SIZE] = { "0", "1" };

    for( int i = 2; i < SIZE; i++ )
    {
        Fibonaccinum[i] = addition(Fibonaccinum[i-1], Fibonaccinum[i-2]);
    }


    int n;
    while( cin >> n )
    {
        cout << "The Fibonacci number for " << n << " is " << Fibonaccinum[n] << endl;
    }

    return 0;
}