汉诺塔递归算法
- 算法实现
// 从 a -> b 经过 c 中转
func Hanoi(size int, a, b, c byte) {
if size == 1 {
fmt.Printf("%c -> %c\n", a, b)
} else {
Hanoi(size-1, a, c, b)
fmt.Printf("%c -> %c\n", a, b)
Hanoi(size-1, c, b, a)
}
}
- 测试代码
func main() {
function.Hanoi(3, 'A', 'B', 'C')
}
- 结果
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
- 时间复杂度
O(2^n)
