0

これは、最終的には JavaScript で記述する必要があります。しかし、アルゴリズムが明確になるまでコードを入力すべきではないと感じていますが、そうではありません!

与えられた問題: 1 から始めて、与えられた数値を返す関数を作成します。これらの操作は、"+5"または"*3"問題の数値を生成します。

私の基本的なアルゴリズム:

  1. 番号を取得する
  2. 数値が 1 の場合は 1 を
    返します。
  3. それ以外の場合は、
    -1 を返します。
  4. それ以外の場合は、到達可能であると仮定して、number に到達するまで"+5"試行を続けます。"*3"

私の問題はステップ 4 にあります: 問題の番号 (ターゲット) にたどり着くには 2 つのパスがあることがわかります"+5"。OR"*3"ですが、両方のパスの MIXTURE で見つかる番号 13 はどうですか? ? 私はどちらか一方しかできません！どのパスをたどるべきか、またそのパスを何回たどるべきかをどのように知ることができますか? パス間を行き来するにはどうすればよいですか?

4

3 に答える 3

1

二分木における幅優先探索の概念に同意します。しかし、私は問題を好転させ、「-5」または「/3」を使用してターゲットから 1 に戻す問題を検討することをお勧めします。これにより、ターゲットに基づいたプルーニングが可能になります。

たとえば、13 は 3 で割り切れないため、ターゲット 13 の後方問題の最初のステップは、「/3」ではなく「-5」でなければなりません。

複雑さは変わりませんが、小さな問題の場合、実際にはアルゴリズムが高速になる可能性があります。

于 2013-08-02T14:27:43.090 に答える
0

what about the number 13 which can be found by a MIXTURE of BOTH paths?? I can only do one thing or the other!

まあ、実際には両方できます。あなたが言及した本の第3章の例のように、関数findがそれ自体の中で2回呼び出されることがわかります.関数は任意の選択点で両方のパスを試し、最初の正しい解が返されます(関数全体を変更して、すべての正しいパスを返すようにします)。

How would I know which path to take and how many times I should take that path? How would I bounce back and forth between paths?

基本的に、パス間を行き来するには、両方を移動することで実現します。関数が目標数に到達すれば、それが正しいパスかどうかがわかります。

于 2013-08-02T17:07:50.407 に答える
0

基本的に、幅優先の二分探索木を実行する必要があります。再帰を使用することも、while ループをいくつか使用することもできます。各ステップで、現在の数値を取得して 5 を追加するか、3 を掛けます。テストを実行し、入力値が見つかった場合は、0 または何かを返します (指定しませんでした)。

ここで重要なのは、データ構造とその検索方法についてです。なぜ幅優先である必要があるのか​​ わかりますか？なぜ二分木なのか分かりますか？

コメントへの返信: まず、あなたの努力に敬意を表します。言語に関係なく、この種の問題を解決することは、問題にアプローチする優れた方法です。Javascript (またはその他の言語) のばかげたトリックではありません。

したがって、最初に理解すべき概念は、解決策を「検索」し、見つからない場合は -1 を返すということです。

次に、二分木に関する調査を行う必要があります。これらは非常に重要な概念です。

3 番目に、幅優先検索を行う必要があります。ただし、それは最も重要ではありません。問題をもう少し効率的にするだけです。

于 2013-08-02T14:18:27.410 に答える