[已解决]关于汉诺塔的问题

coffee_cat

def hanoi(n, x, y, z):
    if n == 1:
        print(x, ' --> ', z)
    else:
        hanoi(n-1, x, z, y) # 将前n-1个盘子从x移动到y上
        print(x, ' --> ', z) # 将最底下的最后一个盘子从x移动到z上
        hanoi(n-1, y, x, z) # 将y上的n-1个盘子移动到z上

n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'X', 'Y', 'Z')


==================
注解的那行看不懂，为什么（n-1, x, z, y）就能表示将前n-1个盘子从x移动到y上，为什么(n-1, y, x, z) 就能表示 将y上的n-1个盘子移动到z上的意思。
我学的是Python3，用的是win7

最佳答案

月排行榜 / 总排行榜

Kotori

2016-9-15 10:15:05

保持简单丶 发表于 2016-9-15 04:11
kotori大神的解释我不是很明白，能解释的更通俗一点吗？
n-1代表什么。参数到什么什么之间这个我明白。

n-1就是递归的下一个情况。
要移动n个盘，先移动‘n-1’个，实现最下面的移动后，就剩下n-1个了。
这时要移动n-1（n-1假定为a)个盘，和上面一样，先移动'a-1'个。
就是这样递归的....，可能是我说的不清楚。
就是一层一层往下找....

跳转到最佳答案楼层

Kotori

这么说吧，hanoi(n,x,y,z)表示的是把n个盘从x移动到z，中间以y为中介。（x-->y-->z)
而hanoi(n,x,y,z)这个事件分为先把n-1个盘从x移动到y，可以理解为这时的中介是z，中介是处于来源和目的中间的，与定函数参数的时候相同，所以z在中间，由x到y，即hanoi(n-1,x,z,y)的调用。(x-->z-->y)
再接来一句是x到z，
最后将y上面的n-1个盘从y移动到z上，中介是x。(y-->x-->z)
这个函数可以理解为hanoi(盘子的数目，来源，中介，目的）的形式，我想你去多玩几次那个游戏对理解会有帮助。

coffee_cat

Kotori 发表于 2016-9-14 21:20
这么说吧，hanoi(n,x,y,z)表示的是把n个盘从x移动到z，中间以y为中介。（x-->y-->z)
而hanoi(n,x,y,z)这个 ...

这么说吧，x,y,z我知道是x经由y挪到z，我的问题是计算机怎么知道x,y,z是这个意思，而不是元祖或是其它

Kotori

这个是函数，x,y,z是参数，计算机是不知道x,y,z是什么的，但是这个递归过程你自己知道，在n==1的情况定义了递归到最后，初始情况就是从参数x到参数z的，y是中介。

保持简单丶

kotori大神的解释我不是很明白，能解释的更通俗一点吗？
n-1代表什么。参数到什么什么之间这个我明白。

Kotori

保持简单丶 发表于 2016-9-15 04:11
kotori大神的解释我不是很明白，能解释的更通俗一点吗？
n-1代表什么。参数到什么什么之间这个我明白。

n-1就是递归的下一个情况。
要移动n个盘，先移动‘n-1’个，实现最下面的移动后，就剩下n-1个了。
这时要移动n-1（n-1假定为a)个盘，和上面一样，先移动'a-1'个。
就是这样递归的....，可能是我说的不清楚。
就是一层一层往下找....

树精树蛙

其实就是表示一个路径问题，按照次序第一个从x移动到z。这个逻辑是倒着的，最终肯定是最后一个从x挪到z，其余的在y上，那么再依次把y上的移动到z
试了一下64,层，跑疯了

houxilan

懵懵懂懂，让自己写个类似的肯定写不出来

coffee_cat

Kotori 发表于 2016-9-14 21:20
这么说吧，hanoi(n,x,y,z)表示的是把n个盘从x移动到z，中间以y为中介。（x-->y-->z)
而hanoi(n,x,y,z)这个 ...

真的不好意思，我还是听不懂，你能推导一下，当n==3的时候，程序的运行情况吗

Kotori

coffee_cat 发表于 2016-9-16 15:07
真的不好意思，我还是听不懂，你能推导一下，当n==3的时候，程序的运行情况吗

hanoi(3,x,y,z):
        hanoi(2,x,z,y)
                hanoi(1,x,y,z)
                        print(x,'-->',z)
                print(x,'-->',y)
                hanoi(1,z,x,y)
                        print(z,'-->',y)
        print(x,'-->',z)
        hanoi(2,y,x,z)
                hanoi(1,y,z,x)
                        print(y,'-->',x)
                print(y,'-->',z)
                hanoi(1,x,y,z)
                        print(x,'-->',z)

由上往下执行，结果如下：
                       
1.x-->z
2.x-->y
3.z-->y
4.x-->z
5.y-->x
6.y-->z
7.x-->z

coffee_cat

Kotori 发表于 2016-9-17 06:48
hanoi(3,x,y,z):
        hanoi(2,x,z,y)
                hanoi(1,x,y,z)

谢谢你的耐心讲解

luck78

Kotori 发表于 2016-9-17 06:48
hanoi(3,x,y,z):
        hanoi(2,x,z,y)
                hanoi(1,x,y,z)

请问，
1，：hanoi(n-1, x, z, y) 和hanoi(n-1, y, x, z )里并没有写 print(z '-->' y) 和print(y '-->' z)，程序是怎么知道要这样打印的？
2，else里第2行的 print(x '-->' z)， x和z是变量吗？ 所以 可以打印出  print(z '-->' y)和print(y '-->' z)?
3, hanoi(n, ‘X’, 'Y', 'Z') 这个为什么是大写的XYZ? 是参数吗？
谢谢！

Kotori

luck78 发表于 2017-3-23 23:17
请问，
1，：hanoi(n-1, x, z, y) 和hanoi(n-1, y, x, z )里并没有写 print(z '-->' y) 和print(y '-->' ...

1.可以简单的理解为递归调用中形参的顺序发生变化导致出现Z-->Y等结果，并不需要print(z'-->'y)的语句，可参照我上面写的3的递归来理解。
2.是形参，当然也是变量。
3.大写XYZ是实参，与1相同，当它们以不同的顺序调用时，与小写xyz形参对应位置发生改变才出现Z-->Y这们的结果。

clew

好题目

luck78

Kotori 发表于 2017-3-24 13:25
1.可以简单的理解为递归调用中形参的顺序发生变化导致出现Z-->Y等结果，并不需要print(z'-->'y)的语句， ...

谢谢谢谢