汉诺塔（Tower of Hanoi）
📌 定义
汉诺塔是一个经典的递归问题：有三根柱子A、B、C，A柱上有n个盘子（从小到大叠放），要求将所有盘子从A柱移动到C柱，移动规则：
- 每次只能移动一个盘子
- 大盘子不能放在小盘子上面
- 可以使用B柱作为辅助
初始状态: 目标状态:
A B C A B C
| | | | | |
- | | | | -
-- | | | | --
--- | | | | ---
核心思路
使用递归分治思想：
- 将n-1个盘子从A移到B（使用C作为辅助）
- 将最大的盘子从A移到C
- 将n-1个盘子从B移到C（使用A作为辅助）
n=3的情况:
步骤1: 将2个盘子从A移到B
A B C
| - |
| -- |
--- | |
步骤2: 将最大盘子从A移到C
A B C
| - |
| -- |
| | ---
步骤3: 将2个盘子从B移到C
A B C
| | -
| | --
| | ---
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(2^n) | 移动次数 = 2^n - 1 |
| 空间复杂度 | O(n) | 递归调用栈深度 |
| 最少步数 | 2^n - 1 | 已被证明是最优解 |
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
func hanoi(n int, source, target, auxiliary rune) {
if n == 1 {
fmt.Printf("移动盘子 1 从 %c 到 %c\n", source, target)
return
}
hanoi(n-1, source, auxiliary, target)
fmt.Printf("移动盘子 %d 从 %c 到 %c\n", n, source, target)
hanoi(n-1, auxiliary, target, source)
}
type Move struct {
From rune
To rune
}
func hanoiMoves(n int) []Move {
var moves []Move
var move func(int, rune, rune, rune)
move = func(n int, source, target, auxiliary rune) {
if n == 1 {
moves = append(moves, Move{source, target})
return
}
move(n-1, source, auxiliary, target)
moves = append(moves, Move{source, target})
move(n-1, auxiliary, target, source)
}
move(n, 'A', 'C', 'B')
return moves
}
func main() {
n := 3
fmt.Printf("汉诺塔: %d个盘子\n", n)
hanoi(n, 'A', 'C', 'B')
totalMoves := int(math.Pow(2, float64(n))) - 1
fmt.Printf("\n总共需要 %d 步\n", totalMoves)
}思路展开
递归树（n=3）
hanoi(3, A, C, B)
/ | \
hanoi(2,A,B,C) 移动3:A->C hanoi(2,B,C,A)
/ | \ / | \
hanoi(1,A,C,B) 移2:A->B hanoi(1,C,B,A) hanoi(1,B,A,C) 移2:B->C hanoi(1,A,C,B)
| | | |
移1:A->C 移1:C->B 移1:B->A 移1:A->C
移动序列:
1. A -> C
2. A -> B
3. C -> B
4. A -> C
5. B -> A
6. B -> C
7. A -> C
移动次数推导
T(n) = 移动n个盘子需要的步数
T(1) = 1
T(n) = T(n-1) + 1 + T(n-1)
= 2*T(n-1) + 1
展开:
T(n) = 2*T(n-1) + 1
= 2*(2*T(n-2) + 1) + 1
= 2²*T(n-2) + 2 + 1
= 2³*T(n-3) + 2² + 2 + 1
= ...
= 2^(n-1)*T(1) + 2^(n-2) + ... + 2 + 1
= 2^(n-1) + (2^(n-1) - 1)
= 2^n - 1
经典题目
基础应用
- 汉诺塔问题 - 面试题 08.06
变体问题
- 四柱汉诺塔（Frame-Stewart算法）
- 限制移动方向的汉诺塔
- 汉诺塔II：只能相邻柱子移动
💡 变体问题
⚖️ 优缺点
优点
- ✅ 递归典范：完美展示递归思想
- ✅ 数学之美：移动次数2
- ✅ 教学价值：帮助理解分治和递归
缺点
- ❌ 指数复杂度：O(2
- ❌ 实际应用少：主要用于教学
🎨 应用场景
- 教学工具：递归和分治思想的经典例子
- 备份系统：分层数据迁移
- 游戏设计：益智游戏的基础
- 算法思维：培养递归思维
🔍 数学性质
1. 最少移动次数
移动n个盘子需要的最少步数：
T(n) = 2^n - 1
证明：
- T(1) = 1
- T(n) = 2*T(n-1) + 1
- 递推得 T(n) = 2^n - 1
2. 格雷码关系
汉诺塔的移动序列与格雷码（Gray Code）一一对应：
- 每一步移动对应格雷码的一位变化
- 第i步移动的盘子编号 = 第i个格雷码变化的位
3. 传说故事
传说中有64个金盘的汉诺塔，僧侣每天移动一个盘子：
2^64 - 1 ≈ 1.844 × 10^19 步
按每秒一步计算：约5850亿年