python请用递归算法编程解决汉诺塔问题 在线等

Python018

python请用递归算法编程解决汉诺塔问题 在线等,第1张

这是Python3系统自带的一个例子，估计就是这个意思，本来他是6个盘子，按照你要求改成4个了。递归算法没问题，描述也非常详细 ；）

#!/usr/bin/env python3

from turtle import *

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/6., 0, 1-n/6.)

        self.st()

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))

        self.append(d)

    def pop(self):

        d = list.pop(self)

        d.sety(150)

        return d

def hanoi(n, from_, with_, to_):

    if n > 0:

        hanoi(n-1, from_, to_, with_)

        to_.push(from_.pop())

        hanoi(n-1, with_, from_, to_)

def play():

    onkey(None,"space")

    clear()

    try:

        hanoi(6, t1, t2, t3)

        write("press STOP button to exit",

              align="center", font=("Courier", 16, "bold"))

    except Terminator:

        pass  # turtledemo user pressed STOP

def main():

    global t1, t2, t3

    ht() penup() goto(0, -225)   # writer turtle

    t1 = Tower(-250)

    t2 = Tower(0)

    t3 = Tower(250)

    # make tower of 6 discs

    for i in range(4,0,-1):

        t1.push(Disc(i))

    # prepare spartanic user interface -)

    write("press spacebar to start game",

          align="center", font=("Courier", 16, "bold"))

    onkey(play, "space")

    listen()

    return "EVENTLOOP"

if __name__=="__main__":

    msg = main()

    print(msg)

    mainloop()

这是一个典型的递归程序

当只有一层的时候，直接把x放到z上结束

当大于1层的时候，先把x和z放到y上，然后继续递归

把y放到x上，然后放到z上，结束处理

解汉诺塔最简单的做法就是递归:

类似如何将大象装进冰箱：1）将冰箱门打开；2）把大大象放进去；3）把冰箱门关上……

我们将所有的盘都在同一个杆上从大到小排列视为【完美状态】，那么，目标就是将最大盘片为n的完美状态从a杆移到b杆，套用装大象的思路，这个问题同样是三步：

1）把n-1的完美状态移到另一个杆上；

2）把n移到目标杆上；

3）把n-1的完美状态移到目标杆上。

如下：