問題タブ [towers-of-hanoi]

重複の可能性:
これはどのように機能しますか? ハノイ ソリューションの奇妙な塔

Google をサーフィンしているときに、スタックをデータ構造としても使用しないハノイの塔に対するこの興味深いソリューションを見つけました。

誰かが私を簡単に説明できますか、それは実際に何をしているのですか?

この解決策は本当に受け入れられますか?

コード

更新: ここでハードコードされた番号 3 は何をしているのですか?

現在、ダグラス・クロックフォードの本を読んでいますが、ハノイの塔の機能は少し頭に浮かびます。コンソールにログを記録しても、何が起こっているのか本当に理解できませんでした。これが私の追加機能です：

これにより、次のようになります。

3
Src Dst
2 Src
Aux
1
Src Dst 0SrcAux ディスク
1 をSrcから Dstに移動 0AuxDst ディスク2をSrcからAuxに移動 1DstAux 0DstSrc ディスク 1 をDstから Auxに移動 0SrcAux ディスク3をSrcから移動to Dst 2 Aux Dst 1 Aux Src 0AuxDst ディスク1をAuxから Srcに移動 0DstSrc ディスク2をAuxからDstに 移動 1SrcDst 0SrcAux ディスク 1 をSrcからDstに移動




























0
Aux Dst

そして、私は早い段階で迷子になっています。結果の6行目で、SrcAuxからSrcDstに戻るにはどうすればよいですか？

そして、関数が「disc-1」を使用して自分自身を呼び出しているだけのときに、ディスクの数が0に達した後、どのようにしてディスクの数を増やすことができますか？

ハノイの塔の問題の実行時間をどのように解決しますか。t（n）= 2t（n-1）+ 1のような漸化式を取得します。漸化式ツリーを描画した後、1 + 2 + 4+8のようなすべてのステップ値で取得します...ツリーの高さはlgになります。 （n）。級数の合計を計算するにはどうすればよいですか？いつ止まりますか？

私がハノイの塔の問題をユニットテストしていたとしたら、最良のケースは何でしょうか？メソッドのパラメーターと一般的に期待される出力をテストできますが、他にテストすることはできますか？

だから私はテストすることができます：出力は正しい（アルゴリズムは機能している）、引数は正しい仮定（つまりnullではない）です、他に何かありますか？

ありがとう

プログラミングを学び始めたばかりなので、地元のコミュニティ カレッジでクラスを受講していて、ハノイの塔のプログラムを作成する必要があります。図書館に行って本を読んだり、家庭教師に行ったりしています。まで。誰かが私を正しい方向に向けるか、助けてください。

私の仕事は、一連の print ステートメントを追加して、ハノイの塔の完全な出力を表示し、最終結果を提供するだけでなく、舞台裏で何をしているのかを確認して理解することでした。

ここに私の出力としてあるものがあります。私が欠けているのはindentationだけです。第 1 レベルの再帰には 1 つのタブ、第 2 レベルの再帰には 2 つのタブが必要です。

現在の出力:

望ましい出力:

関数に入った回数を「カウント」するには、ある種のカウンターが必要ですか? しかし、それは再帰でも可能ですか? この問題に対するもっと簡単な解決策がある場合、おそらく私は分析しすぎているのでしょうか?

ルール

ハノイの塔はパズルです。よく知らない場合は、次のように操作します。

プレイ フィールドは 3 つのロッドとx個のディスクで構成され、次のディスクは前のディスクよりも大きくなっています。ディスクは、次のルールでロッドに取り付けることができます。

• 一度に移動できるディスクは 1 つだけであり、別のロッドの上で移動する必要があります
• ディスクはロッドの上部から取らなければなりません
• ターゲットロッドの最上部のディスクが移動するディスクよりも大きい場合にのみ、ディスクをどこかに移動できます

そして最後に - プレイフィールドは次のように始まります:

• x個の円盤があり、最大のものを下に、最小のものを上に並べた棒
• 空の棒
• 空の棒

