Fibonacci Numbers
memory limit: 65536KB time limit: 500MS
accept: 22 submit: 29
Description
A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.
f(1) = 1, f(2) = 1, f(n > 2) = f(n - 1) + f(n - 2)
Your task is to take a number as input, and print that Fibonacci number.
Input
One integer i
Output
Output the i-th Fibonacci number.
Sample Input
100
Sample Output
354224848179261915075
Hint
No generated Fibonacci number in excess of 1000 digits will be in the test data, i.e. f(20) = 6765 has 4 digits.
Source
ZQUCPC个人赛5
Author
Waterloo local
题意：
输出斐波那契数列的第n项。
错误做法：
打表时数组开小了。
问题的分析与解题思路：
这个题以前做过，需要用高精度解决。预先打表，然后根据输入的数输出即可。
AC代码：
#include<stdio.h> #include<string.h> int a[10000][300]; int main() { int i,j,n,b,k,s; //memset(a[1],0,sizeof(a[1])); //memset(a[2],0,sizeof(a[2])); a[1][299]=1; a[2][299]=1; //初始化第一二项，他们的值为1 for(i=3;i<10000;i++) { //memset(a[i],0,sizeof(a[1])); for(j=299;j>0;j--) { a[i][j]+=a[i-1][j]+a[i-2][j];//每项的每一位都是由前两项对应位置的数值相加得到的。 while(a[i][j]>9999) //每个最大存9999，超出的前一位加1 { a[i][j]-=10000; a[i][j-1]++; } } } while(scanf("%d",&n)!=EOF) { for(i=1;i<300;i++) //找到该项的第一个非0位置 if(a[n][i]) break; for(j=i;j<300;j++) { if(j!=i) //对除第一个位置的其他位置，如果不足四位，说明之前的为0，则用0补足四位。 { b=a[n][j]; s=0; while(b) { s++; b/=10; } if(s<4) for(k=0;k<4-s;k++) printf("0"); } printf("%d",a[n][j]); } printf("/n"); } return 0; }
算法复杂度分析：
时间复杂度是o(n^2)
算法的优缺点分析和改进：
可以提高数组的利用率，或者其他的高精度保存方法来提高效率。
总结：
水题一道，之前做这题时学会了高精度的处理。
