作者ireullin (raison detre)
看板Ruby
標題[問題] 河內塔的演算法
時間Thu Sep 20 12:25:26 2012
這問題不知道在這邊問妥不妥當
如果不適合的話請跟我說
我會把他刪掉
以下是我寫的河內塔程式
可以將每個碟子移動的過程畫出來方便觀察
演算法是參考網路上很多的範例所寫的
可是我對於各碟子移動的規則
還是看不出一個所以然來
是否有人可以幫我解釋一下
或是網路上有更詳細說明可以與我分享
$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
1F：推 mars90226:簡單來說，有三個地方可放碟子，大碟子要在小碟子下面 09/20 14:15
2F：→ mars90226:然後把全部碟子從一個地方一到另一個地方 09/20 14:16
3F：推 sand1050:正常是畫樹狀 看就很清楚了 09/20 15:47
4F：推 SansWord:重點在遞迴規則： 09/22 11:44
5F：→ SansWord:把一個高度為 n 的塔從 A 移動到 C = 09/22 11:45
6F：→ SansWord:先把高度為 n-1 的塔從 A 移動到 B, 在把最底下那片 09/22 11:45
7F：→ SansWord:從 A 放到 C, 在把剛剛移動到 B 的 n-1 的塔移動到 C 09/22 11:46
8F：→ SansWord:收斂條件是當 n 為 1, 則直接把那片移動過去目的地即可 09/22 11:46
9F：→ SansWord:honai 這個method 就是在形容這件事 09/22 11:47
10F：→ SansWord:move_top 則是移動一片使用的 method 09/22 11:47
11F：→ SansWord:這樣懂了嗎 09/22 11:47
12F：→ SansWord:移動次數上的分析是 hanai(n) = 2 * hanai(n-1) + 1 09/22 11:48
13F：→ mars90226:樓上小心板規中的推文限制XD 09/23 09:36
14F：→ godfat:是的，下次請避免推太多，直接回文即可 O_o 09/24 02:35
15F：→ SansWord:喔抱歉....一推就推過頭.... 09/27 01:20