漢偌塔演算法
⑴ 漢諾塔遞歸演算法是什麼
漢諾塔是經典遞歸問題：
相傳在古印度聖廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。
游戲的目標：把A桿上的金盤全部移到C桿上，並仍保持原有順序疊好。操作規則：每次只能移動一個盤子，並且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置於A、B、C任一桿上。
如果A只有一個（A->C）。
如果A有兩個（A->B）,(A->C),(B->C)。
如果A有三個（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C)。
如果更多，那麼將會爆炸式增長。
遞歸：就是函數自己調用自己。 子問題須與原始問題為同樣的事，或者更為簡單；遞歸通常可以簡單的處理子問題，但是不一定是最好的。
其實遞歸在某些場景的效率是很低下的。尤其是斐波那契.從圖你就可以發現一個簡單的操作有多次重復。因為它的遞歸調用倆個自己。那麼它的遞歸的膨脹率是指數級別的，重復了大量相同計算。
起源：
漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。
大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
⑵ 漢諾塔遞歸演算法是什麼
如下：
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上。
⑶ 漢諾塔問題公式是什麼
漢諾塔問題（又稱河內塔問題）是根據一個傳說形成的一個問題：
有三根桿子A，B，C。A桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至C桿：
1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。
提示：可將圓盤臨時置於B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規則。
問：如何移？最少要移動多少次？
一般取N=64。這樣，最少需移動264-1次。即如果一秒鍾能移動一塊圓盤，仍將需5845.54億年。目前按照宇宙大爆炸理論的推測，宇宙的年齡僅為137億年。
在真實玩具中，一般N=8；這將需移動255次。如果N=10，需移動1023次。如果N=15，需移動32767次；這就是說，如果一個人從3歲到99歲，每天移動一塊圓盤，他僅能移動15塊。如果N=20，需移動1048575次，即超過了一百萬次。
先看hanoi(1, one, two, three)的情況。這時直接將one柱上的一個盤子搬到three柱上。注意，這里one柱或three柱到底是A、B還是C並不重要，要記住的是函數第二個參數代表的柱上的一個盤被搬到第四個參數代表的柱上。為方便，將這個動作記為：
one =》three
再看hanoi(2, one, two, three)的情況。考慮到hanoi(1)的情況已經分析過了，可知這時實際上將產生三個動作，分別是：
one =》two
one =》three
two =》three
很顯然，這實際上相當於將one柱上的兩個盤直接搬到three柱上。
再看hanoi(3, one, two, three)的情況。分析
hanoi(2, one , three, two)
one =》three
hanoi(2, two, one, three)
即：先將one柱上的兩個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的兩個盤搬到three柱上。這不就等於將one柱上的三個盤直接搬到three柱上嗎？
運用歸納法可知，對任意n，
hanoi(n-1, one , three, two)
one =》three
hanoi(n-1, two, one, three)
就是先將one柱上的n-1個盤搬到two柱上，再將one柱上的一個盤搬到three柱上，最後再將two柱上的n-1個盤搬到three柱上。這就是我們所需要的結果！
回答者：wuchenghua121 - 經理 四級 12-5 11:51
漢諾塔
漢諾塔（又稱河內塔）問題是印度的一個古老的傳說。開天闢地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其餘一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。解答結果請自己運行計算，程序見尾部。面對龐大的數字(移動圓片的次數)18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動。
後來，這個傳說就演變為漢諾塔游戲:
1.有三根桿子A,B,C。A桿上有若干碟子
2.每次移動一塊碟子,小的只能疊在大的上面
3.把所有碟子從A桿全部移到C桿上
經過研究發現，漢諾塔的破解很簡單，就是按照移動規則向一個方向移動金片：
如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→C
此外，漢諾塔問題也是程序設計中的經典遞歸問題。
補充：漢諾塔的演算法實現（c++）
#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;
}
C語言精簡演算法
/* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("請輸入數字n以解決n階漢諾塔問題：\n");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
回答者： Vanquisher_ - 舉人 五級 12-5 13:57
parcel::::::::::
program hanoi;
functionhanoi(x:integer):longint;
begin
if x=1 then hanoi:=1;
if x=2 then hanoi:=3;
else
begin
hanoi:=2*hanoi(x-1)+1;
end;
end;
begin
read(x){第幾個數 }
write(hanoi(x));
end.
思想就是：第N個就等於第n-1個乘以2+1次