汉诺塔：将递归解决方案建模为非递归解决方案

Question

我正在尝试使用河内塔拼图的递归和迭代方法来解决问题。

f refers to from/source, helper - auxiliary/intermediate position, t - target/destination

这里是递归实现，我们只打印移动：

def towers_of_hanoi_v1(n):
    """
    Recursive approach
    """

    def move(f, t):
        print(f"Move disc from {f} to {t}!")

    def hanoi(n, f, helper, t):
        if n:
            hanoi(n - 1, f, t, helper)
            move(f, t)
            hanoi(n - 1, helper, f, t)

    return hanoi(n, "A", "B", "C")

我将上面的内容转换为 iterative solution 的尝试如下：

class Disc:
    def __init__(self, size):
        self.size = size

def towers_of_hanoi_v2(n):
    """
    Iterative approach
    """

    def mapper(queue):
        """
        util to map queue to its respective label
        """
        if queue is A:
            label = "A"
        elif queue is B:
            label = "B"
        elif queue is C:
            label = "C"
        return label

    def move(f, t):
        """
        utility function to print moves
        """
        print(f"Move disc from {mapper(f)} to {mapper(t)}!")

    def valid_moves(giver, taker):
        """
        utility function to figure out next legal move:
        - One of the towers could be empty, so we can only move to it and not from it
        - Tower x can have a larger disk than tower y.
        """
        if not len(giver):
            giver.appendleft(taker.popleft())
            move(taker, giver)

        elif not len(taker):
            taker.appendleft(giver.popleft())
            move(giver, taker)

        elif giver[0].size > taker[0].size:
            giver.appendleft(taker.popleft())
            move(taker, giver)

        else:
            taker.appendleft(giver.popleft())
            move(giver, taker)

    def hanoi(n, src, helper, dest):
        if n % 2 == 0:
            helper, dest = dest, helper

        moves = pow(2, n) - 1

        for i in range(1, moves + 1):
            if i % 3 == 1:
                valid_moves(src, dest)

            elif i % 3 == 2:
                valid_moves(src, helper)

            elif i % 3 == 0:
                valid_moves(helper, dest)

    """
    Initialise towers as stacks. We use stacks so that we can always look at
    the current top disk and compare the sizes between top disks of two towers
    """
    A = collections.deque(maxlen=n)
    B = collections.deque(maxlen=n)
    C = collections.deque(maxlen=n)

    """
    Populate initial tower while assigning sizes
    sizes will be crucial as we can not move a large disk onto a small disk
    """
    for i in reversed(range(n)):
        A.append(Disc(n - i))

    return hanoi(n, A, B, C)

合并。迭代的方式需要辅助数据结构，我用的是栈：

n = 4    

Recursive approach:
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from A to B!
Move disc from C to A!
Move disc from C to B!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from B to A!
Move disc from C to A!
Move disc from B to C!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
None

Iterative approach:
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from A to B!
Move disc from C to A!
Move disc from C to B!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
Move disc from B to A!
Move disc from C to A!
Move disc from B to C!
Move disc from A to B!
Move disc from A to C!
Move disc from B to C!
None

你有更简洁的方法吗？

Answer 1

如果您查看您的解决方案，它几乎是正确的，但它没有考虑验证合法移动的条件。

例如，在n=2中，B和C之间会有一个移动。但是你必须决定正确的交换方向。

可以有很多种情况，

其中一个塔可能是空的，所以我们只能移动到它而不能离开它。
塔 x 可以比塔 y 有更大的磁盘。

因此，您应该使用 list/stack 来实现它，您可以随时查看当前的顶部磁盘并比较两个塔的顶部磁盘之间的大小。然后，在每次移动之前，你必须根据游戏规则决定正确的移动方向。

汉诺塔：将递归解决方案建模为非递归解决方案

Towers of Hanoi: Model recursive solution to a non-recursive solution

python

recursion

iteration

towers-of-hanoi