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) を 2 回計算します。1 回目は fib(5) が要求するとき、もう 1 回は fib(6) が要求するときです。

于 2013-02-01T23:49:38.867 に答える