漢諾塔問題（遞歸寫法）

漢諾塔問題是一個很經典的題目

哈哈，其實就是我們都已經很熟悉游戲規則了，在此我就在啰嗦一遍題目。

題目描述：

給定一個由n個圓盤組成的塔，這些圓盤按照大小遞減的方式套在第一根柱上。現要將整個塔移動到第三根柱上，每次只能移動一個圓盤，且較大的圓盤在移動過程中不能放置在較小的圓盤上面。

輸入：

輸入只有一個正整數n

輸出：

接下來每一行輸出一步移動步驟。

在此，我們討論比較一種簡單而且很好理解的做法——遞歸做法，既然遞歸，我們只要想好遞歸函數，其它的就交給函數吧。

好了，正經了，我們可以想象除了一個圓盤外最簡單的一種情況——兩個圓盤（哈哈），這種我們當然都知道了。

第一步：只要把上面的1號從A移動到B。

第二步：把2號從A移動到C。

第三步：再把1號從B移動到C就可以了。

（ps：手繪的圖，大家就忍受下吧[委屈]）

此時，我們想想，我們剛才的步驟是不是就是將兩個圓盤從A借助B移動到了C。在我們將1號從A移動到B的時候我們也可以理解成把1號這個圓盤從A借助C移動到B（但是事實我們并沒有借助）。這時我們就可以想象了，把那個1號圓盤當做成除了最下面那個圓盤外的（n-1）個圓盤，這時，是不是就豁然開朗了，對于n個圓盤我們一樣可以分為三步走[嘻嘻]。

第一步：將（n-1）個圓盤從A借助C移動到B

第二步：將第n個圓盤從A移動到C

第三步：將（n-1）個圓盤從B借助A移動到C

代碼實現下：

void hanoi(int n,char A,char B,char C) { if(n==0) return ; hanoi(n-1,A,C,B); step(n,A,C); hanoi(n-1,B,A,C); }

1

2

3

4

5

6

7

8

另外為了觀察，我們還需要寫一個打印移動步驟的函數。把id號圓盤從a位置移動到b位置。

上代碼：

void step(int id,char a,char b) // 把id號圓盤從a位置移動到b位置 { cout<<"第"<

1

2

3

4

輸出結果：

至于輸出的結果當然就是輸出：將n個圓盤從A借助B移動到C的步數，也就是

hanoi(n,‘A’,‘B’,‘C’)

。

完整代碼：

#include using namespace std; int cnt; void step(int id,char a,char b) { cout<<"第"<>n; hanoi(n,'A','B','C'); return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

感謝閱讀！

不妨點個贊再走唄，感謝支持！

加油！

共同努力！

Keafmd

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。