河内塔与相邻的限制

Question

解决tower of hanoi与相邻的限制。 我试图环顾四周，但找不到任何导致它的地方。

我试过到目前为止是：

def hanoi(n, source, helper, target): 
    print "hanoi(", n, source, helper, target, " called" 
    if n>0: 
     hanoi(n-1, source, helper, target) 
     if source[0]: 
      if source[0][-1] == 1: 
       move(source, helper) 
       move(helper, target) 
     else: 
      move(source, helper) 
      hanoi(n-1, target, helper, source) 
    hanoi(n-1, helper, target, source) 
    hanoi(n-1, source, helper, target) 

def move(s, d): 
    disk = s[0].pop() 
    print "moving " + str(disk) + " from " + s[1] + " to " + d[1] 
    d[0].append(disk) 

source = ([2,1], "source") 
target = ([], "target") 
helper = ([], "helper") 
hanoi(len(source[0]),source,helper,target) 

只适用于2个磁盘。 感谢

我发现这个漂亮的数学解释http://www.cse.cuhk.edu.hk/~chi/csc2110-2009/notes/T10.pdf

Answer 1

一个详细的实施

乍一看它看起来好像你必须区分在那里你可以从电流源直接移动到当前目标的情况下，以及那些必须分两步移动最大磁盘的磁盘。下面的实现确实是：

class Stack(object): 
    def __init__(self, index, name, disks): 
     self.index = index 
     self.name = name 
     self.disks = disks 
    def __str__(self): 
     return self.name 
    def __repr__(self): 
     return 'Stack(%r, %r, %r)' % (self.index, self.name, self.disks) 
    def is_adjacent(self, other): 
     return other.index in (self.index + 1, self.index - 1) 
    def push(self, disk): 
     assert len(self.disks) == 0 or self.disks[-1] > disk 
     self.disks.append(disk) 
    def pop(self): 
     return self.disks.pop() 

class Hanoi(object): 

    def __init__(self, n): 
     source = Stack(0, "source", range(n, 0, -1)) 
     helper = Stack(1, "helper", []) 
     target = Stack(2, "target", []) 
     self.stacks = [source, helper, target] 
     self.hanoi(n, source, target) 

    def hanoi(self, n, source, target): 
     """Move n disks from source to target using remaining stack""" 
     helper = self.stacks[3 - source.index - target.index] 
     if n == 0: 
      return 
     if source.is_adjacent(target): 
      self.hanoi(n - 1, source, helper) 
      self.move(source, target) 
      self.hanoi(n - 1, helper, target) 
     else: 
      assert helper.is_adjacent(source) and helper.is_adjacent(target) 
      self.hanoi(n - 1, source, target) 
      self.move(source, helper) 
      self.hanoi(n - 1, target, source) 
      self.move(helper, target) 
      self.hanoi(n - 1, source, target) 

    def move(self, s, d): 
     assert s.is_adjacent(d) 
     disk = s.pop() 
     print "moving %d from %s to %s" % (disk, s, d) 
     d.push(disk) 

Hanoi(5) 

的Stack对象有助于保持你的堆栈在一起的一个所有的东西：名称，位置，与邻居关系，磁盘的当前序列。如果添加了第三个元素来容纳该索引，则可以使用元组，但我认为OOP更直观。

Hanoi类将一组堆栈连在一起。这允许hanoi方法只指定源和目标，而推断第三个堆栈。你可以用不同的代码进行编码，但是我发现省略助手使这些递归调用更容易理解：现在对于单磁盘move和多磁盘hanoi，指定源和目标，并且没有第三个堆栈。

间为了简化

现在，如果你仔细看，你会发现，递归调用，始终是不相邻的堆栈。因此，如果您的堆栈顺序确实是源和目标不相邻，那么所有递归调用将使用我的代码的else分支，并且可以缩短事情以避免区分大小写，并始终使用该分支。尽管如此，我发现上面更详细的代码更容易理解。