查看完整版本: 2008-04-18 Ruby 测试题(00013)

2008-04-18 Ruby 测试题(00013)

今天是经典题，汉诺塔。
简单介绍一下背景：开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
题目要求，针对输入的金片数量N，显示整个搬运过程。
三根金刚石棒分别为A，B，C，初始金片都在A上，最终要求都转移到C上。
输出是这样的：
第1步：A-->B
第2步：A-->C
第1步：C-->B
。。。
。。。

回忆递归中...
**** Hidden Message *****

这不是传说中的，汉诺塔么？

看一下。。

虽说是经典问题但一直没空做一下（或者说懒得做）
今天终于有机会了。:lol

**** Hidden Message *****

回复 2# 的帖子

我觉得次数没必要累加计算，肯定是 2 ** n - 1
直接打印具体搬法就行。

你们都太快了......

学习下。。

召唤非递归算法

非递归算法来了

速度虽然慢一点，不过每一步的状况都可以看的很清楚

**** Hidden Message *****

hano2(4)

"A->B"
[[2, 3, 4], [1], []]
"A->C"
[[3, 4], [1], [2]]
"B->C"
[[3, 4], [], [1, 2]]
"A->B"
[[4], [3], [1, 2]]
"C->A"
[[1, 4], [3], [2]]
"C->B"
[[1, 4], [2, 3], []]
"A->B"
[[4], [1, 2, 3], []]
"A->C"
[[], [1, 2, 3], [4]]
"B->C"
[[], [2, 3], [1, 4]]
"B->A"
[[2], [3], [1, 4]]
"C->A"
[[1, 2], [3], [4]]
"B->C"
[[1, 2], [], [3, 4]]
"A->B"
[[2], [1], [3, 4]]
"A->C"
[[], [1], [2, 3, 4]]
"B->C"
[[], [], [1, 2, 3, 4]]

[[i] 本帖最后由 bbschat 于 2008-4-23 19:07 编辑 [/i]]

支持,先看下答案咯

郁闷死了，白天想到晚上还是没有想出来，无奈看看答案吧。:( :Q

#主要代码块：
def movehano(n, from, to, tmp)
  if n == 1
    to.push(from.pop)
    return
  end
  
  hano(n - 1, from, tmp, to)
  hano(1, from, to, tmp)
  hano(n - 1, tmp, to, from)
end

#验证：
n = 10
a, b, c = [], [], []

#a = [n, n-1, n-2, ...1]
n.times {|i| a[i] = n - i}

movehano(n, a, c, b)

print "a:", a * "-", "\n"
print "b:", b * "-", "\n"
print "c:", c * "-", "\n"

#上述程序再加上显示移动过程的代码，基本完整了应该。:loveliness:

另类点的解法[code]def hano(n)
  from = (n % 2 == 0)?3:2
  to = 1
  h=[]
  h[1]=[n+1]
  h[2]=[n+1]
  h[3]=[n+1]
  n.downto(1){|i| h[1]<<i}
  1.upto(2**n-1){|i|
    if i % 2 == 1
      printf "%s->%s\n",(to+64).chr,(6-from-to+64).chr
      h[6-from-to]<<h[to].pop
      from,to=to,(6-from-to)
    else
      if h[from].last < h[6-from-to].last
        printf "%s->%s\n",(from+64).chr,(6-from-to+64).chr
        h[6-from-to]<<h[from].pop
      else
        printf "%s->%s\n",(6-from-to+64).chr,(from+64).chr
        h[from]<<h[6-from-to].pop
      end
    end
  }
end
hano(5)[/code]

**** Hidden Message *****

初次发帖，只记得c++时代的解法了

**** Hidden Message *****

初次发帖，只记得c++时代的解法了

路过，学习一下

**** Hidden Message ***** 我的短 哈哈

[[i] 本帖最后由 acnono 于 2008-8-21 15:56 编辑 [/i]]

继续疯狂中，膜拜中！

了解一下~