第050讲：函数（X）- 汉诺塔

kkk1029

《零基础入门学习Python》

（最新版）

小甲鱼 著

立即购买

def hanoi(n,x,x,z):
    if n==1:                                       
        print(x,'-->',z)                                PP1
    else:
        hanoi(n-1,x,z,y)                                SS1
        print(x,'-->',z)                                PP2
        hanoi(n-1,y,x,z)                                SS2

原理：
简化成2个球（看颜色发现是对称的)
n-1  个球 从 A-->B
第n  个球从  A-->C
n-1  个球 从 B-->C

简化成3个球（看颜色发现是对称的)
小球      A-->C          step1
中球      A-->B          step2
小球      C-->B          step3
第n个球 A-->C                                           step4
小球      B-->A           step5
中球      B-->C           step6
小球      A-->C           step7

程序运转：
hanoi(3,x,y,z)
n        3
x        "A"
y        "B"
z        "C"

n不等于1，那么走入else  [SS1], 这是中球（注意里面hanoi(2,x,z,y)里面是2）
hanoi(2,x,z,y)
n        2 (中球)
x        "A"
y        "C"
z        "B"

重新回到主程序去判断n是否等于1，不满足后又走回 [SS1]，这是小球（注意里面hanoi(1,x,z,y)里面是1）
hanoi(1,x,z,y)
n        1（小球）
x        "A"
y        "B"
z        "C"

程序指针走回去重新判断n==1?,符合条件，走到[PP1], 这时打印的就是A-->C (因为程序的航一行是上面的hanoi(1,x,z,y))，也就是步骤step1
这时上面的hanoi(1,x,z,y)返回值是None, "归"到hanoi(2,x,z,y),也就是说程序的上一行现在指向是SS1（当n是2时），所以下一行语句就是PP2
PP2打印的结果就是A-->B(因为已经“归”到hanoi(2,x,z,y)，看它的排列就知道是A-->B), 也就是step2
下面指针就走到SS2, n又减去1后就变成1
hanoi(1,y,x,z)
n        1（小球）
x        “C”
y        “A”
z        “B”
这个C，A，B的排列顺序是根据SS1当n=2时确定的

这时由于n又是1，所以执行PP1打印C-->B step3, return None, 这时因为“归”，所以指针指的上一步是SS1（hanoi(2,x,z,y)），这时代码就没有再下一行了，这时SS2也就只能return None, 回到了最开始
hanoi(3,x,y,z)的状态，其实以最大的球作为分界线，那么已经执行完上半部分（原理中以第n个球A-->C为界限，上半部分就完成了，也就是将n-1个球从A-->B），这时程序上一步的指针回到了SS1（n-1个球已经从A-->B，已经完成，所以指针的上一步就回到了SS1），所以下一步就是PP2，完成第n个球从A-->C的转移,step4。下面就是要将n-1个球从B-->C上

这时
hanoi(2,y,x,z)
n        2 （中球）
x        "B"
y        "A"
z        "C"

判断n不等于1，所以指针有指到了SS1
hanoi(1,x,z,y)
n        1
x        "B"
y        "C"
z        "A"
符合n==1，所以指针指到PP1，打印B-->A  step5, return None, 程序还有下一行，所以指针指向PP2
打印B-->C, step6, 之所以打印B-->C是因为上一步return None后，就“归”到了SS1, 然后程序走到了SS2
hanoi(1,y,x,z)
n        1 (小球）
x        "A"
y        "B"
x        "C"
符合n==1,执行PP1，打印A-->C step7，return None, “归”到hanoi(2,y,x,z), return None,继续“归”，hanoi(3,x,y,z), return None程序执行完毕