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的运行结果。

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