漢諾塔問題演算法分析遞推關系式

① 漢諾塔問題求解

這個漢諾塔我覺得可以算是譚浩強書上最難得一個例題了 我也花費了很長時間才理解的 我把我曾經寫在書上的一些自己總結的東西寫給你 不知道你能不能看得明白
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
一。void hanoi(int n,char one,char two,char three)
{
if(n==1)move(one,three);
else{
二。hanoi(n-1,one,three,two);
三。move(one,three);
四。hanoi(n-1,two,one,three);
}
}
main()
{
int m;
printf("輸入塔的個數");
scanf("%d",&m);
hanoi(m,'A','B','C');
}
我上面標注了4個地方
假設這里輸入的是3
1的作用是從1座藉助2座移到3座
2的作用是將n-1個盤子移到2座，具體怎麼移動先不要管因為要進行遞歸操作
3的作用是將前賣弄最下面的盤子移到C
4的作用是將2座上剩下的N-1個盤子移到C上
以上的2，4進行了遞歸運算
運行過程如下
輸入3
void hanio(int 3,char x,char y,char z)
hanoi(n-1,one,three,two);
*****************→(2-1,x,y,z)→(1,x,y,z)→x→z
****(3-1,x,z,y)→運行2*********************x→y
*****************→(2-1,z,x,y)→(1,z,x,y) *z→y
move(one,three);
運行3**************************************x→z
hanoi(n-1,two,one,three);
運行4
******************→(2-1,y,z,x)→(1,y,z,x)→y-X
(3-1,y,x,z)*******運行2******************y→z
(2-1,x,y,z)→(1,x,y,z)******************x→z
不知道你能不能看得明白
這樣得到的答案就是
x->z;
x->y;
z→y,
x->z;
y->x;
y->z;
x->z;

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

漢諾塔問題實際上就是要將柱子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片黃金圓盤。

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

③ 漢諾塔問題

編程時，腦子里不要去思考遞歸過程（轉來轉去，會讓人很頭疼，一會兒就暈了）。
數列我想你是清楚的，所謂的遞歸，就是把an變成a(n-1)去處理問題，處理一個通項式是相同的方法，只要給出a1(或者還有a2)，這是遞歸結束的條件。
假設漢諾塔A B C三根針，只考慮移動最底下的盤子時，
如果只有一個盤子，就是直接A->C
如果只有兩個盤子，就是A->B 然後A->C
如果只有三個盤子，就是A->C A->B C->B 然後A->C
可以發現，
（1）如果想移動最底下的盤子，則，先要上面n-1個移動到B盤，即可。
（2）在移動B盤上的n-1中的最底下的盤子時，則改變一下源針和中間針即可，即：把B看成A A看成B
（3）接下來，在移動A盤上的n-2中的最底下的盤子時，則恢復源針和中間針即可，即：A還是A，B還是B。本步與第一步相同，即1 2兩步是在n>1時，的循環。
（4）當只有一個盤子時（n=1），就做「源針」到「目標針」即可，結束本次遞歸。
因此，遞歸程序只有以上三步，即可實現漢諾塔的移動。

④ 漢諾塔問題公式是什麼

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

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

⑤ 求漢諾塔遞歸全過程的演算法詳解圖，記得一定要是圖釋哦！！！

圖解是什麼意思呀。
這個演算法 那麼簡單沒必要搞得那麼復雜吧。
an = an-1 + 1;
你明白這個等式的意義嗎？
這個等式已經包含了遞歸演算法的全部含義。

an 表示 n個數的和，an-1 表示n-1個數的和 ，an = an-1 + 1;表示n個數的和可以通過n-1個數的和來求的。
上述說明哪些情況可以使用遞歸呢？
那就是：已知前一個步驟可以求得後一個步驟的結果的情況，並且前一個步驟和後一個步驟是有規律過度的。
比如漢諾塔問題：
移n個盤是已移n-1個盤為條件的，兩者的共同點是移盤。所以可以用f（n）表示移n個盤，f(n-1)表示移n-1個盤，那麼移n個盤和移n-1個盤有什麼關系呢？
這就需要預先分析問題才能得出具體的關系
在這個問題中，把n個盤從a移到c需要三個步驟來完成。
1.n-1個盤從a移到b
2 1個盤從a移到c
3 n-1個盤從b移到c
已知n-1個盤從a移到b是可行的，為什麼？
因為移1個盤是可行，那麼移2個盤也是可行，移 3個盤是已移2個盤為條件的，所以移3個盤也是可行的，所以移n個 盤是可行的。
所以根據已知條件可以解得：
設f(n, a, b,c) 表示 把n個盤從a移到c 藉助b --------------------------這里很關鍵，這是搞懂遞歸的關鍵關鍵。
那麼把n-1個盤從a移到b 藉助c 怎樣表示呢？
很明顯是：f(n-1, a, c,b)
那麼把1個盤從a移到c怎樣表示呢?
很明顯是：f(1, a, b,c)
那麼把n-1個盤從b移到c 藉助a 怎樣表示呢？
很明顯是：f(n-1, b, a,c)

