5

他のサイトにも投稿しましたが、この質問をここに投稿しても問題ないことを願っています。適切なプロトコルに従わなかった場合は、お詫び申し上げます。投稿を削除して教訓を学ぶことができるように、すぐにお知らせください。

私は1年以上前からフロントエンド開発者です。私は Web 開発を学ぶために学校に通っていましたが、単純な JavaScript に関しては、ある程度有能なコーダーだと思っています。しかし、どんな種類のフィボナッチ関数を書くことになると、私にはできません。この単純な数列の扱い方を理解する脳の一部が欠けているようです。これは、John Resigの本またはオンラインのどこかから入手したと確信している作業コードの一部です。

fibonacci = (function () {
    var cache = {};
    return function (n) {

        var cached = cache[n];
        if (cached) return cached;

        if (n <= 1) return n;
        console.log(n);

        return (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
    };
}());

10 を引数としてこの関数を呼び出すと、次のシーケンスが得られます: 10,8,6,4,2,3,5,7,9

これが私が理解していることです：

fibonnaci には、すぐに呼び出される関数式 (または自己実行の何とか何とか) が割り当てられ、渡された引数でキャッシュが開始されます。議論がすでにキャッシュにあった場合、私たちはそれを返し、永遠の平和の中で私たちの生活を送っています. 引数が 1 以下の場合、それも関数の終了であり、恒久平和が再び続きます。しかし、これらの条件がどちらも存在しない場合、関数は次のステートメントを返します。これにより、私は人間のスーツを着た単なる猿であるかのように感じます。

私がやりたいのは、最初の 10 個のフィボナッチ数を正しい順序で生成することです。それができれば、少なくともそれを理解しているように感じるからです。

したがって、最初の 2 つの条件が失敗すると、コードは新しいキャッシュ変数を作成し、渡された引数に 2 を引いたフィボナッチ関数の結果と等しくなるように設定し、結果に 1 を引いた値を追加します。

  • 質問 1: fibonacci(n) が計算されていない場合、関数はどのようにして fibonacci(n-2) を認識しますか?
  • 質問 2: 再帰関数は線形ですか、それともどのような順序に従いますか?
  • 質問 3: これが理解できない場合、プログラマーになる希望はありますか?

お時間をいただきありがとうございます。

このブロックを通過した後、関数を少し変更して、結果を変数に保持して出力できるかどうかを確認し、何が起こるかを確認したところ、本当に予期しない結果が得られました。

変更点は次のとおりです。

fibonacci = (function () {
        var cache = {};
        return function (n) {

            var cached = cache[n];
            if (cached) {
                console.log(cached);
                return cached;
            }

            if (n <= 1) {
                console.log(n);
                return n;
            }
            console.log(n);

            var result = (cache[n] = fibonacci(n - 2) + fibonacci(n - 1));
            console.log(result);
            return result;
        };
    }());

結果のパターンは次のとおりです: 10,8,6,4,2,0,1,1,3,1,1,2,3,5,2,3,5,8,7,5,8,13,21 ,9,13,21,34,55 なぜこれが起こるのか、何か助けはありますか?

4

3 に答える 3

0

質問が少し古いことは知っていますが、答えは役に立ちます。私は GoLang でこの演習を行っていましたが、Javascript でどのように記述し、この回答を使用して頭をリフレッシュするかを考えました。あなたのコードには、fib(n-2) + fib(n-1) 反復の値を格納するためのキャッシュ変数があるようです。再帰的に実行している場合、関数が呼び出されるたびに数値が返され、これらの数値が最初の関数呼び出しまで加算されるため、結果を格納するための変数は必要ありません。

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

キャッシュ変数が必要ない理由を確認するには、各関数呼び出しを実行し、値がn1 または 0 になったら計算を開始します。

例えば：

iteration 1)

fib(3) {
   return fib(3-1) + f(3-2)   
}
---------------------------    
iteration 2)

fib(3-1) {
   return fib(2 - 1) + fib(2-2)
}

iteration 3)

fib(3-2) {
   return 1
}    
---------------------------

iteration 4)

fib(2-1) {
   return 1
}


iteration 5)
fib(2-2) {
   return 0
}
----------------------

反復から逆戻り値を計算する場合 5)

5) 0
4) 1
3) 1
2) 1 <== 4) + 5)  = 1 + 0  
1) 2  <== 2) + 3)  = 1 + 1

したがって fib(3) は 2 です

于 2015-02-21T04:14:54.620 に答える