河內塔與相鄰的限制

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分支，並且可以縮短事情以避免區分大小寫，並始終使用該分支。儘管如此，我發現上面更詳細的代碼更容易理解。