hanoi塔的遞歸演算法

A. 漢諾塔遞歸演算法是什麼

如下：

1、漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

2、抽象為數學問題：從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數。

演算法分析（遞歸演算法）：

實現這個演算法可以簡單分為三個步驟：把n-1個盤子由A 移到 B；把第n個盤子由 A移到 C；把n-1個盤子由B 移到 C。從這里入手，在加上上面數學問題解法的分析，我們不難發現，移到的步數必定為奇數步。

1、中間的一步是把最大的一個盤子由A移到C上去。

2、中間一步之上可以看成把A上n-1個盤子通過藉助輔助塔（C塔）移到了B上。

3、中間一步之下可以看成把B上n-1個盤子通過藉助輔助塔（A塔）移到了C上。

B. 求漢諾塔C遞歸演算法詳細解答

Hanoi塔問題, 演算法分析如下，設A上有n個盤子。
如果n=1，則將圓盤從A直接移動到C。
如果n=2，則：
（1）將A上的n-1（等於1）個圓盤移到B上；
（2）再將A上的一個圓盤移到C上；
（3）最後將B上的n-1（等於1）個圓盤移到C上。
如果n=3，則：
A）將A上的n-1（等於2，令其為n`）個圓盤移到B（藉助於C），步驟如下：
（1）將A上的n`-1（等於1）個圓盤移到C上。
（2）將A上的一個圓盤移到B。
（3）將C上的n`-1（等於1）個圓盤移到B。
B）將A上的一個圓盤移到C。
C）將B上的n-1（等於2，令其為n`）個圓盤移到C（藉助A），步驟如下：
（1）將B上的n`-1（等於1）個圓盤移到A。
（2）將B上的一個盤子移到C。
（3）將A上的n`-1（等於1）個圓盤移到C。到此，完成了三個圓盤的移動過程。

從上面分析可以看出，當n大於等於2時， 移動的過程可分解為三個步驟：第一步 把A上的n-1個圓盤移到B上；第二步 把A上的一個圓盤移到C上；第三步 把B上的n-1個圓盤移到C上；其中第一步和第三步是類同的。 當n=3時，第一步和第三步又分解為類同的三步，即把n`-1個圓盤從一個針移到另一個針上，這里的n`=n-1。

Hanoi塔問題中函數調用時系統所做工作

一個函數在運行期調用另一個函數時，在運行被調用函數之前，系統先完成3件事：

①將所有的實參、返回地址等信息傳遞給被調用函數保存。

②為被調用函數的局部變數分配存儲區；

③將控制轉移到被調用函數的入口。

從被調用函數返回調用函數前，系統也應完成3件事：

①保存被調用函數的結果；

②釋放被調用函數的數據區；

③依照被調用函數保存的返回地址將控制轉移到調用函數。

當有多個函數構成嵌套調用時，按照「後調用先返回」的原則（LIFO），上述函數之間的信息傳遞和控制轉移必須通過「棧」來實現，即系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時，就為其在棧頂分配一個存儲區，每當從一個函數退出時，就釋放其存儲區，因此當前運行函數的數據區必在棧頂。堆棧特點：LIFO，除非轉移或中斷，堆棧內容的存或取表現出線性表列的性質。正是如此，程序不要求跟蹤當前進入堆棧的真實單元，而只要用一個具有自動遞增或自動遞減功能的堆棧計數器，便可正確指出最後一次信息在堆棧中存放的地址。

一個遞歸函數的運行過程類型於多個函數的嵌套調用，只是調用函數和被調用函數是同一個函數。因此，和每次調用相關的一個重要的概念是遞歸函數運行的「層次」。假設調用該遞歸函數的主函數為第0層，則從主函數調用遞歸函數為進入第1層；從第i層遞歸調用本函數為進入下一層，即i＋1層。反之，退出第i層遞歸應返回至上一層，即i－1層。為了保證遞歸函數正確執行，系統需設立一個「遞歸工作棧」，作為整個遞歸函數運行期間使用的數據存儲區。每一層遞歸所需信息構成一個「工作記錄」，其中包括所有實參、所有局部變數以及上一層的返回地址。每進入一層遞歸，就產生一個新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個工作記錄，則當前執行層的工作記錄必是遞歸工作棧棧頂的工作記錄，稱這個記錄為「活動記錄」，並稱指示活動記錄的棧頂指針為「當前環境指針」。
P.S.代碼如您寫的。

