3

解决具有相邻限制的河内塔。我试图环顾四周，但找不到任何线索。

到目前为止我尝试过的是：

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

4

1 回答 1

2

详细的实现

乍一看，您似乎必须区分可以直接从当前源移动到当前目标的情况，以及必须分两步移动最大磁盘的情况。以下实现可以做到这一点：

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我的代码的分支，并且您可以缩短内容以避免区分大小写并始终使用该else分支。不过，就正在发生的事情而言，我发现上面更冗长的代码更容易理解。

于 2013-03-21T11:32:19.130 回答