[問題] 河內塔的演算法

[ireullin (raison detre)]

這問題不知道在這邊問妥不妥當
如果不適合的話請跟我說
我會把他刪掉

以下是我寫的河內塔程式
可以將每個碟子移動的過程畫出來方便觀察
演算法是參考網路上很多的範例所寫的
可是我對於各碟子移動的規則
還是看不出一個所以然來
是否有人可以幫我解釋一下
或是網路上有更詳細說明可以與我分享



$src = Array.new
$tmp = Array.new
$des = Array.new
$disk = 3

# 組合出橫向的線
def draw_line(q, index, height)
        _rc = ''
        i = index - (height - q.size)
        if(i<0)
                _rc << ' '*(height-1) << "||" << ' '*(height-1)
        else
                _rc << ' '*(height-q[i]) << "=="*(q[i]) << ' '*(height-q[i])
        end

        return _rc
end


# 畫出目前的狀態
def pirnt_queue
        puts ''
        _tower_height = $disk+1
        0.upto(_tower_height-1) do |i|
                _line = ''
                _line << draw_line($src, i, _tower_height)
                _line << draw_line($tmp, i, _tower_height)
                _line << draw_line($des, i, _tower_height)
                puts _line
        end
end


# 移動最上面的碟子
def move_top(q_src, q_des)
        q_des.insert(0, q_src[0])
        q_src.delete_at(0)
        pirnt_queue
end


def honai(n, q_src, q_tmp, q_des)

        if(n==1)
                move_top(q_src, q_des)
                return
        end

        honai(n-1, q_src, q_des, q_tmp)
        move_top(q_src, q_des)
        honai(n-1, q_tmp, q_src, q_des)

end


def hand_made
        move_top($src, $des)
        move_top($src, $tmp)
        move_top($des, $tmp)
        move_top($src, $des)
        move_top($tmp, $src)
        move_top($tmp, $des)
        move_top($src, $des)
end


def main
        1.upto($disk){|i|$src.push(i)}
        pirnt_queue

        #hand_made
        honai($disk, $src, $tmp, $des)

end


if($1==$FILE)
        main
end

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.220.71.34
推 mars90226:簡單來說，有三個地方可放碟子，大碟子要在小碟子下面
→ mars90226:然後把全部碟子從一個地方一到另一個地方
推 sand1050:正常是畫樹狀 看就很清楚了
推 SansWord:重點在遞迴規則：
→ SansWord:把一個高度為 n 的塔從 A 移動到 C =
→ SansWord:先把高度為 n-1 的塔從 A 移動到 B, 在把最底下那片
→ SansWord:從 A 放到 C, 在把剛剛移動到 B 的 n-1 的塔移動到 C
→ SansWord:收斂條件是當 n 為 1, 則直接把那片移動過去目的地即可
→ SansWord:honai 這個method 就是在形容這件事
→ SansWord:move_top 則是移動一片使用的 method
→ SansWord:這樣懂了嗎
→ SansWord:移動次數上的分析是 hanai(n) = 2 * hanai(n-1) + 1
→ mars90226:樓上小心板規中的推文限制XD
→ godfat:是的，下次請避免推太多，直接回文即可 O_o
→ SansWord:喔抱歉....一推就推過頭....