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:
- 当磁盘数量为偶数时，为什么要翻转辅助/辅助钉和目标钉？
if n % 2 == 0:
helper, dest = dest, helper
- Why do we
mod3 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)
如果可能，请分享资源，以帮助阐明机制。
