【UVa】495 - Fibonacci Freeze

Problem here

Problem

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …) are defined by the recurrence:

eqnarray20

Write a program to calculate the Fibonacci Numbers.

INPUT&OUTPUT

The input to your program would be a sequence of numbers smaller or equal than 5000, each on a separate line, specifying which Fibonacci number to calculate.

Your program should output the Fibonacci number for each input value, one per line.

Sample

input

5 
7 
11

output

The Fibonacci number for 5 is 5 
The Fibonacci number for 7 is 13 
The Fibonacci number for 11 is 89

Solution

這題要用大數加法才不會WA

#include <iostream>
using namespace std;
int f[5001][5001] = {0};

int main(){
    f[1][0] = 1;
    for(int i = 2; i <= 5000; i++){
        for(int j = 0; j < 5001; j++){
            f[i][j] += f[i-1][j] + f[i-2][j];
            f[i][j+1] += f[i][j]/10;
            f[i][j] %= 10;
        }
    }
    int n;
    while(cin >> n){
        cout << "The Fibonacci number for " << n << " is "; 
        int i;
        for( i = 5000 ; i >= 0 ; i-- )
            if( f[n][i] )
             break;
        if( i == -1 )
          cout << 0;
        else
          for( ; i >= 0 ; i-- )
            cout << f[n][i];
        cout << endl;
    }
    return 0;
}