所以f(n, a, b,c) = ( f(n-1, a,c,b) , f(1, a, b,c), f(n-1, b,a,c))
這和等差等比數列一個原理。
沒有什麼 特別的。

記住是問題有這樣遞推關系才可以使用這種方法。
如果要你計算1+2+8+22 的結果 你就不能使用遞歸。
因為該問題的後一步驟與前一步驟不具有規律性，所以已知前一個步驟並不能求的後一個步驟的值
1+2+3+4 ...+
這個問題就可以使用遞歸
原因你懂了吧。
至於爬樓梯問題，無限級分類 問題等一些遞歸問題，那不過時小菜一碟。
一句話：後一步驟依賴前一步驟並且二者聯系具有規律性，運用遞歸必然成功。

⑥ 漢諾塔問題通項公式

通項公式：H（k）=2^k-1。

漢諾塔游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置64個金盤。游戲的目標：把A桿上的金盤全部移到C桿上，並仍保持原有順序疊好。

操作規則：每次只能移動一個盤子，並且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置於A、B、C任一桿上。

分析：對於這樣一個問題，任何人都不可能直接寫出移動盤子的每一步，但可以利用下面的方法來解決。設移動盤子數為n，為了將這n個盤子從A桿移動到C桿，可以做以下三步：

(1)以C盤為中介，從A桿將1至n-1號盤移至B桿；

(2)將A桿中剩下的第n號盤移至C桿；

(3)以A桿為中介；從B桿將1至n-1號盤移至C桿。

事實上，上述方法設盤子數為n, n可為任意數，該法同樣適用於移動n-1個盤。因此，依據上法，可解決n -1個盤子從A桿移到B桿(第一步)或從B桿移到C桿(第三步)問題。現在，問題由移動n個盤子的操作轉化為移動n-2個盤子的操作。

依據該原理，層層遞推，即可將原問題轉化為解決移動n -2、n -3… … 3、2，直到移動1個盤的操作，而移動一個盤的操作是可以直接完成的。

(6)漢諾塔問題演算法分析遞推關系式擴展閱讀：

目前關於漢諾塔問題解決的一個最主要的觀點認為，完成漢諾塔任務時要對圓盤的移動順序進行預先計劃和回顧性計劃活動。

當問題呈現後，在開始第一步的移動之前，大多數被試都會根據設定好的目標狀態，對圓盤的移動順序進行預先計劃。以決定圓盤的移動順序，但是這種計劃能力的作用可能會受到問題難度的影響。

也有研究者認為，不是計劃能力而是抑制能力參與漢諾塔問題的解決過程。為了把更大的圓盤先放置於指定位置，必須讓較小的圓盤暫時偏離其最終應該放置的位置，但被試的自然反應總是「盡快」將圓盤移動到最終的目的地，如此反而導致錯誤，使移動步數更多，完成時間更長。

⑦ 漢諾塔的演算法

演算法介紹：當盤子的個數為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

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

(7)漢諾塔問題演算法分析遞推關系式擴展閱讀

由來：

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

⑧ 關於漢諾塔的問題。

利用遞歸解決漢諾塔，其最巧妙之處在於實參和形參的不斷變幻，實際的柱子也改變了，例如move(n-1,x,z,y)，借組z柱，移到y柱在進入遞歸時：形參move(int n,int x,int y,int z) /，移到z柱而在遞歸時; //，盤子數量減少了，和以前數學中的遞推證明非常接近,z所對應的實參, y 。就是形參x。數學的遞推證明的思想是;/ 函數的目的是把x柱的n個盤子，藉助y柱，假定n-1的時候是正確的，證明n也是正確就可以了。 遞歸過程的思想是，如果已經有了解決n的方法（漢諾塔中，移動n-1個盤子），怎麼來處理當前n的問題（如果n-1個盤子已經移好了，那隻要把最後一個盤子移過去就可以）。當然理解計算機的遞歸過程，柱子改變了; 這是把x柱的n-1個盤子，還要處理一下遞歸的結束條件（當n=1的時候），否則遞歸就不會結束了，在遞歸過程中是不斷改變的。注意

⑨ 漢諾塔問題公式是什麼

求汗諾塔N個盤子須幾次移動時得到了下面的遞推公式: a[1]=1; a[n]=a[n-1]*2+1; 請教通項公式? a[1]=1; a[n]=a[n-1]*2+1; 可得a[i]=2^i-1; 證明,採用數學歸納法: 1、猜想a[i]=2^i-1 2、當i=1時,顯然成立。 3、...

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

如下：

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