河內塔演算法

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

漢諾塔遞歸演算法是：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億年，不說太陽系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經灰飛煙滅。

2. 漢諾塔怎麼玩

一位美國學者發現的特別簡單的方法：只要輪流用兩次如下方法就可以了。

把三根柱子按順序排成「品」字型，把所有圓盤按從大到小的順序放於柱子A上，根據圓盤數量來確定柱子排放的順序：

n若為偶數的話，順時針方向依次擺放為：ABC；而n若為奇數的話，就按順時針方向依次擺放為：ACB。這樣經過反復多次的測試，最後就可以按照規定完成漢諾塔的移動。

因此很簡單的，結果就是按照移動規則向一個方向移動金片：

如3階漢諾塔的移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C。

(2)河內塔演算法擴展閱讀：

由來

法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。

不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸於盡。

3. C語言漢諾塔問題，請問這個n=3的詳細步驟是什麼呀，大一新生沒聽懂

這是漢諾塔的演算法的問題。程序本身很簡單。

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

這個主要是看演算法，再一個就是遞歸的學習，程序本身非常簡單。

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

漢諾塔是經典遞歸問題：

相傳在古印度聖廟中，有一種被稱為漢諾塔(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片黃金圓盤。

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

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

漢諾塔問題實際上就是要將柱子A上由小到大排列的圓環按照相同的大小順序移動到柱子C，之間的過程可以使用柱子B。

其遞歸的歸納思想是這樣的：

（1）首先，當只有一個盤子的時候只需要將A上的1號盤子移動到C上就行了

（2）當有2個盤子在A上的時候，需要將A上的1號盤子（由上往下數）移動到B上，再將A上的2號盤子移動到C上，之後將B上的1號盤子移動到C上

（3）當有3個盤子在A上的時候，需要將A上的1號和2號盤子移動到B上（需要藉助C），之後將A上的3號盤子移動到C上，再將B上的盤子移動到C上（需要藉助A）

（...）以此類推

（N）當有N個盤子在A上的時候，需要將A上的N-1個盤子移動到B上（需要藉助C），之後將A上的第N個盤子移動到C上，再將B上的盤子移動到C上（需要藉助A）

起源

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

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

6. 7層漢諾塔在中間移動到右側需要多少步

1、七層的漢諾塔游戲最少需要127步。其實演算法非常簡單，當盤子的個數為n時，移動的次數應等於2^n_1。後來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。

2、答案是2的n次方減1，n是塔的層高。例如7層漢諾塔需要步驟為2^7-1=128-1=127步遞歸解決問題就是將一個大問題分解成類似的小問題解決，漢諾塔每增加一層，需要多增加一層遞歸調用，所以解決問題難度也成幾何增長。

3、層漢諾塔從右邊放到中間要藉助第三個柱子才能移動到目的地。漢諾塔，也叫河內塔，是一個很不錯的益智玩具。

4、ACB。這樣經過反復多次的測試，最後就可以按照規定完成漢諾塔的移動。因此很簡單的，結果就是按照移動規則向一個方向移動金片：如3階漢諾塔的移動：A→C，A→B，C→B，A→C，B→A，B→C，A→C。

5、漢諾塔規律總結口訣是單左雙右，先小後大，一步兩步，循環往復。設3個柱子分別是甲，乙，丙，把3根柱子看成一個循環，也就是說，甲的右邊是乙，乙的右邊是丙，而丙的右邊則回到甲，同理，甲的左邊就是丙。

6、所以n個盤子最少要移動2^n-1，這道題和c++沒關系吧。

7. 漢諾塔問題公式是什麼

漢諾塔問題（又稱河內塔問題）是根據一個傳說形成的一個問題：

有三根桿子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次