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

小古比鱼

本节介绍了古老的汉诺塔问题，其解法的核心是利用递归思想，将问题分解为三个较为简单的步骤，逐层降级，再分别予以实现，十分巧妙！最有趣的是小甲鱼老师的现场演示环节，操作连贯自然，讲解清晰流畅，语言幽默风趣，帮助大家直观地认识并理解了这个好玩的游戏！

fishcyou

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

复制代码

炎凉来寻

打卡

chenjinchao

卡打

rianbow

小甲鱼能讲一下代码是如何写出来的吗，那些实参转来转去搞不懂？

墨墨在努力吖

滴滴滴~打卡

17671799918

rianbow 发表于 2022-10-10 19:59
小甲鱼能讲一下代码是如何写出来的吗，那些实参转来转去搞不懂？

小甲鱼能讲一下代码是如何写出来的吗，那些实参转来转去搞不懂？

17671799918

小甲鱼能讲一下代码是如何写出来的吗，那些实参转来转去搞不懂？

lymbwx

学习到了

kkk1029

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程序执行完毕

migu_sm1

Learning...这节课有点绕

zhangwa50

# 汉诺塔游戏

"""
    n为初始时A柱子上的盘子数
    a为起始盘子所在的柱子
    b为中转柱子
    c为目的地柱子
"""

def hanoi(n, a, b, c):

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



hanoi(3, "A", "B", "C" )
# 把hanoi(3, "A", "B", "C" )  里这几个参数正确理解了就不难了，A代表盘子一开始所在的柱子，C代表要把盘子移动到哪个柱子上，B是中转柱子

andyleesh

打卡，这个比较有意思，看小朋友玩过，原来是这样的

呱呱呱i

嘀嘀嘀

hcm666

上面那个汉诺塔的代码跑起来就 停不下来了

2450880030

感觉现在做递归题都是凭感觉做，用中文的理解去写，要深度思考一次又一次的调用反而容易混淆