Python第二十四课:递归求解汉诺塔

  • A+
所属分类:Python学习

汉诺塔说明:

汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

Python第二十四课:递归求解汉诺塔

汉诺塔解题思路:

问题一、将X上的63个盘子借助Z移到Y上

1、将前63个盘子从X移动到Y上

2、将最底下的第64个盘子从X移动到Z上

3、将Y上的63个盘子移动到Z上

 

问题二、将Y上的63个盘子借助X移动Z上

1、将前62个盘子从Y移动到X上

2、将最底下的第63个盘子移动到Z上

3、将X上的62个盘子移动到Y上

持续执行上面的内容,将X上的62个盘子借助Z移到Y上,将X上的61个盘子借助Z移到Y上。。。。

将Y上的62个盘子借助X移动Z上,将Y上的61个盘子借助X移动Z上

 

汉诺塔解题代码

  1. i = 0
  2. def hanoi(n,x,y,z):
  3.     global i
  4.     i +=1
  5.     if n==1:
  6.         print(x,'-->',z)
  7.     else:
  8.         hanoi(n-1,x,z,y)   #注意这里(x,z,y)
  9.         print(x,'-->',z)
  10.         hanoi(n-1,y,x,z)   #注意这里(y,x,z)
  11. num = int(input('您需要计算的汉罗塔的块数:'))
  12. n = hanoi(num,'x','y','z')
  13. print('您需要计算的汉罗塔最少的移动次数:',i)

如果你玩了这个游戏后,你会发现动作很简单。你会操作3块的时候,操作四块也很简单,只是会反复的做那些动作,然后搞蒙圈了。

  1. 您需要计算的汉罗塔的块数:3
  2. x --> z
  3. x --> y
  4. z --> y
  5. x --> z
  6. y --> x
  7. y --> z
  8. x --> z
  9. 您需要计算的汉罗塔最少的移动次数: 7

不妨去网上去找下汉诺塔的程序,按照上面的方式尝试一下,或者自己不看先尝试下。


单词扩展:

  • hanoi:汉诺塔

扩展阅读:


版权注释:

Python课程来源于鱼C论坛:http://bbs.fishc.com/forum-243-1.html 版块,课程内容为免费内容,如果你喜欢该课程,建议购买VIP账号支持小甲鱼,官方网店:https://fishc.taobao.com/)。

本内容为在李金龙在学习课程中做的日记记录,方便自己以后查找相关信息,另一方面也希望自己写下的东西可以帮助到别人。

课程内容:http://blog.fishc.com/3136.html

 

李金龙

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: