我正在尝试找出如何在下面的函数hanoi_2
中为Hanoi Towers问题实现非递归算法,但是我不知道如何继续...
它引发错误:“无法从空列表中弹出”。当我输入奇数时,它以某种方式起作用,但是,当第三回合通过时,出现了问题。当输入偶数作为光盘数量时,程序甚至无法启动。
怎么了?
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())
最佳答案
光盘偶数的问题在于堆栈交换不正确:您似乎想循环三个堆栈(由于丢失了对原始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)