C. C++ hanoi塔函數遞歸問題

程序就會按照你帶的參數去繼續調用void hanoi(int n, char one, char two, char three)函數了。這就是調用。以下是我曾經分析過的這個問題。供你參考。附上源程序。

//解決漢諾塔的核心概念：需要將大的在下小的在上的n個盤子從A藉助B移動到C，
//全部還是按照大的在下小的在上的原則。
//可以分解為簡單的3個過程，以實現遞歸
//過程0：A的N個盤子藉助B移動到C； //move(n,a,b,c); //PS1//備注1
//過程1：A的N-1個盤子藉助C移動到B； //move(n-1,a,c,b);
//過程2：A的最後一個盤子直接移動到C //printf("%c->%c\n",a,c); //簡化
//過程3：B的N-1個盤子藉助A移動到C； //move(n-1,b,a,c);
//過程3實際上回到了假定的過程0 //move(n-1,b,a,c);//和PS1相比:參數AB位置發生變化，n變為n-1
//於是，開始了新一輪的過程1、2、3，並以此實現遞歸
//本程序關鍵在於理解遞歸演算法
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long count;
void move(int n,char a,char b,char c)
{
if(n==1)
{
printf("\t第%d次移動%c->%c\n",++count,a,c); //當n只有1個的時候直接從a移動到c
}
else
{
move(n-1,a,c,b); //第n-1個要從a通過c移動到b
printf("\t第%d次移動%c->%c\n",++count,a,c); //用於顯示移動的每一步//上面一個函數運行後的最後一個盤的移動路線
move(n-1,b,a,c); //n-1個移動過來之後b變開始盤，b通過a移動到c，這邊很難理解//
}
}

int main(void)
{
int n;
count=0;
printf("請輸入要移動的圓盤數：");
scanf("%d",&n);
move(n,'a','b','c');
printf("%d個圓盤共需移動%d次\n",n,count);
return(0);
}
//本人也新學，供參考

D. 漢諾塔的演算法

演算法介紹：當盤子的個數為n時，移動的次數應等於2^n–1。後來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放A、B、C；

若n為奇數，按順時針方向依次擺放A、C、B。

所以結果非常簡單，就是按照移動規則向一個方向移動金片：如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C

漢諾塔問題也是程序設計中的經典遞歸問題。

(4)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秒，平均每年31556952秒，計算一下：18446744073709551615秒。

這表明移完這些金片需要5845.54億年以上，而地球存在至今不過45億年，太陽系的預期壽命據說也就是數百億年。真的過了5845.54億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

E. (Hanoi)漢諾塔的遞歸問題

哈哈！正好我們上周實訓也是做的漢諾塔演示程序，不過是C#。其實這里的循環問題你一定要用抽象思維，n就是一個變數，按盤子移動的規律設計代碼的！主要是計算了盤子的起點和終點坐標，再用的遞歸演算法。
不知道我這樣講，有沒一點幫助哈！

F. 漢諾塔遞歸演算法

1個只要1次2個碟子要3次3個要7次歸納法可以推得復雜度為2^n-1這個可以證明的，只是證明很復雜。

G. 求大神講解一下C語言漢諾塔遞歸演算法的簡易理解

