python 复杂递归问题 汉诺塔

汉诺塔问题是法国数学家Edouard Lucas于1883年，根据传说提出来的。

传说在一个印度教寺庙里，有3根柱子，其中一根套着64个有小到大的黄金盘片，僧侣们的任务就是把这一叠黄建盘从一根柱子搬到另一根，但有两个规则：

• 一次只能搬一个板子

• 大盘子不能叠在小盘子上

神的旨意说一旦这些盘子完成迁移，寺庙将会坍塌，世界将会毁灭。

递归逻辑

?将盘片塔从开始柱，经由中间柱，移动到目标柱

• 将上层N-1个盘片的盘片塔，从开始柱，经由目标柱，移动到中间柱；

• 将第N个（最大的）盘片，从开始柱，移动到目标柱；

• 最后将放置在中间柱的N-1个盘片的盘片塔，经由开始柱，移动到目标柱。

基本结束条件，也就是最小规模问题：

• 一个盘片的移动
  

代码：

def?move_tower(height,from_pole,with_pole,to_pole):
????if?height>=1:
????????move_tower(height-1,to_pole,with_pole)
????????move_disk(height,to_pole)
????????move_tower(height-1,to_pole)


def?move_disk(disk,to_pole):
????print(f'moving?disk?{disk}?from?{from_pole}?to?{to_pole}')


move_tower(3,'#1','#2','#3')

输出结果

moving?disk?1?from?#1?to?#3
moving?disk?2?from?#1?to?#2
moving?disk?1?from?#3?to?#2
moving?disk?3?from?#1?to?#3
moving?disk?1?from?#2?to?#1
moving?disk?2?from?#2?to?#3
moving?disk?1?from?#1?to?#3

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!