4

ご存知のように、ハノイの塔を解決する方法はいくつかありますが、最初はすべてのディスクを1つのタワーに配置する必要があります。

今、私はそれを解決する方法があることを知りたいです、そこではディスクは最初にタワーの間ですでにランダムに広がっています。

4

5 に答える 5

8

はい、それでも解決可能です（小さなディスクの上に大きなディスクがないことを前提としています）。例えば：

        1
  4     2
  6     5     3
  -------------

1を含む最大の連続スタックを見つけます。ここでは、{1,2}です。そのスタックを次に大きいディスクに移動し、他のディスクは無視します。このステップでは、標準のハノイの塔アルゴリズムを使用できます。

              1
  4           2
  6     5     3
  -------------

上記の手順を繰り返します。1を含む次の連続スタックは{1,2,3}になります。4に移動します

  1
  2
  3           
  4           
  6     5  
  -------------

同じこと-{1,2,3,4}を5に移動します。

        1
        2
        3     
        4     
  6     5    
  -------------

{1,2,3,4,5}を6に移動すると、完了です。スタック全体を特定のペグに移動する必要がある場合は、もう一度標準ソリューションを使用してください。

于 2012-01-18T13:46:32.397 に答える
0

私も専門家ではありませんが、この問題を見て、3つのスタックABとCを考慮し、前提として、ハノイの最も一般的なタワーのように、6つのディスクをスタックCで終了する必要があり、43の動きでこの問題を解決しました。これが最適な解決策かどうかはわかりませんが、ここに表示される可能性のある非常に興味深いサイトがあり ます

于 2016-07-21T13:09:16.540 に答える
0

法的取り決めの解決策は同じパターンに従います。ソリューションには2種類のステップしかありません。

  • 特定のディスクをペグに移動します
  • 特定のディスクとそれよりも小さいすべてのものをペグに移動します

ディスクをペグに移動するには、ディスクがすでにペグにあり、完了している、またはディスクがペグにない、この手順を実行する方法は1つだけです。

  • 小さいディスクをすべて残りの3番目のペグに移動します
  • 指定されたディスクを現在のペグからターゲットペグに転送します

特定のディスクとすべての小さいディスクを特定のペグに移動するには、この目標を達成する唯一の方法は、次の両方の手順を順番に実行することです。

  • 指定されたディスクをターゲットペグに移動します
  • 小さいディスクをすべてターゲットペグに移動します
于 2016-07-21T15:25:52.880 に答える
0

あなたの質問は私の生産性を破壊しました！

私はそれに答えようとして貴重な時間を費やしました、そしてここに結果があります：

まず、各ディスクが行きたい場所を最大から最小まで計算する必要があります。従うべき3つの簡単なルールがあります：

  1. 最大のディスクは右に移動したいと考えています。
  2. 少し大きいディスクが移動する場合、ディスクは「邪魔にならない」ようにします（からに移動したい場合はN+1、に移動します）。LEFTMIDDLENRIGHT
  3. 少し大きいディスクが動かない場合、ディスクは同じ場所に移動したいと考えています（にN+1とどまっている場合はRIGHT、Nに移動したいと考えていますRIGHT）。

次に、ペグに留まりたくない最小のディスクを目的の場所に移動します。（編集：あるいは、合法的な移動を実行したい最初に遭遇したディスクを移動することができますが、それはあなたのコードが合法的な移動とは何かという概念を持っていることを意味します）

解決するまで繰り返します。

例

ジャスティンの例を見てみましょう。

初期タワー

| | |
| | |
| | |
| 1 |
4 2 |
6 5 3
  • 6からに行きたいLEFT（RIGHTルール1）。
  • 5からに行きたいCENTER（CENTERルール2）。
  • 4からに行きたいLEFT（CENTERルール3）。
  • 3からに行きたいRIGHT（RIGHTルール2）。
  • 2からに行きたいCENTER（RIGHTルール3）。
  • 1からに行きたいCENTER（LEFTルール2）。

最初の動きは、ディスク1を左側のペグ（所定の位置に留まりたくない最小のディスク）に配置することです。

次

次の動きは次のようになります。

| | |
| | |
| | |
1 | |
4 2 |
6 5 3

| | |
| | |
| | |
1 | |
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
4 | 2
6 5 3

| | |
| | |
| | |
| | 1
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
| 4 2
6 5 3

| | |
| | |
| | |
| 1 |
2 4 |
6 5 3

etc.

// TODO : commenting

私はそれらのルールを実装しました、それらはどんな最初のタワー（通常のすべて左のタワーを含む）でも機能します。また、彼らは常に最短経路をたどります。

わーい！ハノイの塔を解くための非再帰的な方法！

于 2018-01-30T15:36:39.747 に答える
0

小さいディスクで大きいディスクから始める場合、解を得ることに制約はありません（たとえば、ディスクは逆の順序で、一番下が最小である可能性があり、その場合、解は簡単です）。それは問題をもう少し面白くします、しかしパズルはある時点でより大きなディスクとより小さなディスクのスタックのように見え始めます。通常の小から大へのパイルを移動して並べ替えを行うには、通常2回の移動があります。移動するディスクの数が奇数の場合は、最初に一番上の（つまり最小の）ディスクを目的の場所に移動し、次に最小のディスクを他のペグに移動してから、その上に最小のディスクを置き、次のディスクを移動するディスクの数が偶数の場合は、最小のディスクを目的の場所ではないペグに移動する必要があります。ディスクがランダムなサイズの順序である場合、いくつかのショートカットまたはいくつかの複雑さがありますが、パズルはまだ解決可能です。ランダムスタートゲームの目的は、ディスクを任意のペグで正しいサイズの順序にすることですが、通常の再帰アルゴリズムを適用して、そのようなスタックを任意のペグに移動できることは明らかです。

于 2020-05-22T14:37:39.687 に答える