本题要求实现求Fabonacci数列项的函数。所谓Fibonacci数列就是满足任一项数字是前...

匿名miss洁

#include <stdio.h>

int fib( int n );

int main()
{
    int n;

    scanf("%d", &n);
    printf("%d\n", fib(n));

    return 0;
}
int fib(int n)
{
  static int r;
    if(n==1||n==2)
        r=1;
    else
    r=fib(n-1)+fib(n-2);
    return r;
}//
为啥n取最大边界时时显示运行超时？？？
大佬帮帮孩子吧!!!

番杰

当n是比较小的数值时，程序可以正常用吧；
如果是这样的话，就是电脑或是编译器的问题啦，
数据太大了，处理时间太长了，然后就失败了呗。

jackz007

     如果是超时的话可能和递归有关，试试这个代码：

1. #include <stdio.h>
   
2. 
   
3. int fib(int n)
   
4. {
   
5.         int a , b , i , s                                                       ;
   
6.         for(s = a = b = 1 , i = 3 ; i < n + 1 ; a = b , b = s , i ++) s = a + b ;
   
7.         return s                                                                ;
   
8. }
   
9. 
   
10. int main(void)
    
11. {
    
12.         int n                                                                   ;
    
13.         scanf("%d" , & n)                                                       ;
    
14.         printf("%d\n" , fib(n))                                                 ;
    
15. }

复制代码

Burnling

递归容易超时，因为存在大量重复运算（O(2^N)的时间复杂度）
可以用递推，即

1. int A[5000];
   
2. A[0] = 1;
   
3. A[1] = 1;
   
4. for(int i = 2;i<n;i++){
   
5.     A[i] = A[i-1] + A[i-2];
   
6. }

复制代码

如果出现MLE，即爆空间，可以用滚动数组
即

1. int A[3];
   
2. A[1] = 1;
   
3. A[2] = 1;
   
4. for(int i = 0;i<=n;i++){
   
5.     A[0] = A[1];
   
6.     A[1] = A[2];
   
7.     A[2] = A[0] + A[1]
   
8. }
   
9. printf("%d",A[2]);

复制代码

还有就是如果数取得特别大（比如5000）
记得写高精度