UVA 10334 - Ray Through Glasses(高精度斐波那契)

Ray Through Glasses

Suppose we put two panes of glass back-to-back. How many ways are there for light rays to pass through or be reflected after changing direction n times Following figure shows the situations when the value of nis 0, 1 and 2.

Input

It is a set of lines with an integer n where 0 <= n <= 1000 in each of them.

Output

For every one of these integers a line containing as described above.

Sample Input

0

1

2

Sample Output

1

2

3

题意：斐波那契，前1000项。

思路：用高精度去写

代码：

#include   
#include   
  
int n;  
int f[1005][35];  
  
void solve() {  
    memset(f, 0, sizeof(f));  
    f[0][0] = 1; f[1][0] = 2;  
    for (int i = 2; i <= 1000; i ++) {  
        for (int j = 0; j < 35; j ++) {  
            f[i][j] += f[i - 1][j] + f[i - 2][j];  
            f[i][j + 1] += f[i][j] / 100000000;  
            f[i][j] %= 100000000;  
        }  
    }  
  
}  
  
void print(int n) {  
    int i, j;  
    for (i = 34; i >= 0; i --) {  
        if (f[n][i] != 0)  
            break;  
    }  
    printf("%d", f[n][i]);  
    for (j = i - 1; j >= 0; j --)  
        printf("%08d", f[n][j]);  
    printf("\n");  
}  
  
int main() {  
    solve();  
    while (~scanf("%d", &n)) {  
        print(n);  
    }  
    return 0;  
}