[ACM_ZJUT_1029]斐波那契数列
杰拉斯 | 时间:2012-04-03, Tue | 17,903 views编程算法
Fibonacci数
Time Limit:1000MS Memory Limit:32768K
Description
有一些整数(≤46),输出以这些整数为序数的第n项fibonacci数。文件中的数据可能上万,但要求运行时间不超过1秒钟。
注:f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2).
Sample Input
- 5
- 6
- 7
- 8
- 9
- 40
Sample Output
- 5
- 8
- 13
- 21
- 34
- 102334155
Source
- #include<stdio.h>
- int f(int n){
- if(n == 0)
- return 0;
- else if(n == 1)
- return 1;
- return f(n - 1) + f(n - 2);
- }
- int main(){
- int n;
- while(scanf("%d", &n) != EOF){
- printf("%d\n", f(n));
- }
- return 0;
- }
但这段代码的结果必定是TLE,因为问题的子问题大量重复,即:
- f(n)
- = f(n-1) + f(n-2)
- = f(n - 2) + f(n - 3) + f(n - 1) + f(n - 2)
- = f(n - 3) + f(n - 4) + f(n - 4) + f(n - 5) + f(n - 2) + f(n - 3) + f(n - 3) + f(n - 4)
- = ...
这样下去,当n比较大时,运算量将是极为恐怖的,我们可以用经典的空间换时间的思想,将数列前两位先储存到数组中,后面的斐波那契数直接通过已储存的数字相加得出,用户输入时直接从数组读取,这样便可以节省出大量的时间:
- #include<stdio.h>
- int main(){
- int f[47];
- f[0] = 0;
- f[1] = 1;
- for(int i = 2; i < 47; ++i){
- f[i] = f[i - 1] + f[i - 2];
- }
- int n;
- while(scanf("%d", &n) != EOF){
- printf("%d\n", f[n]);
- }
- return 0;
- }
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »