http://uva.onlinejudge.org/external/105/10579.html

bpe11487.cpp

#include <iostream>
using namespace std;

int main (void)
{
    int n;
    while (cin >> n)
    {
        if (n == 0) break;
        else if (n == 1) cout << "1" << endl;
        else if (n == 2) cout << "1" << endl;
        else
        {
            int r[1024] = {0}; //第 n 項的結果
            int a[1024] ={0};  //fib 的前項
            int b[1024] ={0};  //fib 的後項
            a[0] = 1; b[0] = 1;//fib 初始化
            int lenb = 1, carry = 0, lenr = 0; 

            for (int i = 3; i <= n; i++)
            {
                carry = 0;
                lenr = 0; //計算新的項的結果
        
                for (int j = 0; j < lenb; j++)
                {
                    carry = b[j] + a[j] + carry;
                    r[lenr] = carry % 10;
                    lenr++;
                    carry = carry / 10;
                }

                if (carry != 0) //如果最後一次有進位
                {
                    r[lenr] = carry % 10;
                    lenr++;
                }

                for (int j = 0; j < lenb; j++) a[j] = b[j]; //後項結果交給前項
                
                for (int j = 0; j < lenr; j++) b[j] = r[j]; //後項結果交給前項
                lenb = lenr; //把目前結果的長度給 b
            }

            for (int i = lenr-1; i >= 0; i--) 
                cout << r[i]; //反序印出 因為lsb在[0]
            cout << endl;
        }
    }
    return 0;
}