經典遞歸 - 漢諾塔問題

最近，想復習一下C語言，所以筆者將會在掘金每天更新一篇關于C語言的文章！ 各位初學C語言的大一新生，以及想要復習C語言/C++知識的不要錯過哦！ 夯實基礎，慢下來就是快！

漢諾塔問題

百度百科

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

不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動呢?這里需要遞歸的方法。假設有n片，移動次數是f(n).顯然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時，

假如每秒鐘一次，共需多長時間呢？一個平年365天有31536000秒，閏年366天有31622400秒，平均每年31557600秒，計算一下：

18446744073709551615秒

問題分析

A上面放的盤子上面小下面大，借助B盤，將A中的盤子移動到C，移動時要保證B,C的盤子都是上面小下面大,要一個一個盤子移動

解決方法

解決方法:

1.把A中的n-1個盤子通過C移動到B

2.把A中的剩余的1個盤子移到C

3.把B中的n-1個盤子，通過A移到C 不斷遞歸

代碼分析

void move(char pos1, char pos2) { printf("%c->%c ", pos1, pos2); } /* n:要移動的盤子數， pos1：起始位置 pos2：中轉位置 pos3：目的位置 */ void Hanoi(int n, char pos1, char pos2, char pos3) { if (n == 1) { move(pos1, pos3); //只有一個盤子，直接從pos1->pos3 } else { /*(1)以C盤為中介，從A桿將1至n - 1號盤移至B桿； (2)將A桿中剩下的第n號盤移至C桿； (3)以A桿為中介；從B桿將1至n - 1號盤移至C桿。*/ Hanoi(n - 1, pos1, pos3, pos2); //以C盤為中介，從A桿將1至n - 1號盤移至B桿 move(pos1, pos3);//將A桿中剩下的一個盤移至C桿； Hanoi(n - 1, pos2, pos1, pos3);//以A桿為中介；從B桿將1至n - 1號盤移至C桿。 } } int main() { Hanoi(3, 'A', 'B', 'C'); return 0; }

明天將會給大家帶來經典下一個經典的遞歸問題-青蛙跳臺階問題！歡迎大家關注

今天就先到這吧~感謝你能看到這里！希望對你有所幫助！歡迎老鐵們點個關注訂閱這個專題！ 同時歡迎大佬們批評指正！

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