0

试图开发一个快速找到斐波那契值的代码。但问题是当输入为 1000000 时，我得到 SIGSEGV 错误。另外，从这里的其他问题中，我知道这可能是因为堆栈内存在运行时超出限制。我想这就是这里的情况。

#include<stdio.h>
unsigned long long int a[1000001] = {0};
unsigned long long int fib(int n)
{
    unsigned long long int y;
    if(n==1 || n==0)
        return n;
    if (a[n] != 0)
        return a[n];
    else
    {
      y=fib(n-1)+fib(n-2);
      a[n] = y;
    }
    return y;
}
main()
{
    int N;
    unsigned long long int ans;
    a[0] = 1;
    a[1] = 1;
    scanf(" %d",&N);
    ans = fib(N+1);
    printf("%llu",ans);
}

如何为输入值 1000000 修复此代码？

4

2 回答 2

2

这是一种更好的方法（仍然可以显着改进），它将为您计算斐波那契数：

unsigned long long Fibonacci(int n)
{ 
    unsigned long long last[2] = { 0, 1 }; // the start of our sequence

    if(n == 0)
        return 0;

    for(int i = 2; i <= n; i++)
        last[i % 2] = last[0] + last[1];

    return last[n % 2];
}

但是，您将无法用它计算第100 万个斐波那契数，因为这个数字比unsigned long long.

于 2013-02-02T00:04:52.283 回答
1

不要使用堆栈，而是使用您自己的变量来跟踪状态。本质上，使用您自己的代码进行函数调用和返回。

最好的方法实际上就是将算法完全切换到一种有效的算法。例如，要计算 fib(6)，您的代码会计算 fib(4) 两次，一次是在 fib(5) 询问时，一次是在 fib(6) 询问时。

于 2013-02-01T23:49:38.867 回答