本题要求实现求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

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

#include <stdio.h>

int fib(int n)
{
        int a , b , i , s                                                       ;
        for(s = a = b = 1 , i = 3 ; i < n + 1 ; a = b , b = s , i ++) s = a + b ;
        return s                                                                ;
}

int main(void)
{
        int n                                                                   ;
        scanf("%d" , & n)                                                       ;
        printf("%d\n" , fib(n))                                                 ;
}

Burnling

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

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

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

int A[3];
A[1] = 1;
A[2] = 1;
for(int i = 0;i<=n;i++){
    A[0] = A[1];
    A[1] = A[2];
    A[2] = A[0] + A[1]
}
printf("%d",A[2]);

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