将其问题分解寻找规律

1. 将b柱子作为辅助，把a上的63个圆盘移动到b上
2. 将a上最后一个圆盘移动到c
3. 将a作为辅助，把b上的62个圆盘移动到a上
4. 将b上的最后一个圆盘移动到c
5. 即每次都是先将其他圆盘移动到辅助柱子上，并将最底下的圆盘移到c柱子上，然后再把原先的柱子作为辅助柱子，并重复此过程。

   著名的斐波那契数列定义如下，可以看出，f(n)是由规模更小一些的f(n-1)和f(n-2)推导出来的：

   f(0)=0，f(1)=1
   f(n)=f(n-1)+f(n-2) (n>=2)

   因此，递归实际上就是用自己来定义自己。

   这个过程称为递归，即定义一组基本操作，这组操作将规模小一点（或大一点）的操作当做一个整体——无需关心它的细节，只当它已经完成了——然后执行剩下的操作。而在更小或更大的规模中也依此操作，直到规模达到预定值。

   2.根据规律创建函数

   我们假设函数func(n, a, b, c)用于将n个圆盘由a移动到c，b作为辅助柱子。那么我们可以这样实现这个递归过程：

   1. func:  
   2. if n!=0 then            ;预定值  
   3.   func(n-1, a, c, b)    ;将n-1个盘子由a移动到b，以c为辅助柱子（注意参数顺序）  
   4.   move a[n] to c        ;将a上的最后一个盘子移动到c  
   5.   func(n-1, b, a, c)    ;将n-1个盘子由b移动到c，以a为辅助柱子  
   6. endif                   ;完成  

   3.结合turtle构建函数

   1. import turtle  
   2.     
   3. class Stack:  
   4.     
   5.     def __init__(self):  
   6.     
   7.         self.items = []  
   8.     
   9.     def isEmpty(self):  
   10.     
   11.         return len(self.items) == 0  
   12.     
   13.     def push(self, item):  
   14.     
   15.         self.items.append(item)  
   16.     
   17.     def pop(self):  
   18.     
   19.         return self.items.pop()  
   20.     
   21.     def peek(self):  
   22.     
   23.         if not self.isEmpty():  
   24.     
   25.             return self.items[len(self.items) - 1]  
   26.     
   27.     def size(self):  
   28.     
   29.         return len(self.items)  
   30.     
   31.      
   32.     
   33. def drawpole_3():  
   34.     
   35.     t = turtle.Turtle()  
   36.     
   37.     t.hideturtle()  
   38.     
   39.     def drawpole_1(k):  
   40.     
   41.         t.up()  
   42.     
   43.         t.pensize(10)  
   44.     
   45.         t.speed(100)  
   46.     
   47.         t.goto(400*(k-1), 400)  
   48.     
   49.         t.down()  
   50.     
   51.         t.goto(400*(k-1), -100)  
   52.     
   53.         t.goto(400*(k-1)-20, -100)  
   54.     
   55.         t.goto(400*(k-1)+20, -100)  
   56.     
   57.     drawpole_1(0)  
   58.     
   59.     drawpole_1(1)  
   60.     
   61.     drawpole_1(2)  
   62.     
   63.      
   64.     
   65. def creat_plates(n):  
   66.     
   67.     plates=[turtle.Turtle() for i in range(n)]  
   68.     
   69.     for i in range(n):  
   70.     
   71.         plates[i].up()  
   72.     
   73.         plates[i].hideturtle()  
   74.     
   75.         plates[i].shape("square")  
   76.     
   77.         plates[i].shapesize(1,20-i)  
   78.     
   79.         plates[i].goto(-400,-90+20*i)  
   80.     
   81.         plates[i].showturtle()  
   82.     
   83.     return plates  
   84.     
   85.      
   86.     
   87. def pole_stack():  
   88.     
   89.     poles=[Stack() for i in range(3)]  
   90.     
   91.     return poles  
   92.     
   93.      
   94.     
   95. def moveDisk(plates,poles,fp,tp):  
   96.     
   97.     mov=poles[fp].peek()  
   98.     
   99.     plates[mov].goto((fp-1)*400,550)  
   100.     
   101.     plates[mov].goto((tp-1)*400,550)  
   102.     
   103.     l=poles[tp].size()  
   104.     
   105.     plates[mov].goto((tp-1)*400,-90+20*l)  
   106.     
   107.      
   108.     
   109. def moveTower(plates,poles,height,fromPole, toPole, withPole):  
   110.     
   111.     if height >= 1:  
   112.     
   113.         moveTower(plates,poles,height-1,fromPole,withPole,toPole)  
   114.     
   115.         moveDisk(plates,poles,fromPole,toPole)  
   116.     
   117.         poles[toPole].push(poles[fromPole].pop())  
   118.     
   119.         moveTower(plates,poles,height-1,withPole,toPole,fromPole)  
   120.     
   121.      
   122.     
   123. myscreen=turtle.Screen()  
   124.     
   125. drawpole_3()  
   126.     
   127. n=int(input("请输入汉诺塔的层数并回车: "))  
   128.     
   129. plates=creat_plates(n)  
   130.     
   131. poles=pole_stack()  
   132.     
   133. for i in range(n):  
   134.     
   135.     poles[0].push(i)  
   136.     
   137. moveTower(plates,poles,n,0,2,1)  
   138.     
   139. myscreen.exitonclick()  

   4.将该代码输入python并运行

   运行过程如下图