zz:Ruby program 汉诺塔
程序员文章站
2022-07-14 21:25:06
...
汉诺塔(又称河内塔)问题是印度的一个古老的传说。
开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。当所有金片都按照规则移到另一个棒上之时就是世界毁灭之时。
已经证明当金片数量为 n 时,需要搬运 2 的 n 次方 - 1 次。所以上述64个金片按照规则需要移动18446744073709551615次才行。假设和尚们一秒钟能搬动一次金片,昼夜不息,轮班操作,至少需要搬运五千八百四十九亿年以上。而地球到目前为止也仅仅存活了46亿年,所以地球末日应该还早 …… ^ - ^
现在我们把汉诺塔当成一个游戏,比如给你 n 个金片,三根金刚石棒分别为A,B,C,初始金片都在A上,最终要求都转移到C上,你会怎么搬运?
递归解法
非递归解法
开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着64个圆的金片,最大的一个在底下,其余一个比一个小,依次叠上去,庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上,规定可利用中间的一根棒作为帮助,但每次只能搬一个,而且大的不能放在小的上面。当所有金片都按照规则移到另一个棒上之时就是世界毁灭之时。
已经证明当金片数量为 n 时,需要搬运 2 的 n 次方 - 1 次。所以上述64个金片按照规则需要移动18446744073709551615次才行。假设和尚们一秒钟能搬动一次金片,昼夜不息,轮班操作,至少需要搬运五千八百四十九亿年以上。而地球到目前为止也仅仅存活了46亿年,所以地球末日应该还早 …… ^ - ^
现在我们把汉诺塔当成一个游戏,比如给你 n 个金片,三根金刚石棒分别为A,B,C,初始金片都在A上,最终要求都转移到C上,你会怎么搬运?
递归解法
$step = ['A', 'B', 'C'] def hano1(n, from, to) if n == 1 # puts from + "->" + to return end rest = ($step - [to, from])[0] hano1(n - 1, from, rest) hano1(1, from, to) hano1(n - 1, rest, to) end hano1(4, 'A', 'C')
非递归解法
def move(from, to) p $step[from] + "->" + $step[to] $hn[to].unshift($hn[from].shift) p $hn end def hano2(n) $hn = [(1..n).to_a, [], []] if n % 2 == 0 $step = ['A', 'B', 'C'] last_pos = 2 else $step = ['A', 'C', 'B'] last_pos = 1 end pos_1 = 0 until $hn[last_pos].size == n new_pos_1 = pos_1 + 1 new_pos_1 = 0 if new_pos_1 == 3 move(pos_1, new_pos_1) pos_1 = new_pos_1 break if $hn[last_pos].size == n pos_2 = ([0, 1, 2] - [pos_1])[0] pos_3 = ([0, 1, 2] - [pos_1])[1] if $hn[pos_2].size == 0 move(pos_3, pos_2) elsif $hn[pos_3].size == 0 move(pos_2, pos_3) elsif $hn[pos_2][0] < $hn[pos_3][0] move(pos_2, pos_3) else move(pos_3, pos_2) end end end hano2(4)
下一篇: WEB免费打印控件推荐(4款)