菜鸟笔记之——汉诺塔原理分析

myckjx

我用以前学VB时候的笨办法，把老师的代码做上标记，把xyz变量的值换成123，这样容易通过结果来分析过程

1. def  hanoi(n, x, y, z):  #初始hanoi()
   
2.     if n == 1:
   
3.         print('A|',x, ' --> ', z,'|n=%d' % n)
   
4.     else:
   
5.         hanoi(n-1, x, z, y)  # 第一个hanoi()
   
6.         print('B|',x, ' --> ', z,'|n=%d' % n)
   
7.         hanoi(n-1, y, x, z) # 第二个hanoi()
   
8.         print('C')
   
9. 
   
10. n = int(input('请输入汉诺塔的层数：'))
    
11. hanoi(n, 1, 2, 3)
    

复制代码

执行结果：

1. 请输入汉诺塔的层数：3
   
2. A| 1  -->  3 |n=1
   
3. B| 1  -->  2 |n=2
   
4. A| 3  -->  2 |n=1
   
5. C
   
6. B| 1  -->  3 |n=3
   
7. A| 2  -->  1 |n=1
   
8. B| 2  -->  3 |n=2
   
9. A| 1  -->  3 |n=1
   
10. C
    
11. C

复制代码

下面是我的分析结果，不对之处还望纠正
A| 1  -->  3 |n=1        第一个hanoi()开始递归过程：（n=1,1,2,3）->(n=2,1,3,2)->(n=3,1,2,3)，当n=1时执行了一次A
B| 1  -->  2 |n=2        当第一个hanoi()递归到：（n=1,1,2,3）->(n=2,1,3,2)时，顺序执行一次B
A| 3  -->  2 |n=1        并顺序调用第二个hanoi()，因为此时n=2,所以第二个hanoi()开始递归（n=1,3,1,2），此时n=1，所以执行了一次A
C                                第一个hanoi()递归过程结束前顺序执行了一次C
B| 1  -->  3 |n=3        第一个hanoi()递归过程结束，返回(n=3,1,2,3),顺序执行了一次B，接下来该第二个hanoi()上场了。
A| 2  -->  1 |n=1        第二个hanoi()用(n=2,2,1,3)调用初始hanoi()，但是，因为第一个hanoi()在前面，所以又调用了第一个hanoi(),
                                此时n=2,所以第一个hanoi()参数为(n=1,2,3,1),并直接递归执行了一次A
B| 2  -->  3 |n=2        第一个hanoi()递归完后恢复正常(n=2,2,1,3)，然后又顺序执行了一次B
A| 1  -->  3 |n=1        第二个hanoi()接着用(n=1,1,2,3)调用初始hanoi()，因为n=1所以执行了一次A
C                                第二个hanoi()递归过程结束前顺序执行了一次C
C                                所有递归结束后又顺序执行了一次C