论坛 › Python交流 › 递归_汉诺塔，有点儿混乱。

SmilerLiu 发表于 2020-4-13 00:02:20

递归_汉诺塔，有点儿混乱。

# 将大小不同的盘子从X位置移动到Z位置，要求小盘子必须在大盘子上面
# 每次只能移动一个盘子
# 将n-1个盘子看做一个整体：:X-->Y, n:X-->Z, :Y-->Z
def hanoi(n,x,y,z):
    global count
    if n == 1:
      print('第%d步：从%s到%s'% (count,x,z))
      count += 1
    else:
      hanoi(n-1,x,z,y) # 将n-1个盘子由X移动到Y上
      print('第%d步：从%s到%s'%(count,x,z)) # 将最底下的盘子由X移动到Z上。
      count += 1
      hanoi(n-1,y,x,z)# 将Y上的n-1个盘子由Y移动到Z上
      
count = 1
n = int(input('输入盘子的个数：'))
hanoi(n,'X','Y','Z')

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
老师这个递归没搞明白，这里输出的第一个print语句是第7行的吗？

leon_xinxin 发表于 2020-4-13 00:42:44

你好，是第七行，但是不是初始层的，第一次打印应该是递归最后一层打印，也就是递归到n==1的时候，打印第一次，然后逐层返回，并打印

BngThea 发表于 2020-4-13 08:28:35

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

SmilerLiu 发表于 2020-4-13 21:42:41

# 将大小不同的盘子从X位置移动到Z位置，要求小盘子必须在大盘子上面
# 每次只能移动一个盘子
# 将n-1个盘子看做一个整体：:X-->Y, n:X-->Z, :Y-->Z
def hanoi(n,x,y,z):
    global count
    if n == 1:
      print('line7:\t第%d步：%d号从%s到%s'% (count,n,x,z))
      count += 1
    else:
      hanoi(n-1,x,z,y) # 将n-1个盘子由X移动到Y上
      print('line11:\t第%d步：%d号从%s到%s'%(count,n,x,z)) # 将最底下的盘子由X移动到Z上。
      count += 1
      hanoi(n-1,y,x,z)# 将Y上的n-1个盘子由Y移动到Z上
      
count = 1
n = int(input('输入盘子的个数：'))
print()
print('盘子从小到大：1号到%d号'%n)
print()
hanoi(n,'X','Y','Z')

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

hanio(2,x,y,z)--->    hanoi(1,x,z,y)
                  print('line11:x-z')
                        hanoi(1,y,x,z)
                  
            展开--->    print('line7:x-y')
                  print('line11:x-z')
                        print('line7:y-z')
               
hanio(3,x,y,z)--->    hanoi(2,x,z,y)
                  print('line11:x-z')
                        hanoi(2,y,x,z)
                  
            展开--->      hanoi(1,x,z,y)
                        print('line11:x-z')
                            hanoi(1,x,y,z)
                  print('line11:x-y')
                            hanoi(1,x,z,y)
                        print('line11:x-z')
                            hanoi(1,x,y,z)
                  
          再展开--->      print('line7:x-z')
                        print('line11:x-y')
                            print('line7:z-y')
                  print('line11:x-z')
                            print('line7:y-x')
                        print('line11:y-z')
                            print('line7:x-z')

'''
~~~~~~~~~~~~~~~~~~
做了一个展开，终于看清怎么回事了。

leon_xinxin 发表于 2020-4-14 00:50:20

SmilerLiu 发表于 2020-4-13 14:42
~~~~~~~~~~~~~~~~~~
做了一个展开，终于看清怎么回事了。

嗯嗯，对的！

查看完整版本: 递归_汉诺塔，有点儿混乱。