【Python3】ハノイの塔 (paizaランク A 相当)：アルゴリズム付きの解説

要求分析

• 3つの杭（A、B、C）があり、杭Aには n 個の円盤が大きい順に積まれている。
• n 個の円盤を最短手順で杭Aから杭Cに移動させる。
• t 回の移動後の各杭の状態を出力する。

アルゴリズム

1. 初期状態を設定し、各杭に円盤を配置。
2. 再帰的に円盤を移動する関数 move_disks を定義。
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:

3 4

出力例1:

-
2 1
3

入力例2:

4 6

出力例2:

4 1
3 2
-

解説

1. n と t を標準入力から読み込む。
2. pegs は3つの杭を表し、初期状態では全ての円盤が pegs[0] に積まれている。
3. moves リストは円盤の移動を記録し、t 回移動する。
4. move_disks 関数は再帰的に円盤を移動する。
5. 最終的な各杭の状態を出力する。

このコードは指定された t 回の移動後の杭の状態を正確に出力します。