讲座5：递归算法案例分析之汉诺塔游戏-技术圈

说在前面

在上一节“递归算法之寻找轻球问题”中，我们研究了如何分析实际问题、构造数学模型、推导递归公式的方法。并不是所有的递归函数都能构造简明的递归公式，今天我们将通过“汉诺塔游戏”案例，进一步分析递归函数的设计方法，理解递归算法简单明晰的特征。

新课引入

经典案例

课后练习

黑白棋子的移动。有2*n个棋子（n>=4）排成一行，开始位置为白子全部在左边，黑子全部在右边，如下图为n=5的情形：

○○○○○●●●●●

移动棋子的规则是：每次必须同时移动相邻的两个棋子，颜色不限，可以左移也可以右移到空位上去，但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能移成黑白相间的一行棋子。如n=5时，成为：

○●○●○●○●○●

你的任务是根据输入的棋子数量，编程打印出黑白棋子的移动过程。

程序运行界面如下图所示：

（1）先思考当n=4时的情形，下图给出了黑白棋子的初始位置和前2步移动过程，请写出剩下的移动过程。

0 ○○○○●●●●—— （"—"表示空位）

1 ○○○——●●●○●

2 ○○○●○●●——●

（2）当n=5时，需要移动几次，就能将问题转换成求解n=4时的情形？

需要本文PPT、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

讲座5：递归算法案例分析之汉诺塔游戏