[ACM_ZJUT_1029]斐波那契数列
杰拉斯 | 时间:2012-04-03, Tue | 17,725 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; }
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »