欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

zz:Ruby program 汉诺塔  

程序员文章站 2022-07-14 21:25:06
...
汉诺塔(又称河内塔)问题是印度的一个古老的传说。

开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒,第一根上面套着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)