hdu 1250 Hat's Fibonacci(高精度加法)

hdu 1250 Hat's Fibonacci(高精度加法)

题目：​​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

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

2005位的话用高精度计算，算到第8000多应该就够了。

#include #include using namespace std;const int maxn=2008;char f[9000][maxn+2]; //为什么取9000？int main(){ int i=5,p=maxn,n,num; f[1][maxn]=f[2][maxn]=f[3][maxn]=f[4][maxn]=1; while(f[i-1][1]<=1){ for(int j=maxn;j>=p;j--){ f[i][j]=f[i-1][j]+f[i-2][j]+f[i-3][j]+f[i-4][j]; //****** } for(int j=maxn;j>=p;j--){ int c=f[i][j]/10; if(c>0){ f[i][j]=f[i][j]%10; f[i][j-1]+=c; } } if(f[i][p-1]>0)p--; i++; } while(cin>>n){ for(int k=0;k<=maxn;k++){ if(f[n][k]!=0){ num=k; break; } } for(int k=num;k<=maxn;k++)printf("%d",f[n][k]); puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。