漢諾塔遞歸算法
- 算法實(shí)現(xiàn)
// 從 a -> b 經(jīng)過 c 中轉(zhuǎn)
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')
}
- 結(jié)果
A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B
- 時間復(fù)雜度
O(2^n)
