0

負のインデックスを考慮に入れるために、フィボナッチ数に拡張子を追加しようとしています。拡張子はFib（-n）=（-n）^（n + 1）* Fib（n）これをc ++で実装しようとしましたが、問題が発生し、回避方法がわかりません。それ。

#include <iostream>
#include <math.h>


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


int main(void){
    std::cout << "fib("<< -2<<") = " << fib(-2) << std::endl;
    return 0;
}

これは私にセグメンテーション違反を与えます、これがなぜであるかについて何か考えはありますか？

編集：私は問題が何であるかを理解しました。基本ケースを忘れたため、無限再帰が発生し、セグメンテーション違反が発生しました。

4

4 に答える 4

4

私はあなたがそれを呼ぶときfib(-2)それが呼ぶと思いますfib(2)

fib(2)電話fib(1)とfib(0)

fib(1)電話fib(0)とfib(-1)

fib(-1)呼び出しfib(1)、これは無限ループです

于 2010-09-08T09:20:13.597 に答える
1

これにより、無限の再帰が発生します。1つではなく、2つの終了ケースが必要です。

たとえばfib(1)。fib(0)これはとを呼び出しますfib(-1)。fib(0)終了しますが、fib（-1）`を無限fib(-1)に呼び出します。fib(1), which will then again call

n==0解決策：またはの場合、再帰を終了しますn==1。

補足：fib(0)通常、1ではなく0として定義されます。

于 2010-09-08T09:22:09.800 に答える
1

おっと、n==-1の基本ケースを忘れてばかげた間違いをしました。そのはず：

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

これで、すべてが期待どおりに機能します。

于 2010-09-08T09:23:31.043 に答える
1 
According to your extension, shouldn't this be:
int fib(int n) { 
    if ( n < 0 ){  
        return ( pow(-1,n+1 ) * fib(n) ); // <<<
    }else if (n == 0){ 
        return 1; 
    }else{ 
        return fib(n-1) + fib(n-2); 
    } 
}
于 2010-09-08T09:23:38.813 に答える