塔

Question

1 
2 def printMove (to, fr): 
3  '''Prints the moves to be executed''' 
4  print 'move from ' + str (fr) + ' to ' + str (to) 
5 
6 def towers (n, fr, to, sp): 
7  if n == 1:    
8  
9  printMove (to, fr) # 
10  
11  else: 
12   towers (n-1, fr, sp, to) 
13      
14     
15     
16   towers (1, fr, to, sp) 
17   towers (n - 1, sp, to, fr) 
18 
19 towers (3, 'fr', 'to', 'sp') 

请有人可以解释为什么这代码完成与n递减至1第12行的递归调用，然后再做另一个调用n = 2，然后转移后第16行？我一直在使用Python导师，并试图理解每一步以及算法的工作原理。

Answer 1

首先，你的代码并不完全正确。这里是改变的towers功能 - >

def towers (n, fr, to, sp): 
    if n == 1:    
     printMove (to, fr) 
    else: 
     towers (n-1, fr, sp, to) 
     printMove (to,fr) 
     towers (n-1, sp, to, fr) 

这里去解释。看图片 - >

通过调用Movetower(3,a,b,c)，你打算将所有从塔A 3盘至塔B。因此，连续通话是 - >

1. Movetower(3,a,b,c) // No Move needed 
2. Movetower(2,a,c,b) // No move needed 
3. Movetower(1,a,b,c) // Here is the time to move, move disc1 from a to b 
4. Movetower(2,a,c,b) // Returning to this call again, this is the time to move disc2 from a to c 
5. Movetower(1,b,c,a) // Again the time to move, this time disc1 from b to c 
6. Movetower(3,a,b,c) // Returning to this call again, this is the time to move disc3 from a to b 
7. Movetower(2,c,b,a) // Not the time to move 
8. Movetower(1,c,a,b) // Here is the time to move, move disc1 from c to a 
9. Movetower(2,c,b,a) // Returning to this call again, this is the time to move disc2 from c to b 
10.Movetower(1,c,a,b) // Here is the time to move, move disc1 from a to b 

希望它能帮助:)

您还可以找到一些很好的解释在这里：Tower of Hanoi: Recursive Algorithm

动画：https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html

Answer 2

首先，旁白：您显示的代码在第9行中包含错误，该错误没有合法缩进。

执行从第19行开始，第19行呼叫塔（3，...），它继续前进到第12行，在那里它呼叫塔（2，...），它继续前进到第12行，塔（1，...），打印一些东西并返回。当它返回时，执行在塔（2，...）调用中继续，并在第16行恢复，如你所观察到的。