ゲームの目標は、ディスクの元の「スタック」を別のロッドに移動することです。つまり、すべてのディスクを別のロッドに配置します。したがって、(ここでも)最大のものは下に、最小のものは上になります。

実装

あなたの目標は、選択したプログラミング言語でプログラムを作成することです。このプログラムは、入力 (以下で説明) を受け取り、位置を解決するために必要なステップを出力します。

いつものように、できるだけ短くするようにしてください。

入力

入力例:

入力は、コンマで区切られた 3 つの部分で構成される文字列です。パーツは、3 つのロッドのそれぞれにあるディスクのリストです。今回はハイフン ( - ) で区切られており、各サブパートは数字であり、数字が大きいほどディスクが大きくなります。

したがって、上記の入力の場合、これは視覚的な表現になります。

出力

上の図でわかるように、入力の一番左の部分がロッド番号 1、中央がロッド番号 2、最後の部分がロッド番号 3 です。

プログラムの出力は次のようになります。

ディスクを取り出すロッドとディスクを取り付けるロッドを定義する、コンマで区切られた番号のリスト。ロッドは 3 つしかないため、考えられる組み合わせは 6 つだけです (ディスクを同じロッドではなく別のロッドに移動する必要があるため)。

ノート

入力は、「元の」状態のフィールドを記述する必要はありません。解決の途中でもかまいません。

あなたのプログラムはヌル出力を生成できません。入力が元の状態の場合は、ディスクを別のロッドに入れるだけです。

入力には、次のように空のロッドを含めることができます。

入力がこのようにフォーマットされていない場合、プログラムは未定義の動作を引き起こす可能性があります。そのため、入力が有効でない場合 (小さいディスクに大きなディスクが接続されている、ディスクが見つからない、解決できないなど) は可能です。入力は常に有効です。

ソリューションが可能な限り高速であることを確認してください (可能な限り少ないターン)。つまり、「12,21,12」でターンを無駄にしないでください...

テスト

そこで、この小さなフラッシュを用意しました。これを使用すると、プログラムが適切なソリューションを生成したかどうかを書き留めたり何もせずにテストしたりできます。

ここにあります：Hanoi AlgoTest（ロードしてから更新するのを待ちます-デッドリンク:|）

これを使用するには、プログラムへの入力をINPUTフィールドに貼り付け、プログラムによって生成された出力をPROCESSフィールドに貼り付けます。変更可能な速度でシミュレーションを実行し、視覚的な表現を使用して、下部にエラーを出力します。

それが役に立てば幸い。

ハノイの塔問題に関するいくつかの議論を読みました。次のコードを使用した再帰的なソリューションを理解しています。

私が実際に行う必要があるのは、各ステップでタワーのある種の「イラスト」を出力することです。私はこれを達成するのに多くの問題を抱えています。インストラクターは、どのディスクがどのタワーにあるかを追跡するためにスタックを使用することを提案しましたが、スタック内の値を見つけて出力するには、一番上のエントリをポップして削除する必要があるため、これを出力するのに問題があります。私が正しく理解すれば、それらは失われます。

いずれにせよ、それは次のように始まるいくつかの解決策に私を導きました:

これが間違っていることは十分承知しています。ソースにディスク番号を入力するのに適した場所がどこかわかりません。そして、毎回同じサイズのソース スタックを渡しています。誰かが私に何らかの方向性や何かを与えることができれば、それは本当に素晴らしいことです. ありがとうございました。

2*n 個の円盤があるとします。棒 "A" に奇数の円盤があり、棒 "B" に偶数の円盤がある場合、ハノイの問題はどのように解決されるでしょうか? さらに情報が必要な場合はお知らせください。

ありがとう

ハノイの塔の問題の解決策を開発しました。

それは正常に動作します。ここで、スライドの数を制限し、特定の制限に達した場合に例外をスローしたいと考えています。カウンターで試してみましたが、うまくいきません：

例外がスローされることはありません。何か案は？

更新: 結果は 6 枚のスライドですが、5 枚にする必要があります http://ideone.com/lm084