ハノイの塔を解くII

1. • 私はリングを動かするための基本的なルールはよく知られていると仮定します。
     
   • リングの数が奇数の場合は、あなたが望むリングの上にまっすぐにトップリングを配置するために1ステップだけ必要です。
     
   • 偶数の場合は、移動を行うための2つのステップが必要です。左から右にペグA、B、Cを仮定しましょう。たとえば、B にリング 1,2,3,4 の山があり、C のリング 5 の上に置きたい場合、最初のステップは 1 から A、2 から C、次は 1 から C になります。15の動きの合計で、我々はペグC上の5以上の1,2,3,4リングを持つことになります。
     
   • 最初のレイアウトでは、小さなリングの上に大きなリングがありますが(これはこのゲームのバージョンIとの主な違いです)、あなたがプレイを開始すると、ハノイの塔のように小さなリングの上に大きなリングを置くすることはできません。
     
   • 私はゲームを解決するための最良のアプローチは、リング9、8、7の位置を簡単に見て始めていると思います。リング9がすでにペグのベースにあるかどうかを確認することが重要です。そうでなければ、そこに置く最善の方法(動きが少ない)は何ですか?この場合、多くの場合、9の無料ペグを持つために7オーバー8を配置する必要がある(特に7と8が異なるペグにある場合)発生します。さらに、私たちは9に6を配置する必要があるかもしれません, 7は6を移動した後、フリーペグに移動し、6オーバー7 . 結果は1から7までの山になり、これらの7つのリングを8,9の上に置くために127の追加の動きが必要になります(ハノイIの塔でゲームを解決するための動きの最小数は: 最小限の動き = 2^n - 1 はnがリングの数なので、3リングは7つの動きを必要とします、4リングは15..7つのリングは127などを必要とします)。
     
   • どのような場合でも、目的は、可能な限り最小限の移動数で、ハノイIの塔の状況に初期レイアウトを変更することです。これは、ゲームを実際に終了することなく解決できるかどうか、常に事前に知っていることを意味します。リングがハノイ1の塔の状況にある場合(リング1,2.で始まる昇順の山。1つのペグ、フリーペグ、残りのリングを持つペグ、さらに昇順で、9があるペグのベースで終わるだけで、上記の方程式によって与えられた必要な動きに既に行われた動きを追加するだけで、結果は必要最小限の動きに等しくする必要があります(コントロールが最後の数字を追加するだけです)。
     
2. 3つの例(すべてこのウェブサイトから)。
   1. 初期レイアウト(145の最小限の移動が必要)
      
      ペグA - 1,8,2,9
      ペグB - 7,3
      ペグC - 6,5,4
      
      ステップ1 - 最良の戦略は、ペグCのベースに9を置き、ペグBの7の上に6を置く。
      
      最初の動きは、Aの9の上にリング3、Bの7の上に4です。
      
      最初のレイアウトから 18 の移動後、私たちは得る:
      
      ペグA - 1
      ペグB - 7,6,5,4,3,2 18の動き
      ペグC – 9,8
      
      ステップ 2 – このレイアウトを注意深く見ると、次の動きが C の 8 の上にリング 1 を配置する場合、これは B の 7 の上に 6 つのリングに相当することに注意してください。私たちは6つのリング(6,5..)について話しています。1 すなわち、ペグBおよび2ステップ上であっても必要である)。したがって、これらの6つのリングをAに配置するには、もう一方のペグ(この場合はC)に1を配置する最初の動きが必要です。
      
      すでに知っているように、6つのリングを別のペグ(ペグA)に移動するには、63の動きが必要です。これらの動きの後、9,8の上に7、今は無料で配置する追加のものがあります。
      したがって、このステップ2では、移動は 63 + 1 = 64 になり、レイアウトは次のようになります。
      
      A - 6,5,4,3,2,1
      B - 63+1 = 64移動
      C - 9,8,7
      
      これまでのところ、ステップ2のステップ1と64で18の動きがあります
      
      ステップ3 - 上記のレイアウトは、私はハノイIの状況の塔と呼ばれるものに対応しています.
      
      ゲームを終了するには、6つのリング(6,5,...を移動する必要があります1)ペグCの9,8,7の上部にペグAに。 これには別の63の動きが必要です。
      
      総移動数= 18 + 64 + 63 = 145 必要最小限の移動です。
      
      
   2. 初期レイアウト(256の最小限の移動が必要)
      
      A - 5,3,9
      B - 8,1,6,4
      C - 2,7
      
      8と7が異なるペグにあるので、ベースに9を置くためには、Bの8の上に7を置く必要があります。
      
      ステップ1 - 私たちの目標は、Cに9、Bの8の上に7を置く。これを達成するには、最初にAの9のトップに6,4を移動し、Cを解放して9を受け取る必要があります。
      
      最初の5つの動きは、Aの9の上に7,6の上に4、6、1〜4とペグBで7〜8です。
      
      20移動後、レイアウトは
      
      A – 5,3
      B – 8,7,6,4,2,1 20 の動き
      C - 9
      
      ステップ2はペグCの上に6オーバー9を置きます。これを達成するためには、ペグAの5,4,3,2,1でこのステップ2を終える5の上に4が必要です。これは13の移動で行われ、レイアウトは
      
      A – 5,4,3,2,1
      B – 8, 7 13移動
      C - 9,6
      
      ステップ 3 – ペグ C の 6 の上部に 5,4..,1 (5 つのリング) を移動します。これは、ペグAに7を配置するために31の動きプラス1に対応しています。 したがって、ステップ 3 31+1=32 の移動回数とレイアウトは
      
      A - 7
      B – 8 32の動き
      C – 9,6,5,4,3,2,1
      
      ステップ4 - 6,5を移動,...ペグAの7の上に1は(6リング)63の動きとCの9の上に8を置くために別のものを必要とします。
      
      A – 7,6,5,4,3,2,1
      B - 63+1 = 64移動
      C - 9,8
      
      ステップ 5
      
      私たちはハノイ1の状況の塔を持っています。最後のステップは、ペグAから7リングを移動することです
      ペグCの9,8の上に。これは127の動きを意味します。
      
      総移動 - 20 + 13 + 32 + 64 + 127 = 256 最小の移動が必要です。
      
      
   3. 初期レイアウト(303の最小限の移動が必要)
      
      A – 4,9,7,5,8
      B – 6,2
      C – 3,1
      
      この例は、前の 2 つよりも少し難しいです。
      
      9 は、上に 3 つのリング (7,5,8) を持つ A に貼り付けられていることに注意してください。また、BとCは無料のペグではありません。無料のペグに8,7を置く必要性は明らかです。そうでなければ9のための無料のペグはありません。
      
      これを行う最善の方法は、ペグCに8,7を配置し、Cの8,7のトップに6を移動することです。
      
      これが完了した後、ペグBは9を受け取って自由になります。ただし、7 を解放する前に、B の 6 の上に 5 を配置する必要があります。
      
      ステップ 1 - C 上に 8 を配置し、6,5,3,2,1 を B に配置します。
      
      最初の 7 つの移動は次のとおりです。
      2 オン A
      1 オン A
      トップBの3(6の上)
      1 オン C
      2 オン B
      1 オン B
      8 on C
      
      開始後23の動き は、我々はレイアウトを取得します
      
      A – 4,9
      B – 6,5,3,2,1 23の動き
      C – 8,7
      
      ステップ2 – 8,7の上にC上に6,5,3,2,1(5つのリング)を置きます(ペグBは9を自由に配置することができます)。
      
      別のペグに5リングを移動するには、31の動きとBに9を配置する別の動きが必要なので、このステップでは 31 +1 =32の移動が 必要です。
      
      レイアウトは
      
      A – 4
      B – 9 31+1= 32移動
      C – 8,7,6,5,3,2,1
      
      ステップ3 - 今の目的は、7を受け取るためにペグAを解放することです(そうでなければ、9の上に8を置くすることはできません)。これを達成するには、6,5,3,2,1を9の上にBに移動する必要があります。
      
      しかし、動きはBに6を置くために交互に行われるので、以前は5をAに、4をB.に置く必要があります。
      
      ステップ2の開始から 57 移動後、次のレイアウトになります。
      
      A - 7
      B – 9,6,5,4,3,2,1 57の動き
      C – 8
      
      これらの57の動きが論理に従わなければならないことは明らかです。実際、以下のアクションで分解することができます
      
      

      アクション	移動数
      4 オン B	1
      Bのトップ4に3,2,1(3リング)	7
      5 から A へ	1
      4,3,2,1(4リング) から A	15
      6 から B へ	1
      5,4,3,2,1 (5リング) から B へ 6 個	31
      7 から A へ	1
      合計	57

      
      
      ステップ4 - 7の上にAに6,5.....2.1(6リング)を移動します。これには63の動きが必要です。 これで、B の 9 の上に 8 を配置することが可能になり、追加の移動が行われます。
      
      したがって、このステップ4では合計63+1 = 64の動きがあります
      
      これが完了すると、レイアウトは
      
      A – 7,6,5,4,3,2,1
      B – 9,8, 63+1=64 (ハノイ1の塔状況)
      C –
      
      ステップ5 - 最後のステップは、移動することです 7,6,...2,1は9,8の頂上にBをペグする。
      
      7つのリングを動かすには、127の移動が必要になります。
      
      したがって、総移動は 23 +32+57+64+127=303必要 最小限の移動です

フォーラムに、入れ子になったリストや表、下線をどのように投稿したのですか？