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

詳細な実装

一見すると、現在のソースから現在のターゲットに直接移動できる場合と、最大のディスクを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オブジェクトは、スタックの1つに関するすべてのもの（名前、位置、隣接関係、およびディスクの現在のシーケンス）をまとめるのに役立ちます。そのインデックスを保持するために3番目の要素を追加した場合はタプルを使用できますが、OOPの方が直感的だと思います。

Hanoiクラスはスタックのセットをまとめます。これにより、hanoiメソッドはソースとターゲットを指定するだけで、3番目のスタックが推測されます。これを別の方法でコーディングすることもできますが、ヘルパーを省略すると、これらの再帰呼び出しがはるかに理解しやすくなります。シングルディスクmoveとマルチディスクの両方で、hanoiソースと宛先を指定し、3番目のスタックはありません。

簡素化の余地

ここでよく見ると、再帰呼び出しは常に隣接していないスタックに対するものであることがわかります。したがって、スタックの順序が実際にソースとターゲットが隣接していないようなものである場合、すべての再帰呼び出しはelse私のコードのブランチを使用し、大文字と小文字の区別を避けるために短縮して、常にそのelseブランチを使用できます。ただし、上記のより冗長なコードは、何が起こっているのかという点で理解しやすいと思います。

于 2013-03-21T11:32:19.130 に答える