Keito - 技術ブログとポートフォリオ

概要

Goでハノイの塔を再帰的に行うサンプルコード
ハノイの塔は3本の棒と複数の円盤を使う数学パズル。全ての円盤を別の棒に移動させる問題で、再帰アルゴリズムの代表例。

特徴

分割統治法: 問題を小さな部分問題に分割
再帰の美しさ: 複雑な問題をシンプルなコードで解決
指数的移動回数: 2^n - 1回の最小移動回数
数学的証明可能: 最適解が数学的に証明済み
視覚的理解: 動きをステップごとに追跡可能

動作原理

基本的な流れ：

n枚のディスクを元の棒から目的の棒へ移動
補助の棒を使って一時的にディスクを置く
大きいディスクの上に小さいディスクしか置けない
一度に動かせるのは1枚のみ

再帰的解法

n枚のディスクを棒Aから棒Cへ移動する手順：

上のn-1枚を棒Aから棒Bへ（棒C経由）
最大のディスクを棒Aから棒Cへ
n-1枚を棒Bから棒Cへ（棒A経由）

具体例

3枚のディスクの移動過程：

初期状態:        移動1後:         移動2後:
  1
  2               2              3
  3               3
-----           -----           -----
A B C           A B C           A B C
                    1            2 1

移動3後:         移動4後:         移動5後:
                                 1
  3               2              2
                  3              3
-----           -----           -----
A B C           A B C           A B C
  1 2               1

移動6後:         移動7後（完了）:
                    1
                    2
1                   3
-----           -----
A B C           A B C
    2 3

総移動回数: 7回 = 2^3 - 1

サンプルコード

基本実装

package recursion

import "fmt"

// HanoiMove は1回の移動を表す構造体
type HanoiMove struct {
    From string
    To   string
    Disk int
}

// TowerOfHanoi はハノイの塔の移動手順を返す
func TowerOfHanoi(n int, from, to, aux string) []HanoiMove {
    moves := []HanoiMove{}
    hanoiHelper(n, from, to, aux, &moves)
    return moves
}

func hanoiHelper(n int, from, to, aux string, moves *[]HanoiMove) {
    // ベースケース: 1枚の場合は直接移動
    if n == 1 {
        *moves = append(*moves, HanoiMove{From: from, To: to, Disk: n})
        return
    }

    // ステップ1: n-1枚を補助の棒へ
    hanoiHelper(n-1, from, aux, to, moves)

    // ステップ2: 最大のディスクを目的地へ
    *moves = append(*moves, HanoiMove{From: from, To: to, Disk: n})

    // ステップ3: n-1枚を目的地へ
    hanoiHelper(n-1, aux, to, from, moves)
}

ステップ表示版

// TowerOfHanoiWithSteps は再帰呼び出しの過程を表示
func TowerOfHanoiWithSteps(n int, from, to, aux string, depth int) {
    indent := ""
    for i := 0; i < depth; i++ {
        indent += "  "
    }

    fmt.Printf("%sHanoi(%d, %s, %s, %s) を呼び出し\\\\n", indent, n, from, to, aux)

    if n == 1 {
        fmt.Printf("%s  ディスク1を%sから%sへ移動\\\\n", indent, from, to)
        return
    }

    fmt.Printf("%s  ステップ1: %d枚のディスクを%sから%sへ（%s経由）\\\\n",
               indent, n-1, from, aux, to)
    TowerOfHanoiWithSteps(n-1, from, aux, to, depth+1)

    fmt.Printf("%s  ステップ2: ディスク%dを%sから%sへ移動\\\\n",
               indent, n, from, to)

    fmt.Printf("%s  ステップ3: %d枚のディスクを%sから%sへ（%s経由）\\\\n",
               indent, n-1, aux, to, from)
    TowerOfHanoiWithSteps(n-1, aux, to, from, depth+1)
}

シミュレーション版

// SimulateTowerOfHanoi は移動過程を視覚的に表示
func SimulateTowerOfHanoi(n int) {
    // 3本の棒を初期化
    towers := map[string][]int{
        "A": make([]int, 0),
        "B": make([]int, 0),
        "C": make([]int, 0),
    }

    // 初期状態: 全てのディスクを棒Aに配置
    for i := n; i >= 1; i-- {
        towers["A"] = append(towers["A"], i)
    }

    fmt.Printf("初期状態（%d枚のディスク）:\\\\n", n)
    PrintHanoiState(towers)

    // 移動手順を取得
    moves := TowerOfHanoi(n, "A", "C", "B")

    // 各移動を実行
    for i, move := range moves {
        fmt.Printf("移動 %d: ディスク%dを%sから%sへ\\\\n",
                   i+1, move.Disk, move.From, move.To)

        // ディスクを移動
        fromTower := towers[move.From]
        disk := fromTower[len(fromTower)-1]
        towers[move.From] = fromTower[:len(fromTower)-1]
        towers[move.To] = append(towers[move.To], disk)

        PrintHanoiState(towers)
    }

    fmt.Printf("\\\\n完了！ 総移動回数: %d\\\\n", len(moves))
}

