作者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