遞歸演算法漢諾塔

⑴ 求大神講解一下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。

⑵ 漢諾塔遞歸演算法

漢諾塔
遞歸演算法
Hanoi(int
n,char
Start,Middle,End)
begin
if
n=1
then
輸出Start->End
else
begin
Hanoi(n-1,Start,End,Middle);
//要把Start的盤子藉助middle移動到End
先把n-1個盤子由start移到middle
//這步做完後
Start上
n-1個盤子移到中轉盤
Middle上
輸出
Start->End;
//把Start上最後一個盤子移到End
Hanoi(n-1,Middle,Start,End);
end
end

⑶ 用遞歸法求漢諾塔問題 求解

c1、c2都是臨時變數，分別代表從A移到B時移動了幾次，以及從B移動到C時移動了幾次，兩者相加再加1，就是從A移動到C的移動次數。
它們的賦值就是通過遞歸調用得到啊，c1 = move( n-1, A, C, B )...

⑷ 漢諾塔遞歸演算法是什麼

hanot (n-1,b,a,c);（解釋：在把B塔上的(n-1))個藉助A塔移動到C塔）

為了實現 n個盤從 藉助c 從a 移動到 b

思路如下：

首先考慮極限當只有一個盤的時候，盤直接從 a -> b即可。

當有2個盤的時候，把1號盤從a -> c 然後 把2號盤 a->b 再 把 2好盤從 c - > b。

當有n個盤的時候，把 n-1個 盤 藉助 b 移動到 c 然後將 n號盤從 a -> b。

這時候只要將 n-1想辦法從c移動到 b 藉助 a 那麼就可以先把 n-2個盤藉助b移動到a。

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

構成遞歸需具備的條件：

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

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

在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。

以上內容參考：網路-遞歸公式

⑸ 漢諾塔遞歸問題

#include <fstream>
#include <iostream>
using namespace std;
ofstream fout("out.txt");
void Move(int n,char x,char y)
{
fout<<"把"<<n<<"號從"<<x<<"挪動到"<<y<<endl;
}