// PrintHanoiState は塔の状態を表示
func PrintHanoiState(towers map[string][]int) {
    maxHeight := 0
    for _, tower := range towers {
        if len(tower) > maxHeight {
            maxHeight = len(tower)
        }
    }

    // 上から順に表示
    for level := maxHeight - 1; level >= 0; level-- {
        for _, peg := range []string{"A", "B", "C"} {
            if level < len(towers[peg]) {
                fmt.Printf("  %d  ", towers[peg][level])
            } else {
                fmt.Print("  |  ")
            }
        }
        fmt.Println()
    }
    fmt.Println("-----+-----+-----")
    fmt.Println("  A     B     C  ")
    fmt.Println()
}

移動回数の計算

// CountHanoiMoves はn枚のディスクの最小移動回数を計算
func CountHanoiMoves(n int) int {
    return (1 << n) - 1  // 2^n - 1
}

// 使用例
func main() {
    for n := 1; n <= 10; n++ {
        moves := CountHanoiMoves(n)
        fmt.Printf("%2d枚: %d回\\\\n", n, moves)
    }
    // 出力:
    //  1枚: 1回
    //  2枚: 3回
    //  3枚: 7回
    //  4枚: 15回
    //  5枚: 31回
}

反復版（比較用）

// TowerOfHanoiIterative は反復による実装
func TowerOfHanoiIterative(n int) []HanoiMove {
    moves := []HanoiMove{}

    // 偶数と奇数で移動パターンが異なる
    if n%2 == 0 {
        moves = iterativeHanoi(n, "A", "B", "C")
    } else {
        moves = iterativeHanoi(n, "A", "C", "B")
    }

    return moves
}

func iterativeHanoi(n int, source, auxiliary, destination string) []HanoiMove {
    moves := []HanoiMove{}
    totalMoves := (1 << n) - 1

    // 各棒の状態を管理
    towers := map[string][]int{
        source:      make([]int, 0),
        auxiliary:   make([]int, 0),
        destination: make([]int, 0),
    }

    // 初期配置
    for i := n; i >= 1; i-- {
        towers[source] = append(towers[source], i)
    }

    pegs := []string{source, auxiliary, destination}

    // ビット演算を使った移動パターン
    for i := 1; i <= totalMoves; i++ {
        from := pegs[(i&(i-1))%3]
        to := pegs[((i|(i-1))+1)%3]

        // 小さいディスクを大きいディスクの上に移動
        if canMove(towers, from, to) {
            moveDisc(towers, from, to, &moves)
        } else {
            moveDisc(towers, to, from, &moves)
        }
    }

    return moves
}

計算量

時間計算量

移動回数: O(2^n) - 正確には2^n - 1回
再帰呼び出し: O(2^n) - 各ノードで2つの再帰呼び出し

空間計算量

再帰版: O(n) - 再帰スタックの深さ
反復版: O(n) - ディスクの状態を保持

ディスク枚数と移動回数

ディスク枚数	移動回数	計算式
1	1	2^1 - 1
2	3	2^2 - 1
3	7	2^3 - 1
4	15	2^4 - 1
5	31	2^5 - 1
10	1,023	2^10 - 1
20	1,048,575	2^20 - 1
64	約1,844京	2^64 - 1

使いどころ

向いてる場面

再帰アルゴリズムの教育
分割統治法の理解
問題解決思考の訓練
アルゴリズム設計の練習

実例：パズルゲーム実装

// HanoiGame はハノイの塔ゲームの実装
type HanoiGame struct {
    Towers    map[string][]int
    NumDisks  int
    MoveCount int
    History   []HanoiMove
}

func NewHanoiGame(n int) *HanoiGame {
    game := &HanoiGame{
        Towers:    make(map[string][]int),
        NumDisks:  n,
        MoveCount: 0,
        History:   []HanoiMove{},
    }

    // 初期配置
    game.Towers["A"] = make([]int, 0)
    game.Towers["B"] = make([]int, 0)
    game.Towers["C"] = make([]int, 0)

    for i := n; i >= 1; i-- {
        game.Towers["A"] = append(game.Towers["A"], i)
    }

    return game
}

