問題タブ [towers-of-hanoi]

私が目にするほとんどの実装では、再帰的なソリューションを使用しています。しかし、私はこれを望んでいません。幅優先や深さ優先などの検索アルゴリズムを使用してツリー内を検索したい。

ありがとうございました

Javaでハノイの塔の問題をテストしていたところ、次のコードを実行しました:(便宜上削除しました)sysouts

私は実験を行い、1 から 35 までのディスク サイズ (インデックス) を試しました。非常に奇妙なタイミング パターンを観察しました。プログラムの出力は次のとおりです。

質問 1 : アルゴリズムには指数関数的な増加(2^n-1)があります。しかし、その後、20 から 35 へと急上昇したのでしょうか。

質問 2 : また、私をさらに驚かせたもう 1 つのことは、ペアの時間が等しいことです。19 から始めて、(19,20)、(21,22)、(23,24)、(25,26) など....同等の時間があります。アルゴリズムの成長率が実際に指数関数的である場合、なぜ2つのインデックスがほぼ同等の時間を与え、次のインデックスで突然ジャンプするのか理解できませんか?

注: このプログラムを 2 ～ 3 回繰り返したところ、ほぼ同等のタイミングが得られたので、平均的な実行と見なすことができます。

編集
して、次の 結果System.nanoTime()を得ました：

出力はミリ秒にほぼ似ていますが、全体像を明確にしています...私の質問 1の答えかもしれませんが、質問 2はまだ興味深いものです。そして、System.nanoTime()もう1つの質問を提起しました：

質問 3 : インデックス 1 が次のインデックス (2、3...) などよりも時間がかかるのはなぜですか?

これは宿題ではありません。学校にお金がないので、高速道路の料金所で交代制勤務をしている間（顧客が少ない長い夜）、自分で教えています。

JavaでHanoiTowersソルバーの単純なバージョンを実装しようとしています。私は自分自身を考える機会を得るために外部ソースに相談することなく、スタックと再帰関数を使用しています。

配列の配列（int[][] pegs）から始めましたが、「移動」ステップの実装、特に開始位置の配列から「選択」する必要がある「高さ」と「高さ」を知る方法に行き詰まりました。ディスクをdestination-position配列にドロップします。もちろん、Stack<Integer>これを行うのはデータ構造であり、何も追跡する必要はありません。私はこのバージョンをコーディングしましたが、あきらめることについて否定的に怠惰に感じました。私は自分の脳を伸ばし、アレイを使ってそれをすべて行う方法を理解することに興味を持っています。

を使用してこのコードを実装することは可能int[][] pegsですか？どのように？（ヒントで十分です。私はアプローチに固執しています。正しい道を特定した後、自分でレッグワークを行うことができます）。

ところで、私が書いたコードは「無難な」Javaですか、それとも誤用していますか？（JavaとC ++のどちらに焦点を合わせるかはまだわかりません。両方の電子書籍を持っています）。

RobetSedwick による C++ の本でアルゴリズムを読んでいます。ここで筆者はハノイの塔について、分割統治法と再帰性を用いて説明しています。

次のコードは、問題に対する再帰的な解決策です。各ステップでどのディスクをシフトするか、どの方向に移動するかを指定します (+ はペグを 1 つ右に移動し、一番右のペグにある場合は一番左のペグに循環することを意味し、- はペグを 1 つ左に移動し、ペグを左に循環することを意味します)。一番左のペグの場合は一番右のペグ)。

私の質問は、ディスクが左のペグ (つまり、ペグ 1) にある場合、「左端のペグへのサイクリング」の上で著者が何を意味するかです。

著者はまた、再帰は次のアイデアに基づいていると述べました。ディスクをもう 1 つ左に (ディスク N に) ペグします。

上記の左右の用語で混乱しています。誰でも説明してください。

私はロバート・セッジウィックのアルゴリズムを読んでいます

以下は、数値の2進表現における後続ゼロの数に関する213ページからの抜粋です。

ハノイの塔の問題の場合、nビット数との対応の意味はタスクの単純なアルゴリズムです。完了するまで2つの手順を実行することで、パイルを1ペグ右に移動できます。

1. nが奇数の場合は小さなディスクを右に移動します（nが偶数の場合は左に移動します）
2. 小さなディスクを含まない唯一の合法的な動きをしてください。

つまり、小さなdsikを移動した後、他の2つのペグには2つのディスクが含まれ、一方が他方よりも小さくなります。小さいディスクを含まない唯一の合法的な移動は、小さいディスクを大きいディスクに移動することです。1つおきの数字が奇数であり、ルール上の1つおきのマークが最短であるのと同じ理由で、1つおきの移動には小さいディスクが含まれます。

