理解迭代求解河内塔的机制

The following code implements the Towers of Hanoi iteratively:

def towers_of_hanoi(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:
        - A disk can be moved if its the uppermost disk on a stack
        - No disk may be placed on top of a smaller disk
        - One of the towers could be empty, so we can only move to it and not from it
        """
        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

        # only one disk can be moved at a time
        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 - source stack
    B - Auxiliary stack
    C - destination stack
    """
    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)

If n = 4, we get the following output:

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!

However, I do not quite understand the following sections in the function hanoi:

  1. 当磁盘数量为偶数时,为什么要翻转辅助/辅助钉和目标钉?
if n % 2 == 0:
    helper, dest = dest, helper
  1. Why do we mod 3 and how does that influence the moves between the source, destination and helper pegs?
if i % 3 == 1:
   valid_moves(src, dest)

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

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

如果可能,请分享资源,以帮助阐明机制。

评论