// Move はディスクを移動
func (g *HanoiGame) Move(from, to string) error {
    fromTower := g.Towers[from]
    toTower := g.Towers[to]

    // 移動可能チェック
    if len(fromTower) == 0 {
        return fmt.Errorf("棒%sにディスクがありません", from)
    }

    disk := fromTower[len(fromTower)-1]
    if len(toTower) > 0 && toTower[len(toTower)-1] < disk {
        return fmt.Errorf("大きいディスクを小さいディスクの上に置けません")
    }

    // 移動実行
    g.Towers[from] = fromTower[:len(fromTower)-1]
    g.Towers[to] = append(toTower, disk)
    g.MoveCount++
    g.History = append(g.History, HanoiMove{From: from, To: to, Disk: disk})

    return nil
}

// IsComplete はパズルが完成したか判定
func (g *HanoiGame) IsComplete() bool {
    return len(g.Towers["C"]) == g.NumDisks
}

他の実装との比較

実装方法	時間計算量	空間計算量	可読性	実装難易度
再帰	O(2^n)	O(n)	◎	易
反復（ビット演算）	O(2^n)	O(n)	△	難
反復（スタック）	O(2^n)	O(n)	○	中
並列処理	O(2^n)	O(n)	△	難

最適化アイデア

パフォーマンス測定

import "time"

func BenchmarkHanoi(n int) {
    fmt.Printf("n = %d での比較:\\\\n", n)

    // 再帰版
    start := time.Now()
    recursiveMoves := TowerOfHanoi(n, "A", "C", "B")
    recursiveTime := time.Since(start)

    // 反復版
    start = time.Now()
    iterativeMoves := TowerOfHanoiIterative(n)
    iterativeTime := time.Since(start)

    fmt.Printf("再帰版: %v (%d moves)\\\\n", recursiveTime, len(recursiveMoves))
    fmt.Printf("反復版: %v (%d moves)\\\\n", iterativeTime, len(iterativeMoves))
}

並列処理版

// ParallelHanoi は並列処理を使った実装（概念的）
func ParallelHanoi(n int) []HanoiMove {
    // 左右の部分問題を並列実行
    ch1 := make(chan []HanoiMove)
    ch2 := make(chan []HanoiMove)

    go func() {
        // n-1枚を補助棒へ
        ch1 <- TowerOfHanoi(n-1, "A", "B", "C")
    }()

    go func() {
        // n-1枚を目的棒へ
        ch2 <- TowerOfHanoi(n-1, "B", "C", "A")
    }()

    // 結果を結合
    moves1 := <-ch1
    middleMove := HanoiMove{From: "A", To: "C", Disk: n}
    moves2 := <-ch2

    result := append(moves1, middleMove)
    result = append(result, moves2...)

    return result
}

メモリ効率版

// HanoiGenerator は必要に応じて移動を生成
func HanoiGenerator(n int) <-chan HanoiMove {
    ch := make(chan HanoiMove)

    go func() {
        defer close(ch)
        generateMoves(n, "A", "C", "B", ch)
    }()

    return ch
}

func generateMoves(n int, from, to, aux string, ch chan<- HanoiMove) {
    if n == 1 {
        ch <- HanoiMove{From: from, To: to, Disk: n}
        return
    }

    generateMoves(n-1, from, aux, to, ch)
    ch <- HanoiMove{From: from, To: to, Disk: n}
    generateMoves(n-1, aux, to, from, ch)
}

// 使用例
func main() {
    for move := range HanoiGenerator(3) {
        fmt.Printf("移動: ディスク%dを%sから%sへ\\\\n",
                   move.Disk, move.From, move.To)
    }
}

まとめ

メリット

エレガントな再帰解法
数学的に最適解が保証
分割統治法の良い例
実装がシンプル

デメリット

指数的な実行時間
大きなnでは実用不可
再帰スタックの制限
並列化が困難

使うべき時

アルゴリズム教育
再帰の理解
パズルゲーム実装
問題解決思考の訓練

学習ポイント

再帰的思考: 大きな問題を小さな問題に分割
数学的帰納法: ベースケースと再帰ケース
計算量の理解: 指数的増加の実感
最適性の証明: 数学的に最小手数が証明可能

ハノイの塔は再帰アルゴリズムの美しさと威力を示す最良の例。シンプルなルールから複雑な動作が生まれ、数学的な美しさとプログラミングの実用性を兼ね備えた問題。