[已解决]汉诺塔递归问题分解

小时候可帅了

我是想自己分解一下汉诺塔递归程序，后来发现水平有限，分解不下去了，希望大神帮忙拆解一下，最好后面有个注释，感激不尽。还有其中（a,b,c）虽然知道是形参实参的问题，但是还是在分解期间绕绕绕绕不清楚，希望大神能帮忙注释一下。                   这个问题已经困扰了三四天了，天天都在想，太痛苦了。

汉诺塔程序推演：
现在假设n = 3 对该递归程序进行拆解

def hanoi(n,a,b,c):      
    if n ==1 :
        print ( a, '->' , c)
    else:
        hanoi(n-1,a,c,b)   

Hanoi(3-1,a,c,b)
If n == 1:
                Print ( a ,’->’,b )
Else:
                Hanoi(3-1-1,a,b,c)
                                If n == 1:
                                                Print ( a ,’->’,c )①

                Print (a,’->’,b)②

                Hanoi(3-1,a,c,b)  
                If n == 1:
                                Print( b,’->’,a )
                Else :
                                Hanoi( 3-1-1,c,a,b )
                                If n == 1:
                                                Print( c,’->’,b )③  

                                Print(a,’->’,c)④

                                Hanoi(3-1-1,c,a,b)
                                                If n == 1:
                                                                Print(c,’->’,b)


print( a, '->' , c)   
        hanoi(n-1,b,a,c)      

最佳答案

月排行榜 / 总排行榜

XiaoPaiShen

2020-2-25 03:23:38

跳转到最佳答案楼层

ouyunfu

1. # -*- coding: utf-8 -*-
   
2. def hanoi(n,a,b,c):  #n为盘子数，a,c,c为三根柱子   
   
3.     if n == 1 :
   
4.         print ( a, '->' , c)
   
5.     else:
   
6.         hanoi(n-1,a,c,b) #将前n-1个盘子从a移到b上
   
7.         print(a,'->',c)#将最底下的最后一个盘子从a移到c上
   
8.         hanoi(n-1,b,a,c)#将b上的n-1个盘子移动到c上
   
9.         
   
10. n=4
    
11. print(hanoi(n,'a','b','c'))

复制代码

小时候可帅了

这个论坛里有这个答案了，我的也是这个，我想问的n=3时拆解else里面的语句。

拉了盏灯

嗯，代码注释了你也不一定看的懂，当时我也想了很久，不过想通了以后，递归用起来那叫一个得心应手。下面说说我的拙见，
这个递归函数，本质上就是把所有的盘子从a移动到.c,中间过程很多，但是不用去管，你要把所有盘子移动到c，就先得把最底下的盘子上面的所有盘子，也就是n-1个盘子移动到b中间位置缓冲，这就是hanoi(n-1,a,c,b)  ,然后再把最底下的盘子从a运到c,
这就是print(a,'->',c)，这时候，已经完成了一层递归了，这时候的a柱什么都没有是中间柱，盘子在b柱，c柱是目标柱，所以又调用hanoi(n-1,b,a,c)，周而复始，当还剩最后一块的时候，肯定是要有一个出口结束递归，这时候直接a到c。结束，

XiaoPaiShen

小时候可帅了

XiaoPaiShen 发表于 2020-2-25 03:23

一下子看懂了，感谢

XiaoPaiShen

能帮到你很高兴