上記のテキストは、情報からさまざまな参考資料を読んだ後でも、頭に浮かびません。

ディスクN=3などの簡単な例を教えてください。Disk3が最大でDisk1が最小であり、PegAからPegBに移動する必要があります。

再帰についてもっと理解するために、ハノイの塔の問題を実装していました。私は 3 ペグのケースを使用してそれを実装することができましたが、より多くのペグを使用したい場合 (より少ない動きを生成するため) は、私が持っているディスクの数を壊して1 つのペグに積み重ねる必要がある Frame-Stewart ソリューションを理解していますそして、元のペグからすべての中間ペグを使用して目的のペグにディスクを転送している間は、そのペグに触れないでください。しかし、関数として move(disks, 1, i, {2...K}) のようなものを記述する方法がわかりません。最初からペグの名前すら知らないのに、どうやって関数プロトタイプのすべてのペグの名前を書けばよいのでしょうか? 以下に 3 ディスク ソリューションについて考えたことを示しましたが、より一般的なケースについては助けが必要です。

6ペグのケースを解決するために、「移動」機能にどのような変更を加える必要があるのか​​ わかりません。ありがとう

ハノイの塔の問題の k-peg ソリューションを解決するアルゴリズム (論理的) を思いつくことができましたが、コードを実装すると、セグメンテーション エラーが発生しました。

アイデアは非常に単純です。フリーペグ (またはタワー) のベクトルを保持し、ディスクを移動するときにそれを更新します。したがって、6 つのペグと n 個のディスクの場合、1 つのソース、1 つの宛先、および 4 つの空きペグがあります。アイデアは、ソースから free_peg[3] (4 番目のフリー ペグ) に (n - p) (p ~ n/2) を移動することです。現在、ベクターには 3 つの空きペグしかありません。これらの 3 つの空きペグを使用して (n - p - 1) ディスクを free_peg[2] に移動し、最後のディスクをソースから宛先に移動します。これで、2 つの空きペグと 1 つのソース = 3 つの空きペグができました。次に、(n - p - 1) 個のディスクを peg[2] から 3 つの空きペグ (現在は空きになっているソースを含む) を使用して移動先に移動する必要があります。最後に、4 つのフリー ペグを使用して、p 個のディスクを free_peg[3] から移動先に移動します。ただし、これをコードに実装すると、セグメンテーション違反が発生します。誰か助けてもらえますか?

以下のコードは、事前定義された関数 moveLOD、swapLOI、および swapLID を使用して手のリストを返す hanoi を解決します。

MoveLOD: 1 つのディスクを 1 番目の位置から 3 番目のピンの 3 番目の位置に移動します。さらに、動きに関する情報を含む文字列が文字列のリストに積み上げられています。

CS の宿題でこの問題を解決しようとしています (宿題としてタグ付けします。正しい方向への一歩が必要です)。編集:どうやら「宿題」タグは廃止され、使用されなくなったようです。とにかく、与えられた手のリストがタワーを解決できるかどうかを判断するルール定義を Prolog で作成する必要があります。私は指示が悪いことを知っています、私の教授は非常に不明確ですが、私が持っているのは以下の条件が満たされなければならないということだけです:

上記のいずれかが私に何をするように示唆しているのか、私には少しの手がかりがないので、どんなガイダンスも大歓迎です! そのようにタグ付けすることはできませんが、私が言ったように、これは宿題の問題です（説明がないことを考えると、一見ばかげて難しいように見えますが）ので、必ずしも答えが欲しいとは限りません。何が起こっているのかを正確に理解するために。

皆様本当にありがとうございました!!

スタックとリンクされたリストを使用してタワー ゲームを解決し、再帰を使用してブロックをタワーからタワーに移動することに取り組んでいます。

java.lang.NullPointerException を引き起こす問題が発生しました。これが起こった理由は、エントリがない場合でもスタックから値をポップしようとしたためだと思います。バインドされたコントロールを配置した後も、そのエラーが発生します。

エラーは deleteFirst() メソッドのある行を指していますが、リストが空かどうかを確認した後でも、なぜこれが発生するのかわかりません。

ここでの私のタスクは、タワーまたは LinkedStack オブジェクトを渡し、それらのコンテンツをタワー ゲームのように移動することだけでした。

エラー:

ここで何が間違っていますか？私はこれを機能させることはできません。あるべきように。