杰拉斯的博客

[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

  1. 5
  2. 6
  3. 7
  4. 8
  5. 9
  6. 40

Sample Output

  1. 5
  2. 8
  3. 13
  4. 21
  5. 34
  6. 102334155

Source

ZJUT1029

如果我们使用递归分治法的思想,可以得到代码:

  1. #include<stdio.h>
  2. int f(int n){
  3. if(n == 0)
  4. return 0;
  5. else if(n == 1)
  6. return 1;
  7. return f(n - 1) + f(n - 2);
  8. }
  9. int main(){
  10. int n;
  11. while(scanf("%d", &n) != EOF){
  12. printf("%d\n", f(n));
  13. }
  14. return 0;
  15. }

但这段代码的结果必定是TLE,因为问题的子问题大量重复,即:

  1. f(n)
  2.  = f(n-1) + f(n-2)
  3.  = f(n - 2) + f(n - 3) + f(n - 1) + f(n - 2)
  4.  = f(n - 3) + f(n - 4) + f(n - 4) + f(n - 5) + f(n - 2) + f(n - 3) + f(n - 3) + f(n - 4)
  5. = ...

这样下去,当n比较大时,运算量将是极为恐怖的,我们可以用经典的空间换时间的思想,将数列前两位先储存到数组中,后面的斐波那契数直接通过已储存的数字相加得出,用户输入时直接从数组读取,这样便可以节省出大量的时间:

  1. #include<stdio.h>
  2. int main(){
  3. int f[47];
  4. f[0] = 0;
  5. f[1] = 1;
  6. for(int i = 2; i < 47; ++i){
  7. f[i] = f[i - 1] + f[i - 2];
  8. }
  9. int n;
  10. while(scanf("%d", &n) != EOF){
  11. printf("%d\n", f[n]);
  12. }
  13. return 0;
  14. }

如需转载请注明出处:杰拉斯的博客

相关文章

当前暂无评论 »