Python3实现汉诺塔问题

2023-01-31 01:01:37 python3 汉诺

python3实现汉诺塔问题

  • 一、思路
  • 二、python3代码实现
  • 三、总结
  • 四、参考资料

总结归纳为以下3步:

  1. 把x上的n-1个盘子借助z,移动到y上
  2. 把x上最下面的盘子移动到z上
  3. 最后把y上的n-1个盘子借助x移动到,z上,大功告成
    递归出口:n=1时,直接从x移动到z上
# Python3递归实现汉诺塔游戏
def hannota(n,x,y,z): # n是盘子数,x,y,z为形参作为柱子
    if n == 1: # 递归出口
        print(x,'-->',z)
        return # 返回None
    else:
        hannota(n-1,x,z,y) # 把x上的n-1个盘子借助z,移动到y上
        hannota(1,x,y,z) # 把x上最下面的盘子移动到z上
        hannota(n-1,y,x,z) # 最后把y上的n-1个盘子借助x移动到,z上,大功告成
hannota(3,'X','Y','Z') # 传递实参进去

放一张我自己画的图,里面记录了函数执行的每一步的过程。重点在注意形参和实参的传递问题。
在这里插入图片描述
输出结果:
在这里插入图片描述

  1. 递归函数关键在于归纳总结出规律,确认它是可以递归的,并且找到合适的简单的递归出口。
  2. 在汉诺塔里面,对于实参和形参的理解很重要,要注意其区别。整个函数的打印过程,可以自己动手一步一步的去画一下,每一步怎么传参,打印的是什么,来帮助理解。
  3. 汉诺塔游戏是递归调用,在函数调用过程中,栈的问题需要注意,递归函数一层一层的深入调用,但是每调用一层,函数不是马上返回的,而是放在栈中,相应的局部变量也是存在在里面,只有当调用到n=1时,函数才一个一个返回,n=1时返回了,n=2才可以正确返回,直到n=n时,该函数调用才结束。中间有一个递归函数的返回出问题,都会导致最后的结果出错。
  4. 汉诺塔游戏的移动次数问题其实是一个很经典的等比数列问题。
    假设需要移动的总次数为f(n),根据之前的分析思路,则有f(n) = f(n-1)+1+f(n-1) 即:f(n)=2f(n)=1。变化一下则:[f(n) + 1 ]= 2 * [f(n-1) + 1],一个非常经典的以2为等比的等比数列,又因为f(1)=1,所以求得f(n) = 2^n -1。
    所以如果有3个盘子,移动的步数就是2^3 - 1 = 7次,你可以去数一下,看看是不是?
    再回过头来看hannota(3,‘X’,‘Y’,‘Z’)
    hannota(2,‘X’,‘Z’,‘Y’) # 执行这句时会移动2^2 -1 = 3次盘子
    hannota(1,‘X’,‘Y’,‘Z’) # 执行这句时会移动 1次盘子
    hannota(2,‘Y’,‘X’,‘Z’ ) # 执行这句时会移动2^2 -1 = 3次盘子
    所以hannota(3,‘X’,‘Y’,‘Z’)总共移动了3+1+3=7次盘子。
  1. 通过汉诺塔问题理解递归的精髓
  2. 递归经典案例汉诺塔 python实现
  3. 形参和实参的区别
  4. 汉诺塔 程序实现—Python 及其具体运行步骤

相关文章