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

Python算法之旅

共 852字,需浏览 2分钟

 ·

2021-08-23 06:52

说在前面

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


新课引入


经典案例


课后练习

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

○○○○○●●●●●

移动棋子的规则是:每次必须同时移动相邻的两个棋子,颜色不限,可以左移也可以右移到空位上去,但不能调换两个棋子的左右位置。每次移动必须跳过若干个棋子(不能平移),要求最后能移成黑白相间的一行棋子。n=5时,成为
○●○●○●○●○●
你的任务是根据输入的棋子数量,编程打印出黑白棋子的移动过程。
程序运行界面如下图所示:

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

0 ○○○○●●●●——   ("—"表示空位)

1 ○○○——●●●○●

2 ○○○●○●●——●

(2)当n=5时,需要移动几次,就能将问题转换成求解n=4时的情形?


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

我们专注Python算法,感兴趣就一起来!

相关优秀文章:

阅读代码和写更好的代码

最有效的学习方式

讲座1:递归算法案例分析之入门第一课

讲座2:递归算法案例分析之猴子吃桃问题

讲座3:递归算法案例分析之斐波那契数列

讲座4:递归算法案例分析之寻找轻球问题


浏览 15
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报