經典益智遊戲讓你一秒掌握C語言遞歸方法論

遞歸

遞歸，就是在運行的過程中調用自己。

構成遞歸需具備的條件：

1. 子問題須與原始問題為同樣的事，且更為簡單；

2. 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。

我們用遞歸的方式去解決問題則異常的簡單，甚至簡單到我們給出程序解決了問題，還有可能搞不明白問題到底是怎麼解決的。

當然在使用遞歸解決問題之前，我們必須要學會用遞歸的方法去思考問題。

下面我們試圖使用C程序來解決一個益智遊戲--漢諾塔:

漢諾塔

漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

漢諾塔問題，使用傳統的思維方式去尋求解決方案，顯然比較困難。

下面我們採用遞歸的方式來解決這個問題。·

使用遞歸解決實際問題，需要找准兩個關鍵點：

基準情況，不需使用遞歸解決，一般能輕易得出答案的情況

如何將問題分解為規模更小但形式相同的子問題

對於漢諾塔而言，只有一個盤時，就是基準情況，我們可以直接將盤從源桿移動到目標杆：

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

將上述思路整理成偽代碼：

加入基準情況，我們的漢諾塔函數實現如下：

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

這是完整的代碼：

#include

using namespace std;

void hanoi(int n,char a,char b,char c)

{

if(n==1)

cout

else

{

hanoi(n-1,a,c,b);

cout

hanoi(n-1,b,a,c);

}

}

int main()

{

int n;

cout

cout

hanoi(n,"A","B","C");

return 0;

}

結果如下：

想要一起學習C++的可以加裙六二六八七一九一六，裙內有各種資料滿足大家，歡迎加裙

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！