講座5：遞歸算法案例分析之漢諾塔游戲

說在前面

在上一節(jié)“遞歸算法之尋找輕球問題”中，我們研究了如何分析實(shí)際問題、構(gòu)造數(shù)學(xué)模型、推導(dǎo)遞歸公式的方法。并不是所有的遞歸函數(shù)都能構(gòu)造簡明的遞歸公式，今天我們將通過“漢諾塔游戲”案例，進(jìn)一步分析遞歸函數(shù)的設(shè)計(jì)方法，理解遞歸算法簡單明晰的特征。

新課引入

經(jīng)典案例

課后練習(xí)

黑白棋子的移動(dòng)。有2*n個(gè)棋子（n>=4）排成一行，開始位置為白子全部在左邊，黑子全部在右邊，如下圖為n=5的情形：

○○○○○●●●●●

移動(dòng)棋子的規(guī)則是：每次必須同時(shí)移動(dòng)相鄰的兩個(gè)棋子，顏色不限，可以左移也可以右移到空位上去，但不能調(diào)換兩個(gè)棋子的左右位置。每次移動(dòng)必須跳過若干個(gè)棋子（不能平移），要求最后能移成黑白相間的一行棋子。如n=5時(shí)，成為：

○●○●○●○●○●

你的任務(wù)是根據(jù)輸入的棋子數(shù)量，編程打印出黑白棋子的移動(dòng)過程。

程序運(yùn)行界面如下圖所示：

（1）先思考當(dāng)n=4時(shí)的情形，下圖給出了黑白棋子的初始位置和前2步移動(dòng)過程，請寫出剩下的移動(dòng)過程。

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

1 ○○○——●●●○●

2 ○○○●○●●——●

（2）當(dāng)n=5時(shí)，需要移動(dòng)幾次，就能將問題轉(zhuǎn)換成求解n=4時(shí)的情形？

需要本文PPT、源代碼和課后練習(xí)答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

講座1：遞歸算法案例分析之入門第一課

講座2：遞歸算法案例分析之猴子吃桃問題

講座3：遞歸算法案例分析之斐波那契數(shù)列

講座4：遞歸算法案例分析之尋找輕球問題