汉诺塔问题——python递归算法实现
依次类推到n个金盘的情况,每次需先完成n-1的情况。显然,子问题与原始问题为同样的事,更为简单,且操作次数均为有限次,故考虑递归算法。
·
1.问题描述:
相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
2.问题分析:
想要解决该问题,即是要将64个金盘全部移动到C杆,则
要想把第64个金盘移到C杆,先要借助B杆,将63个金盘移动到B杆
要想把63个金盘移动到B杆,先要借助C杆,将62个金盘移动到C杆
…………
于是,
要想把3个金盘移动到C杆,先要借助B杆,将2个金盘移动到B杆
要想把2个金盘移动到B杆,先要借助C杆,将1个金盘移动到C杆
3.算法设计:
case1:一个金盘
def hanoi(A, B, C):
print("将%c座中%d盘子---->%c座" % (A, 1, C)) # 将金盘1移动到C杆
case2:两个金盘
hanoi('A', 'C', 'B') # 借助B杆将金盘2移动到C杆
print("将%c座中%d盘子---->%c座" % (A, 2, C)) # 将金盘2移动到C杆
hanoi('B', 'A', 'C') # 移回金盘1
case3:三个金盘
def hanoi(n, A, B, C):
if n == 1:
print("将%c座中%d盘子---->%c座" % (A, n, C))
else:
hanoi(n - 1, A, C, B) # 借助C杆将金盘1、2移动到B杆
print("将%c座中%d盘子---->%c座" % (A, n, C)) # 将金盘3移动到C杆
hanoi(n - 1, B, A, C) # 借助A杆将金盘1、2移动到C杆
hanoi(3, 'A', 'B', 'C')
依次类推到n个金盘的情况,每次需先完成n-1的情况。
显然,子问题与原始问题为同样的事,更为简单,且操作次数均为有限次,故考虑递归算法。
4.完整程序:
def hanoi(n, A, B, C):
if n == 1:
print("将%c座中%d盘子---->%c座" % (A, n, C))
else:
hanoi(n - 1, A, C, B) #借助C杆将金盘1到n-1移动到B杆
print("将%c座中%d盘子---->%c座" % (A, n, C)) #将金盘n移动到C杆
hanoi(n - 1, B, A, C) #借助A杆将金盘1到n-1移动到C杆
n = eval(input())
hanoi(n, 'A', 'B', 'C')
5.运行结果:
n=64时,移动次数为18 446 744 073 709 551 615次,故在此展示n=3的运行结果。
更多推荐
已为社区贡献1条内容
所有评论(0)