一開始我接觸漢諾塔也是很不解，隨著代碼量的積累，現在很容易就看懂了，因此樓主主要還是對遞歸函數的理解不夠深刻，建議你多寫一些遞歸程序，熟練了自己就能理解。
圓盤邏輯移動過程+程序遞歸過程分析
hanoi塔問題, 演算法分析如下，設a上有n個盤子，為了便於理解我將n個盤子從上到下編號1-n，標記為盤子1，盤子2......盤子n。
如果n=1，則將「 圓盤1 」 從 a 直接移動到 c。
如果n=2，則：
（1）將a上的n-1（等於1）個圓盤移到b上，也就是把盤1移動到b上；
（2）再將a上 「盤2」 移到c上；
（3）最後將b上的n-1（等於1）個圓盤移到c上，也就是第（1）步中放在b上的盤1移動到c上。
注意：在這里由於超過了1個盤子，因此不能直接把盤子從a移動到c上，要藉助b，那
么 hanoi（n，one，two，three）的含義就是由n個盤子，從one移動到three，如果n>2
那麼就進行遞歸，如果n=1，那麼就直接移動。
具體流程：
hanoi（2，a，b，c）；由於2>1因此進入了遞歸的環節中。
<1>執行hanoi（1，a，c，b）：這里就是剛才的步驟（1），代表藉助c柱子，將a柱子上的 1個圓盤（盤1）移動到b柱子，其實由於是n=1，此時c柱子並沒被用到，而是直接移動了。
<2>執行hanoi（1，a，b，c）：這是步驟（2），藉助b柱子，將a柱子上的一個圓盤（盤2）移動到c柱子上。這里由於也是n=1，也並沒有真正藉助b柱子，直接移動的。
<3>執行hanoi（1，b，a，c）：這是步驟（3），將b上的一個盤子（盤1）移動到c
函數中由於每次調用hanoi的n值都是1，那麼都不會進入遞歸中，都是直接執行了mov移動函數。
如果n=3，則：（倒著想會想明白）移動的倒數第二部，必然是下面的情況
（1）將a上的n`-1（等於2）個圓盤移到c上，也就是將盤1、盤2 此時都在b柱子上，只有這樣才能移動最下面的盤子（盤3）。那麼由於現在我們先忽略的最大的盤子（盤3），那麼我們現在的目標就是，將兩個盤子（盤1、盤2）從a柱子上，藉助c柱 子，移動到b柱子上來，這個過程是上面n=2的時候的移動過程，n=2的移動過程是「2 個盤子，從柱子a，藉助柱子b，移動到柱子c」。現在是「2個盤子，從柱子a，藉助柱子 c，移動到柱子b上」。因此移動過程直接調用n=2的移動過程就能實現。
（2）將a上的一個圓盤（盤3）移到c。
（3）到這一步，由於已經將最大的盤子（盤3）移動到了目的地，此時無論後面怎麼移動都不需要在用到最大的那個盤子（盤3），我們就先忽略他，剩下的目標就是將b上面的n-1個盤子（盤1、盤2）移動到c上，由於a上沒有盤子了，此時要完成上面的目標，就要藉助a盤子。最終達到的目標就是將b上的2個盤子，藉助a移動到c上，這個過程就是當n=2時分析的過程了，僅僅是最開始的柱子（b柱子）和被藉助的柱子（a柱子）不同了。所以直接調用n=2時候的過程就能股實現了。
具體執行過程：
hanoi（3，a，b，c）；由於3>1因此進入了遞歸的環節中。
<1>執行hanoi(2,a,c,b):這里代表剛才的步驟（1），將兩個盤子（盤1、盤2）從a移動到b，中間藉助c。根據n=2的分析過程，必然是能夠達到我們的目的。
<2>執行hanoi（1，a，b，c）：現在a上只有一個盤子（盤3），直接移動到c上面即可。
<3>執行hanoi（2，b，a，c）：此時對應步驟（3），剩下的目標就是將b上的兩個盤子，藉助a移動到c上。那麼同樣根據n=2的移動過程，必然能達到目的。

最終實現了3個盤子從a，藉助b移動到了c。

H. 如何理解漢諾塔的遞歸

遞歸就是一層套一層，函數自己調用自己，直到出現限制條件為止。函數自己調用自己，可以理解為sum = sum + M；給這個加一個循環 是不是就可以求出總和了；意思是一樣的自己調自己，漢諾塔這個比較深，你可以用遞歸的方式去求所有數字的和，多學幾遍你自然就會了。1. 漢諾塔可以理解為一個移動塔的游戲，把一個n層的塔從一個柱子移動到另一個柱子上2.這就是漢諾塔遞歸原型 hannuota（n, A,C）--n層的塔從A柱移動到C柱；每次必須回歸到這個原型才算一次遞歸完成！<就像1-100的遞歸累加f(n)=f(n-1)+n； 此時f(n)是遞歸原型，回歸到f(n-1)>3.中間需要藉助一個柱子B，漢諾塔原型寫成hunnuota(n,A,B,C)--n層塔從A柱藉助B柱移動到C柱，這一步應該能夠理解吧；4.遞歸都要求有一個出口，也即是控制條件，當n=1時直接把塔從A移動到C即可，這就是出口<如果n=2則需要移動兩次才行，無法一次完成，不能出去>5.n>1時,這一步是理解漢諾塔遞歸的關鍵，必須形成n-1層往C柱移動的形式，分為三步：a. n層無法一次移動，那麼可以理解為先把A上面的n-1層移動到B柱<hannuota(n-1,A,C,B)>-------b A柱剩下第n層的塔移動到C，C 然後形成B柱上的n-1層移動到C柱上--<hannuota（n-1,B,A,C）此時已經形成了遞歸的原型 不同的只是中間藉助的柱子不同罷了,hanoi(n, a, b, c)這個函數的作用是：將n個金片從a移動到c（通過b）。遞歸完成

I. 證明hanoi塔問題的遞歸演算法與非遞歸演算法實際上是一回事

證明：設解決漢諾塔問題的函數為Hanoi（n，A，B，C）
用數學歸納法即可證明上述問題
當n=1和n=2時容易直接驗證。設當k<=n-1時，遞歸演算法和非遞歸演算法產生完全相同的移動序列。考察k=n時的情形。
將移動分為順時針移動（S），逆時針移動（N）和非最小圓盤塔間的移動（F）三種情況。
（1）當n為奇數時，順時針非遞歸產生的移動序列為S,F,S,F,······S，逆時針非遞歸演算法產生的序列為N,F,N,F,······N。
當n為偶數時，順時針非遞歸產生的移動序列為N,F,N,F,······N，逆時針非遞歸演算法產生的序列為S,F,S,F,······S。
（2）當n為奇數時，順時針遞歸演算法Hanoi（n，A，B，C）產生的移動序列為
Hanoi（n-1，A，C，B）產生的移動序列，F，Hanoi（n-1，C，B，A）產生的移動序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均為偶數圓盤逆時針移動問題。由數學歸納法知，它們產生的移動序列均為S,F,S,F,······S。因此Hanoi（n，A，B，C）產生的移動序列為S,F,S,F,······S。
當n為偶數時，順時針遞歸演算法Hanoi（n，A，B，C）產生的移動序列為
Hanoi（n-1，A，C，B）產生的移動序列，F，Hanoi（n-1，C，B，A）產生的移動序列
其中，Hanoi（n-1，A，C，B）Hanoi（n-1，C，B，A）均為奇數數圓盤逆時針移動問題。由數學歸納法知，它們產生的移動序列均為N,F,N,F,······N。因此Hanoi（n，A，B，C）產生的移動序列為N,F,N,F,······N。
當n為奇數和偶數時的逆時針遞歸演算法也類似。
由數學歸納法可知，遞歸演算法和非遞歸演算法產生相同的移動序列。

J. 漢諾塔問題具體是怎麼遞歸的

有a，b，c三個柱子
hanoit(n-1,a,c,b);//先藉助c，把上面n-1個從a移動到b
move(a,c);//把第n個從a移動到c
hanoit(n-1,b,a,c);//把上面n-1個從b移動到c
移動第n個要先移動前n-1個。