Problem Description

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.

F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)

Your task is to take a number as input, and print that Fibonacci number.

 

Input

Each line will contain an integers. Process to end of file.

 

Output

For each case, output the result in a line.

 

Sample Input

100

 

Sample Output

4203968145672990846840663646Note:No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

1 #include 
      
        2 #include 
       
         3 int f[10000][505] = {
    0}; 4 int main() 5 { 6     int n, carry, sum, i, j, length; 7     //f[number][0] is the length of the number 8     f[1][0] = 1; 9     f[1][1] = 1;10     f[2][0] = 1;11     f[2][1] = 1;12     f[3][0] = 1;13     f[3][1] = 1;14     f[4][0] = 1;15     f[4][1] = 1;16     while (scanf("%d", &n) != EOF)17     {18         if (n < 5)19         {20             puts("1");21             continue;22         }23         for (i = 5; i <= n; i++)24         {25             f[i][0] = f[i - 1][0];26             carry = 0;27             //splite the number by four28             for (j = 1; j <= f[i][0]; j++)29             {30                 sum = f[i -1][j] + f[i - 2][j] + f[i - 3][j] + f[i - 4][j] + carry;31                 f[i][j] = sum % 10000;32                 carry = sum / 10000;33             }34             //if the carry is not zero, then the length must plus one35             if (carry != 0)36             {37                 f[i][0]++;38                 f[i][j] = carry;39             }40         }41         //formatted printing42         length = f[n][0];43         printf("%d", f[n][length]);44         for (i = length - 1; i >= 1; i--)45             printf("%04d",f[n][i]);46         printf("\n");47     }48     return 0;49 }
       
      

Main points

firstly, you can't use string in C and if the array is big, you must declare in global variable.

secondly, the question is splitting the number by four, or you will accure Runtime Error (ACCESS_VIOLATION). The one diffence with spliting by one is you should use %d firstly, then use %04d.