【Python3】ハノイの塔 (paizaランク A 相当)をやってみた

ハノイの塔のプログラムは、与えられた n 個の円盤を杭Aから杭Cに最短手順で移動する際の t 回目の状態を出力します。

コードの手順:

1. ハノイの塔の状態を再帰的にシミュレート。
2. 特定の手順数 t における状態を記録。
3. 各杭の状態を出力。

def hanoi(n, t):
    # 初期状態の設定
    pegs = [list(range(n, 0, -1)), [], []]
    moves = []

    # ハノイの塔の再帰的な移動関数
    def move_disks(num_disks, from_peg, to_peg, aux_peg):
        if num_disks == 0:
            return
        move_disks(num_disks - 1, from_peg, aux_peg, to_peg)
        if len(moves) < t:
            disk = pegs[from_peg].pop()
            pegs[to_peg].append(disk)
            moves.append((from_peg, to_peg))
        move_disks(num_disks - 1, aux_peg, to_peg, from_peg)

    # 再帰的に円盤を動かす
    move_disks(n, 0, 2, 1)

    # 各杭の状態を出力
    for peg in pegs:
        if peg:
            print(" ".join(map(str, peg)))
        else:
            print("-")

# 標準入力からの入力を受け取る
import sys
input = sys.stdin.read().strip()
n, t = map(int, input.split())

# ハノイの塔のシミュレーションと出力
hanoi(n, t)

コードの説明:

1. 初期状態の設定:

   • pegs というリストを使って各杭の状態を表現します。最初は杭Aに n 個の円盤が大きい順に積まれています。
   • moves というリストで移動を記録します。

2. ハノイの塔の再帰的な移動関数 move_disks:

   • num_disks 個の円盤を from_peg から to_peg に aux_peg を使って移動します。
   • 基本ケースでは何もしません (num_disks == 0)。
   • 再帰的に num_disks - 1 個の円盤を補助の杭に移動し、一番大きい円盤を目的の杭に移動します。
   • moves リストが t より短い場合のみ円盤を移動し、その状態を記録します。
   • 残りの num_disks - 1 個の円盤を補助の杭から目的の杭に移動します。

3. 各杭の状態を出力:

   • 各杭 (peg) の状態を出力します。空の杭は "-" と表示します。

このプログラムを実行すると、指定された n と t に対して、各杭の状態を適切に出力します。