第34期-汉诺塔游戏

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

塔内有三个座A、B、C，A座上有n个盘子，盘子从上到下逐渐变大，最下面的盘子最大。目前要把A座的n个盘子从A座移到C座，并且每次只能移动一个盘子，移动过程中三个座保持大盘子在下，小盘子在上，要求输出盘子的移动过程。

有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。
如果移动一个圆盘需要1秒钟的话，等到64个圆盘全部重新落在一起，宇宙被毁灭是什么时候呢？
让我们来考虑一下64个圆盘重新摞好需要移动多少次吧。1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次......这实在是太累了。
因此让我们逻辑性的思考一下吧。
3个的时候能够移动最大的3盘时。
到此为止用了7次。
接下来，在上面再放上3个圆盘时还要用7次（把3个圆盘重新放在一起需要的次数）。
因此，4个的时候是
“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”
=2x“3个圆盘重新摞在一起的次数”+1次
=15次。
那么，n个的时候是
2x“（n-1）个圆盘重新摞在一起的次数”+1次。
由于1 个的时候是1次，结果n个的时候为（2的n次方减1）次。
1个圆盘的时候 2的1次方减1
2个圆盘的时候 2的2次方减1
3个圆盘的时候 2的3次方减1
4个圆盘的时候 2的4次方减1
5个圆盘的时候 2的5次方减1
........
n个圆盘的时候 2的n次方减1
也就是说，n=64的时候是（2的64次方减1）次。
因此，如果移动一个圆盘需要1秒的话，宇宙的寿命=2的64次方减1（秒）
2的64次方减1到底有多大呢？动动计算器，答案是一个二十位的数字约是1.84467440*10^19
用一年=60秒x60分x24小时x365天来算的话，大约有5800亿年吧。
太阳及其行星形成于50亿年前，其寿命约为100亿年。
汉诺塔问题在数学界有很高的研究价值，而且至今还在被一些数学家们所研究。
也是我们所喜欢玩的一种益智游戏，它可以帮助开发智力，激发我们的思维。

2 解题思路

• 用input函数请用户输入初始盘子的层数
• 将n盘从a移到c，可以想成先将上面n-1层从a移到b，再将最下面一层移到c，再将上面n-1层从b移到c，递归

3 解题方法

num = int(input('请输入A盘上的圆盘个数：'))
n = 0


def process(A, B, C, num):
    global n
    if num == 1:
        print(A, '到', C)
        n += 1
    else:
        num = num - 1
        process(A, C, B, num)
        print(A, '到', C)
        n += 1
        process(B, A, C, num)


process('A', 'B', 'C', num)
print(f'最少{n}步完成')

第1-2行： 定义变量num与n，用input函数使用户输入圆盘个数，并赋值给num，给n赋值为0记录移动次数
第5行： 创建函数process，内部元素A,B,C,num,函数意义是将num层从A移到C
第6行： global引入全局变量n
第7-9行： 当num只有一层时，直接将A移到C
第10-15行： num多余一层时，先num-1代表移动上面的num-1层，process(A,C,B,num)代表将上面num从A移到B，将最底下一层从A移到C并记录步数加一，再将之前num-1层从B移到C，迭代过程
第18-19行： 给process函数内变量赋值，并打印步数

这里用到的迭代过程较为复杂，需要多多思考

代码运行结果为：

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码