Lotplace

又翻作河內塔/漢諾塔，經典的遞迴問題，
印象中第一次碰到這問題的時候，
是待在高職的選手室，啃著一本《零基礎學算法》苦練武功，
沒想到一晃眼就過了快十年QQ
當時沒有離散跟歸納法的觀念，
解法都是靠公式與條件硬背下來的，
到了現在準備研究所的考試，
才發現過去拼了老命通過的高牆，如今只是通往未來的一小道門檻，
人生果然是隨著年齡等級提高難度的糞GAME。

條件歸納

河內塔的運作可以簡化成三個步驟:
1. 起始塔上n-1個盤子放到暫存塔
2. 起始塔第n(最大的)盤子放到目標塔
3. 暫存塔的n-1個盤子放到目標塔

終止條件: 當起始塔只剩一個盤子時，直接放到目標塔。
初始條件: A塔為起始塔 B塔為暫存塔 C塔為目標塔

GOLANG

package main

import "fmt"

//河內塔
func hanoi(n int, a, b, c byte) int {
    if n == 1 {
        //A塔上只剩一個盤子時 直接放到C塔
        fmt.Printf("%c => %c (disk: %d)\n", a, c, n)
        return 1
    } else {
        steps := 0
        //A塔上有多個盤子時，先把n - 1個盤子從A塔放到B塔，
        steps += hanoi(n-1, a, c, b)
        //然後將第n個盤子A塔移動到C塔
        fmt.Printf("%c => %c (disk: %d)\n", a, c, n)
        steps++
        //最後將B塔上的盤子放回C塔
        steps += hanoi(n-1, b, a, c)
        return steps
    }
}

func main() {
    fmt.Println("input disk count n:")
    var n int
    fmt.Scanf("%d", &n)
    fmt.Printf("hanoi(%d) = %d\n", n, hanoi(n, 'A', 'B', 'C'))
}

---

Filed under: 演算法 - @ 2021 年 7 月 8 日 下午 4:30

標籤: algo, recursive