python - 汉诺塔非递归函数

Question

我试图找出如何在下面的函数 hanoi_2 中实现汉诺塔问题的非递归算法，但我不知道如何继续...

它抛出一个错误:“无法从空列表中弹出”。当我输入奇数时，它会以某种方式起作用，但是，当第三轮通过时，事情就会出错。当输入偶数作为光盘数量时，程序甚至不会启动。

出了什么问题？

from turtle import *
from tkinter import *  # used for the dialog box
from tkinter.simpledialog import askinteger  # used for the dialog box
from tkinter import ttk  # used for the progress bar
import time  # used for time-related functions (in pause)
import pickle  # used to save an object to a file

class Disc(Turtle):
    def __init__(self, n):
        Turtle.__init__(self, shape="square", visible=False)
        self.pu()
        self.shapesize(1.5, n*1.5, 2)  # square-->rectangle
        self.fillcolor(n/10., 0, 1-n/10.)
        self.st()
        self.speed(11-n)  # sets the speed of movement of the rectangles (the bigger, the slower)
        self.moves = 0  # stores the number of times the disc is moved

class Tower(list):
    """Hanoi tower, a subclass of built-in type list"""
    def __init__(self, x):
        """create an empty tower. x is x-position of peg"""
        self.x = x

    def push(self, d):
        d.setx(self.x)
        d.sety(-150+34*len(self))
        d.clear()
        d.write("Moved %s times" %(str(d.moves)), align="left", font=("Courier", 16, "bold"))
        d.moves += 1  # increments the number of moves each time the disc is moved
        self.append(d)

    def pop(self):
        d = list.pop(self)
        d.sety(150)
        return d

def hanoi(n, from_, with_, to_):
    global moves
    global ans
    clear()
    if n > 0:
        hanoi(n-1, from_, to_, with_)
        moves += 1  # amount of total moves is incremented
        to_.push(from_.pop())
        hanoi(n-1, with_, from_, to_)
    sety(-255)
    write("Total moves: %s" % (moves), align="center", font=("Courier", 16, "bold"))
    sety(-320)
    progress_bar(ans)  # calls progress bar function

def hanoi_2(n, A, B, C):
    global moves
    clear()
    if n%2==0:
        B=C
        C=A
        A=B
    for i in range(1,(2**n)-1):
        if i%3==1:
            C.push(A.pop())
        if i%3==2:
            B.push(A.pop())
        if i%3==0:
            B.push(C.pop())

Answer 1

偶数个光盘的问题是堆栈交换不正确:您似乎想要循环三个堆栈(因为您丢失了对原始 B 列表的引用，所以您以错误的方式执行此操作)，而实际上你只需要交换B和C堆栈，你可以这样做:

B, C = C, B

该算法的问题在于，尽管您拥有所涉及的两个堆栈(基于 i%3)，但您仍然必须确定所涉及的两个堆栈中哪一个是给予者，哪一个是给予者接受者，因为这并不总是相同的!最好为此编写一个函数，该函数需要两个堆栈并确定两个可能的“方向”中哪一个是有效的，然后执行该移动:

def validMove(A, B):
    if not len(A): 
        A.push(B.pop())
    elif not len(B):
        B.push(A.pop())
    elif A[-1] > B[-1]:
        A.push(B.pop())
    else:
        B.push(A.pop())

现在主要算法如下所示:

for i in range(1,2**n):
    if i%3==1:
        validMove(A, C)
    if i%3==2:
        validMove(A, B)
    if i%3==0:
        validMove(B, C)