5

これはEloquent Javascriptの例です:

1 から始めて 5 を足したり、3 を掛けたりすることを繰り返すと、新しい数が無限に生成されます。与えられた数値に対して、その数値を生成する加算と乗算のシーケンスを見つけようとする関数をどのように記述しますか?

ここで再帰がどのように機能しているかを理解するのに苦労しています.findがどのように呼び出されるか、または他の説明を誰かが数回書き出すことができるかどうか疑問に思っています.

function findSequence(goal) {
  function find(start, history) {
    if (start == goal)
      return history;
    else if (start > goal)
      return null;
    else
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }
  return find(1, "1");
}

console.log(findSequence(24)); // => (((1 * 3) + 5) * 3)
4

11 に答える 11

10

この関数は、バックトラッキングを使用したかなり単純なブルート フォース検索を実行します。各呼び出しレベルで、数値に加算を試行し、結果の数値から開始してゴールにたどり着くかどうかを確認します。一致する場合は、結果が返されます。それ以外の場合、数値は で乗算され、ゴールの検索はその新しい数値から続行されます。再帰が進むにつれて、数値を生成する式のテキスト表現が次の呼び出しレベルに渡されます。53

の検索は14次のようになります。

(1,  "1")
(5,  "1+5")
(10, "(1+5)+5")
(15, "((1+5)+5)+5") <<= Fail
(30, "((1+5)+5)*3") <<= Fail
(15, "(1+5)*3") <<= Fail
(3,  "1*3")
(8,  "(1*3)+5")
(13, "((1*3)+5)+5")
(18, "(((1*3)+5)+5)+5") <<= Fail
(39, "(((1*3)+5)+5)*3") <<= Fail
(24,  "((1*3)+5)*3") <<= Fail
(9, "(1*3)*3")
(14, "((1*3)*3)+5) <<= Success!
于 2013-03-29T22:19:32.353 に答える
4

これを理解するには、呼び出しのツリーを作成する必要があります。

findSequence(24)
    find(1, "1")
       find(1 + 5, "(1 + 5)")
           find(6 + 5, "((1 + 5) + 5)")
               find(11 + 5, "(((1 + 5) + 5) + 5)"
                   find(16 + 5, "((((1 + 5) + 5) + 5) + 5)"
                       find(21 + 5, "(((((1 + 5) + 5) + 5) + 5) + 5)"
                          start > goal: return null
                       find(21 * 3, "(((((1 + 5) + 5) + 5) + 5) + 5)" 
                          start > goal: return null
                   find(16 * 3, "((((1 + 5) + 5) + 5) * 3)"
                       start > goal: return null
               find(11 * 3, "(((1 + 5) + 5) * 3)"
                   start > goal: return null
           find(6 * 3, "((1 + 5) * 3)")
               find(18 + 5, "(((1 + 5) * 3) + 5)")
                   find(23 + 5, "((((1 + 5) * 3) + 5) + 5)")
                       start > goal: return null
                   find(23 * 3, "((((1 + 5) * 3) + 5) * 3)")
                       start > goal: return null
               find(18 * 3, "(((1 + 5) * 3) * 3)")
                   start > goal: return null
       find(1 * 3, "(1 * 3)") 
           find(3 + 5, "((1 * 3) + 5)")
               find(8 + 5, "(((1 * 3) + 5) + 5)")
                   find(13 + 5, "((((1 * 3) + 5) + 5) + 5)")
                       find(18 + 5, "(((((1 * 3) + 5) + 5) + 5) + 5)")
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                           find(23 + 5, "((((((1 * 3) + 5) + 5) + 5) + 5) + 5)")
                               start > goal: return null
                       find(18 * 3, "(((((1 * 3) + 5) + 5) + 5) * 3)")
                           start > goal: return null
                   find(13 * 3, "((((1 * 3) + 5) + 5) * 3)")
                       start > goal: return null
               find(8 * 3, "(((1 * 3) + 5) * 3)")
                   return "(((1 * 3) + 5) * 3)"
           find(3 * 3, "((1 * 3) * 3)")
               find(9 + 5, "(((1 * 3) * 3) + 5)")
                  find(14 + 5, "((((1 * 3) * 3) + 5) + 5)")
                      find(19 + 5, "(((((1 * 3) * 3) + 5) +5) + 5)")
                         return "(((((1 * 3) * 3) + 5) +5) + 5)"
                      find(19 * 3, "((((1 * 3) * 3) + 5) *3)")
                          start > goal: return null
               find(9 * 3, "(((1 * 3) * 3) * 3)")
                    start > goal: return null
于 2013-03-29T22:37:57.333 に答える
2

これを学習する最善の方法は、JavaScript デバッガーでコードをトレースすることです。

以前にデバッガを使用したことがありますか? それは本当に楽しくて啓発的で簡単です。

debugger;コードを停止したい場所にステートメントを追加するだけです。適切な場所は、電話をかける直前ですfindSequence()。

debugger;
console.log(findSequence(24));

開発者ツールを開いた状態で Chrome にページをロードします。コードはそのdebugger;行で停止します。コードにステップ インできるボタンを見つけます (ウォッチ式パネルの右上にあります)。そのボタンをクリックして、findSequence()通話に参加します。クリックするたびに、次のコード行に進みます。これには、各再帰呼び出しが含まれます。

コードが停止している場合はいつでも、マウスを任意の変数の上に置いて表示するか、右側のパネルで変数を確認できます。再帰呼び出しのどこにいるかを正確に示す呼び出しスタックもあります。

誰かが再帰について説明できると思いますが、デバッガーでコードをステップ実行して実際に経験すると、さらに多くのことを学ぶことができます。

于 2013-03-29T22:20:38.940 に答える
2

簡単に言えば、値に達していないfind(start,goal)限り、再帰的に呼び出されます。goal各呼び出しでは、現在の数値が 3 倍されるか、5 ずつ増加します。history変数には、実行された操作の文字列が格納されます。現在の操作は、反復ごとにその文字列に追加されます。

説明：

function findSequence(goal) {

  // This inner function will be called recursively.
  // 'history' is a string with the current operations "stack"
  function find(start, history) {
    if (start == goal)           // if goal is achieved, simply return the result
                                 // ending the recursion
      return history;
    else if (start > goal)       // return null to end the recursion
      return null;
    else
      // One of the 'find' calls can return null - using ||
      // ensures we'll get the right value.
      // Null will be returned if 'start+5' or 'start*3' is
      // greater than our 'goal' (24 in your example).
      // The following line is where a recursion happens.
      return find(start + 5, "(" + history + " + 5)") ||
             find(start * 3, "(" + history + " * 3)");
  }

  // Start with '1'
  return find(1, "1");
}
于 2013-03-29T22:19:01.433 に答える
1

goalが目標で、24 に設定されています

goal == 24

これで、 が 24 に等しいfind()かどうかをチェックする内部関数ができました。startそうではありません。また、start が 24 より大きいかどうかもチェックしますが、これも当てはまりません。

find(1 "1")
1 == 24 //false
1 > 24 //false

そのため、find を再度呼び出す else ステートメントにヒットします。ここで、からの null 値がelse if()入ります。戻り値が null の場合は、|| を呼び出します。最終的に正しい答えが見つかるまでパートします。

return find(6, "(1 + 5)")
       find(11, "((1 + 5) + 5)")
       find(16, "(((1 + 5) + 5) +5)")
       find(21, "((((1+5) + 5) + 5) +5)")
       //next one returns null!
       //tries * by 3 on 21, 16, and 11 all return null

|| に切り替わります。

return find(3, "(1 * 3)")
       find(8, "((1 * 3) +5)")
       //some calls down +5 path but that returns null
       find(24, "(((1 * 3) + 5) * 3)")

ついに！真のリターンがあり、履歴 var にたどったパスを記録しました。

于 2013-03-29T22:37:36.183 に答える
1

の本体にfindは、再帰を停止する条件に対応する 2 つと再帰する条件に対応する 3 つの出口パスがあります。

if (start == goal)
  return history; // stop recursion: solution found
else if (start > goal)
  return null;    // stop recursion: solution impossible
else
  // ...

3 番目のパスは実際には「分岐」であり、2 回再帰します (1 回は加算を試行し、1 回は乗算を試行します)。

  return find(start + 5, "(" + history + " + 5)") ||
         find(start * 3, "(" + history + " * 3)");

それで、ここで何が起こっているのですか？

まず、これら 2 つのfind呼び出しのそれぞれが、空でない文字列 (操作の履歴) または のいずれかに評価されることに注意してくださいnull。空でない文字列は「真の」値であり、「偽の」値であるため、これらを演算子nullで結合することでこれを利用します。||この演算子は、真の場合は最初のオペランドに評価され、そうでない場合は 2 番目のオペランドに評価されます。

これは、最初の再帰分岐 (+5) が最初に評価されることを意味します。5 を加算することから始まり、ゴールに到達する操作のシーケンスがある場合、このシーケンスの説明が返されます。それ以外の場合、3 を乗算することから開始してゴールに到達するシーケンスがある場合、その履歴の説明が返されます。

ゴールに到達する方法がない場合、戻り値はnull2 番目の分岐によって生成されます。

于 2013-03-29T22:19:54.673 に答える
1

この関数は 1 から始まり、それに 5 を足すか 3 を掛けようとします。それが目標に等しい場合、関数は終了し、見つかった式を出力します。そうでない場合は、一致が見つかるか、値が高くなりすぎるまで、そのレベルの値で自分自身を再帰的に呼び出します。

それは役に立ちますか？

于 2013-03-29T22:17:10.877 に答える
1

find が呼び出される方法を誰かが数回書き出すことができます。

どうぞ：

find(1, "1") -> find(3, "(1 * 3)")
             -> find(8, "((1 * 3) + 5)")
             -> find(24, "(((1 * 3) + 5) * 3)")
于 2013-03-29T22:17:57.397 に答える
1

二分木のように、5 を足して 3 を掛ける無限の組み合わせを考えてみてください。上部は計算が最も簡単な数値です1(実際には、「ステップは必要ありません」という回答です)。1 つ下のレベルで左が1+5、右が です1*3。各レベルで、方程式は新しい値に解決されます (より複雑な履歴を持つ)。この方程式は、次のノードに等しいノードが見つかるまで、そのツリーをナビゲートします。goal. ツリーのブランチのノードが目標よりも大きい値を生成する場合、null を返します (したがって、そのブランチをさらに再利用するのを停止します。これは、両方の操作が値を増やすだけであるためです。ノードの値がゴールに等しい場合、それが答えとして返されます (そこに到達するために使用したパスと共に)。値がそれより小さい場合、両方のパスが答えを保持している可能性があるため、それぞれで find を呼び出します。ここで、JavaScript の「真の」ブール論理の出番です。||(OR) 演算子を使用することにより、JavaScript はまず+5ツリーの側面を調べます。0 または null が返された場合、( を調べるための) 他の呼び出し*3が実行されます。リターンが非と評価された場合false値の場合、スタックに返され、検索が終了します。

于 2013-03-29T22:19:19.873 に答える
1

If you get rid of the pretty printing stuff, the code is a little easier to read:

function findSequence(goal) {
    function find(start) {
        if (start == goal) {
            return true;
        } else if (start > goal) {
            return false;
        } else {
            return find(start + 5) || find(start * 3);
        }
    }

    return find(1);
}

The outer function, findSequence, dynamically creates a new function called find where goal is taken from the scope of the parent function. You could re-write it like this for clarity:

function findSequence(start, goal) {
    if (start == goal) {
        return true;
    } else if (start > goal) {
        return false;
    } else {
        return findSequence(start + 5, goal) || findSequence(start * 3, goal);
    }
}

Now, you can see a little more clearly what happens. The recursive step is in the final return statement, which tries both start + 5 and start * 3 at each step and picks the branch that eventually returns true.

Follow the logic of findSequence(1, 23) by hand and you'll understand how it works.

于 2013-03-29T22:23:20.433 に答える
1

history パラメーターはそのままにしておきます。後で説明します。

再帰は、可能なすべての操作に展開されます。1の値で始まりますstart。

  1. 最初に、目的地に到達したかどうかを確認しgoalますtrue:

  2. 次に、境界 ( ) を超えましたgoalか? もしそうならfalse、この道は役に立たないので戻るべきです。

  3. それ以外の場合は、2 つの可能性を試してみましょう (少なくとも 1 つが必要なため、OR を使用します)。

    • 同じ関数を呼び出しますが、次のように設定startしますstart + 5
    • 同じ関数を呼び出しますが、次のように設定startしますstart * 3

履歴変数は、実行した手順を保持します。したがって、関数呼び出しがstart == goalそれを返すことを識別した場合。

于 2013-03-29T22:24:27.950 に答える