汉诺塔的实现

一、汉诺塔的基本实现

 1 def hanoi(n,a,b,c):
 2     global count
 3     if n==1:
 4         print("{}:{}->{}".format(1,a,b))
 5         count+=1
 6     else:
 7         hanoi(n-1,a,c,b)
 8         print("{}:{}->{}".format(n,a,b))
 9         count+=1
10         hanoi(n-1,c,a,b)
11 count = 0
12 n = eval(input("请输入汉诺塔的层数:"))
13 hanoi(n,'x','y','z')

二、汉诺塔的动态实现

 1 import turtle
 2 class Stack:
 3     def __init__(self):
 4         self.items = []
 5     def isEmpty(self):
 6         return len(self.items) == 0
 7     def push(self, item):
 8         self.items.append(item)
 9     def pop(self):
10         return self.items.pop()
11     def peek(self):
12         if not self.isEmpty():
13             return self.items[len(self.items) - 1]
14     def size(self):
15         return len(self.items)
16 
17 def drawpole_3():#底座
18     t = turtle.Turtle()
19     t.hideturtle()
20     def drawpole_1(k):
21         t.up()
22         t.pensize(20)
23         t.goto(400*(k-1), 100)
24         t.down()
25         t.goto(400*(k-1), -100)
26         t.goto(400*(k-1)-20, -100)
27         t.goto(400*(k-1)+20, -100)
28     drawpole_1(0)
29     drawpole_1(1)
30     drawpole_1(2)
31 
32 def plate(n):#盘子
33     plates=[turtle.Turtle() for i in range(n)]
34     for i in range(n):
35         plates[i].up()
36         plates[i].hideturtle()
37         plates[i].shape("square")
38         plates[i].shapesize(1,8-i)
39         plates[i].goto(-400,-90+20*i)
40         plates[i].showturtle()
41     return plates
42 
43 def pole_stack():
44     poles=[Stack() for i in range(3)]
45     return poles
46 
47 def moveDisk(plates,poles,fp,tp):
48     mov=poles[fp].peek()
49     plates[mov].goto((fp-1)*400,150)
50     plates[mov].goto((tp-1)*400,150)
51     l=poles[tp].size()
52     plates[mov].goto((tp-1)*400,-90+20*l)
53 
54 def moveTower(plates,poles,height,fromPole, toPole, withPole):
55     if height >= 1:
56         moveTower(plates,poles,height-1,fromPole,withPole,toPole)
57         moveDisk(plates,poles,fromPole,toPole)
58         poles[toPole].push(poles[fromPole].pop())
59         moveTower(plates,poles,height-1,withPole,toPole,fromPole)
60 
61 myscreen=turtle.Screen()
62 drawpole_3()
63 n=int(input("请输入汉诺塔的层数:"))
64 plates=plate(n)
65 poles=pole_stack()
66 for i in range(n):
67     poles[0].push(i)
68 moveTower(plates,poles,n,0,2,1)