void Hannoi(int n,char a,char b,char c)
{
if(n==1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}
int main()
{
fout<<"以下是7層漢諾塔的解法:"<<endl;
Hannoi(7,'a','b','c'); //調用
fout.close();
cout<<"輸出完畢！"<<endl;
return 0;

漢諾塔使用遞歸的方法來實現的
可能你對遞歸還沒理解透，反正記住，程序總是一步一步的按順序執行，有調用函數就先在調用的地方設個斷點，轉入函數執行，執行完了又返回斷點，萬變不離其宗！

程序執行的順序
Hannoi(7,'a','b','c');這里調用函數，轉入函數執行並傳入參數n=7

第一步，執行判斷語句，根據n的值進入else執行
第二步，執行Hannoi(n-1,a,c,b);這時是調用函數本身，也就是所謂的遞歸了，你看傳入的值n-1，相當於傳入n=6，還有a,c,b,的值，這個要注意順序，在調用的時候a,c,b的值是第一次傳入的值
第三步，執行Hannoi(int n,char a,char b,char c)函數，這點能理解吧，這次傳入的值n=6了，但是a,b,c,的值相對於第一次的值有改變了哦，可以理解成，a(2)=a(1),b(2)=c(1),c(2)=b(1),這里括弧里代表函數調用的次數，其實這里最容易弄混的就是，a,b,c的值，自己用本子把每次傳入的值的a,b,c按傳入順序列出來，會容易理解些
同樣，執行判斷，n>1進入else,按順序執行，先執行Hannoi(n-1,a,c,b);然後又是調用本身，注意傳入的值，是a(2),c(2),b(2),又轉入去執行Hannoi(int n,char a,char b,char c)函數,這時接收的值a(3)=a(2),b(3)=c(2),c(3)=b(2)，就像在兜圈子是吧，沒錯。後面你自己做張表來理一下。
這樣兜圈子直到n=1。你看Hannoi(n-1,a,c,b);每次n都是減了1的，所以n-1次遞歸的時候，就直接執行if(n==1)裡面的了，終於有所改變了是吧，他執行的是Move(1,a,c); 也就是輸出函數，執行完Move(int n,char x,char y) 返回原來的調用的那個斷點。繼續向後。沒有語句了，就返回上次調用的函數，上次調用Hannoi(int n,char a,char b,char c)是誰呢，就是n-2次的Hannoi(int n,char a,char b,char c)中的Hannoi(n-1,a,c,b);調用的他啊，返回到這里，繼續向後又遇到Move(n,a,c); 這里不用講解了吧，輸出後返回來，繼續向後執行Hannoi(n-1,b,a,c); 新的遞歸開始了，看你再列個新的表理一下呢，注意傳入的值和他的順序，還有n的值這時是多少。

其實我的講解你可能看的也不是很清楚，關鍵是要理解到遞歸他無非就是調用自己，調用完返回就是返回上次調用的地方，也是他自己，只是倆次的函數使用中的值是不一樣的，這個值呢，最好拿筆記下來，並寫個次數才容易理解和分析。

這遞歸程序很經典，值得研究，你會發現他是如此的巧妙，太棒了！建議測試的時候不要把n設的太大，不然容易死機！想想裡面的循環次數就真令人咂舌了！

⑹ 漢諾塔問題的遞歸演算法流程圖

關鍵是第一步移法，奇數層的說，3層在第一柱，後兩根柱數數：123。所以，第一塊應放在第二根柱，4層，第一塊放第三柱。...........奇數層第一塊放第二柱，偶數層第一塊放第三柱。

⑺ 漢諾塔遞歸演算法是什麼

漢諾塔遞歸演算法是：f（n）=2^n-1。

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

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

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

⑻ 漢諾塔遞歸演算法是什麼

如下：

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上。

⑼ 遞歸演算法 漢諾塔 演示

整理分析結果：把第1步中化簡問題的條件作為遞歸 結束條件，將第3步分析得到的演算法作為遞歸演算法。
定義函數movedisc( n，fromneedle，toneedle，usingneedle)。將 fromneedle 桿上的 N 個圓盤，藉助 usingneedle 桿，移動到 toneedle 桿上。
移動N個圓盤的遞歸演算法描述如下：
movedisc ( n，fromneedle，toneedle，usingneedle )
{ if ( n==1 ) 將 n 號圓盤從 fromneedle 上移到 toneedle;
else {
① movedisc ( n-1，fromneedle，usingneedle，toneedle )
② 將 n 號圓盤從 fromneedle 上移到 toneedle;
③ movedisc ( n-1，usingneedle，toneedle，fromneedle )
}
}

下面是程序
int i=0; /* 移動圓盤數量計數器 */
main( )
{ unsigned n;
scanf ("%d", &n);
movedisc ( n,』a』,』b』,』c』); /* 將A上的N個圓盤藉助C將移動到B上 */
printf( "\t Total: %d\n", i );
}
movedisc ( n, fromneedle, toneedle, usingneedle )
unsigned n;
char fromneedle, toneedle, usingneedle;
{ if ( n == 1 )
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
else {
movedisc ( n-1, fromneedle, usingneedle, toneedle );
printf("%2d-(%2d): %c ==> %c\n",++i, n,fromneedle,toneedle);
movedisc ( n-1, usingneedle, toneedle, fromneedle );
}
}

⑽ 關於漢諾塔問題的遞歸演算法 演算法如圖 嗯 我看不懂if語句以後的演算法 if(n){hanoi(n-1

遞歸方法最重要的清楚遞歸邏輯，也就是func(n)函數的含義。
漢諾塔的邏輯就是，先想辦法把上面n-1個塊挪到中間，再挪最底下那個到右側，最後再把n-1個塊挪到右側。hanoi(n,x,y,z)的含義，就是把n個塊從x挪到z上，可以利用中間柱子y。
使用遞歸的時候，看清楚最上層邏輯就好，不要糾結遞歸走到下一層的具體步驟。