杭电_ACM_Hat's Fibonacci

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

Sample Output

4203968145672990846840663646


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

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 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 four
28             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 one
35             if (carry != 0)
36             {
37                 f[i][0]++;
38                 f[i][j] = carry;
39             }
40         }
41         //formatted printing
42         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.