zz:Ruby program 汉诺塔

汉诺塔（又称河内塔）问题是印度的一个古老的传说。

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