3

数値がフィボナッチ数であるかどうかを再帰的にチェックするプログラムを作成する必要があります。これと同じ作業を繰り返し行うのは簡単です。また、再帰的に n 番目のフィボナッチ数を見つけるのは簡単ですが、再帰を使用して数値がフィボナッチかどうかを確認する方法に行き詰まっています。n 番目の fib を見つけるコードは次のとおりです。番号：

int fib(int n){
    if (n <= 1){
       return n;
    }else {
       return (fib(n-1) + fib (n-2));
    }
}

どうすればよいかわからないのは、上記のコードを変更して、特定の数値がフィボナッチであるかどうかを確認する方法です。

4

4 に答える 4

5

伝統的な方法は、ゲッセルの検定を使用することです。5N 2 + 4または5N 2 – 4が平方数である場合に限り、Nはフィボナッチ数です。これについては、この SO の質問およびこの SOの質問 で説明されています。こちらにも例がありますが、このページには Python のコードがあります (わかりやすいですが)。

さて、特に再帰を使用するように求められた場合... 1 つの方法は、生成された数値がテストしている数値とほぼ同じになるまで、フィボナッチ数の生成を開始することです。一致する場合、テストされた数値はフィボナッチ数列に属します。一致するものがなく、テストした数値よりも大きい数値を生成した場合、テストした数値はフィボナッチ数ではありません。

これはあなたのための基本的な（そして醜い）例です：

bool isFibonacci( int testedNumber, int a = 1, int b = 1 )
{
    if( testedNumber == 0 || testedNumber == 1 )
        return true;//returning true for 0 and 1 right away.
    int nextFib = a + b;//getting the next number in the sequence
    if( nextFib > testedNumber )
        return false;//if we have passed the tested number, it's not in the sequence
    else if( nextFib == testedNumber )
        return true;//if we have a perfect match, the tested number is in the sequence
    else
        isFibonacci( testedNumber, b, nextFib );//otherwise, get the next fibonacci number and repeat.
}

そのまま使うisFibonacci( the_number_you_want_to_test );

O(log n)たとえば、この SO の質問で説明されているように、フィボナッチ数は時間で計算できることに注意してください。

于 2012-11-21T06:10:29.513 に答える
1

これは私には少し不格好に感じますが、試してみることができます：

bool isFib(int numToCheck int twoPrev = 0, int prev = 1) {
    if (numToCheck == twoPrev || numToCheck == prev)
        return true;

    int currentFibNumber = twoPrev + prev;
    if (currentFibNumber == numToCheck)
        return true;
    else if (currentFibNumber > numToCheck)
        return false;

    return isFib(numToCheck, prev, currentFibNumber);
}

これは基本的に、生成された数値がチェックしている値を超えるか、一致が見つかるまで、再帰を使用してフィボナッチ数を繰り返します。

他の人が指摘したように、再帰を必要としない解決策があります。

于 2012-11-21T06:14:53.540 に答える
0

フィボナッチ数には数学的な性質があります。(5*n^2 + 4) または (5*n^2 – 4) のいずれかまたは両方が完全な正方形である場合にのみ、数値はフィボナッチです (出典: Wiki)。

このメソッドは、再帰関数呼び出しメソッドよりもはるかに単純です。このリンクを確認してください：

http://www.geeksforgeeks.org/check-number-fibonacci-number/

別の方法:

static bool IsFib(long n)//n is the number to be checked
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    long idx    = (long)Math.Floor( Math.Log(n*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == n);
}

このコードは、大きな入力に対して機能します。同様の質問のために、スタックオーバーフローの abelenky によって投稿されました。

于 2015-01-08T06:09:33.563 に答える