[已解决]汉诺塔求解程序的疑问

脚底的老泥

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)
        hanoi(n-1,y,x,z) # 将y上的n-1个盘子移动到z上

n = int(input('请输入汉诺塔的层数：'))
hanoi(n,'x','y','z')





hanoi(n-1,x,z,y) # 将前n-1个盘子从x移动到y上
hanoi(n-1,y,x,z) # 将y上的n-1个盘子移动到z上

这两行是为什么？求解释

最佳答案

月排行榜 / 总排行榜

BngThea

2019-1-24 14:42:48

参考：
https://fishc.com.cn/thread-116890-1-1.html

跳转到最佳答案楼层

BngThea

参考：
https://fishc.com.cn/thread-116890-1-1.html

sunrise085

汉诺塔问题的求解是递归问题。将x上的n个盘子通过y移动到z上，递归的过程如下：第一步，将x上的n-1个通过z，移动到y上；第二部，将x上剩下的那一个移动到z上；第三步，将y上的n-1个通过x移动到z上。

你所说的那两行实际上就是递归的第一步和第三步。具体这n-1个盘子是怎么移动的，那就是下一次递归的问题了，一直递归到n==1，就可以直接移动了。

你可以先从n比较小的时候开始试试，程序的运行过程，例如，n=2时如何运行，n=3时如何运行。然后你就能够看出这个递归了

gzxyzxc

如果要在里面加上步骤，怎么实现呢？比如：第1步，……
不知像这样做对吗？

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

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