漢諾塔問題遞歸演算法

1. 用遞歸法求漢諾塔問題 求解

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

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

3. 漢諾塔遞歸演算法求詳解 （研究了5天了，沒有理解，如果能教會我願支付寶付現金20元）

首先要知道漢諾塔的基本思路.
漢諾塔有3根柱子. 為什麼要有3根呢? 那是因為要直接使一個柱子上的碟片全部移動到另一根柱子是不行的,必須要通過第三根柱子來中轉一下.
這種中轉思路就是關鍵了.
具體來說,如果我們要把A柱子上的碟片移動到C柱子上,那麼首先我們可以通過"某種方式"將A柱子上除了最底下的碟片以外的所有碟片移動到B柱子上去,也就是拿B柱子當中轉. 然後下一步就可以直接把A柱子上最底層的那張碟片移動到C柱子上了. 最後,我們再以同樣的方式,將B柱子上剩下的那堆碟片以同樣的"某種方式"移動到C上. 總體來看,我們就完成了A->C的碟片移動操作.

那麼剩下的問題就是,這"某種方式"是什麼呢? 其實思考一下可以發現,在進行這"某種方式"的時候,除去A上最大的那個,其餘碟片都是我們需要操作的, 這個時候由於A是最大,其他的碟片對他來說移動都沒有限制的(都會比他小). 那麼我們就可以暫時忽視這個最大的碟片.

以上面的例子來說,我們要移動A柱子上除了底層之外的所有碟片到B柱上,就可以暫時忽略掉A上最大的那個碟片. 發現沒有, 這個時候我們的問題變成是: 將A上的所有碟片(因為已經忽視掉了最大的那個了)移動到B上,C可以作為轉接(因為上面沒有碟片).

這一步意味著我們把一個n個碟片的漢諾塔問題轉化成了n-1個碟片的漢諾塔問題,從而這裡面就包含了遞歸意義.

最後說回到你的程序. 函數hanoi(n,a,b,c)正是這樣一個意味: 列印將a柱子上的n個碟片以b為中轉移動到c上的操作步驟. 而可以看到,在執行這個函數的時候,如果n=1,那麼由於只有一個碟片,可以直接列印a->c, 如果n>1,則先用hanoi(n-1,a,c,b), 以c為中轉將a上的n-1個碟片先移動到b上,再列印a->c,即將a上剩下最大的那個碟片移動到c, 然後再調用hanoi(n-1,b,a,c), 以a為中轉將b上的碟片移動到c上.
按如此的遞歸邏輯下去就可以得到全部的操作過程了.

4. 編程實現5個盤子的漢諾塔問題；（遞歸演算法）

//漢諾塔c++程序
#include
using
namespace
std;
void
hanoi(int,int,int,int);//用於遞歸的函數
void
print(int,int);//從一個樁移動到另一個樁
int
A=1,B=2,C=3;
static
int
counter
=
0;//用於計算總共移動的次數
int
main()
{
int
n;//移動的盤數
cout<<"please
enter
the
quantity
of
the
plates：";
cin>>n;
hanoi(n,A,B,C);
cout<<"Totally
used
"<
"<
評論
0
0
0
載入更多

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

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

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

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

7. 求漢諾塔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.代碼如您寫的。

8. 漢諾塔遞歸函數問題

遞歸其實很簡單,你只要曉得啥子是嵌套調用就可以了,所謂嵌套調用,就是在一個函數里調用另一個函數,main函數不能被調用的,所以遞歸就是有限次的嵌套調用本身函數,每次調用,系統都會重新分配內存,返回時就返回上次調用他的那塊內存中的調用函數處,這樣理解應該很簡單了

void move(int , char ,char,char); /*聲明函數,告訴系統我隨後要定義一個函數,他不對其中參數進行檢查,所以可以省略參數,一般只寫類型,表示有多少個什麼類型的參數,便於自己理解 */
main()
{int n;
printf("請輸入盤數n=" );
scanf("%d",&n);
printf("在3根柱子上移%d只盤的步驟為:\n",n);
move(n,'a','b','c');}/*函數調用,用a,b,c代表3跟柱子,把盤子數,柱子代碼傳給函數*/
void move(int m, char p, char q, char r) //定義函數
{if (m==1)
{printf("[%d] move 1# from %c to %c\n", step, p,r);
step=step+1;}
else{move(m-1,p,r,q); //調用本身函數,進行遞歸 A
printf("[%d] move %d# from %c to %c\n",step, m,p,r);
step=step+1;
move(m-1,q,p,r); //再次調用 B
}
getch();}

這裡面的遞歸涉及一個漢諾塔的演算法問題,具體講明白的話有點麻煩,總體思路是假設盤子全在a柱上,想放到c上
第N個人就想要是有人搬動其他N-1個盤子到b,那他只要搬一次從a到c就可以,在讓那個人把N-1個盤子放到c上
第N-1那個人就想要是有人搬動其他N-2個盤子到c,他只要搬動一次從a到b就可以,在讓那個人把N-2個盤子放到b上
....
第1個人就直接把盤子從a到c

這樣形成遞歸
我在倆處調用標記了A,B,我寫出步躊,你看看.
假設3個盤子
A函數相當於雙重循環中的外層循環
B函數相當於雙重循環中的內層循環

1,主函數調用,p=a,q=b,r=c,m=3,運行A,調用本身(A第一次調用)傳入p,r,q(a,c,b) 注意調用函數中p,r,q排列
2,被調函數是用p,q,r的順序接收傳入的p,r,q.p=a,q=c,r=b,m=2,執行A,調用本身(A第二次調用) 調用傳入p,r,q(a,b,c)
3,p=a,q=b,r=c,m=1,執行if,輸出a->c,返回A第二次調用
4,本次函數中p=a,q=c,r=b,m=2,向下執行,輸出a->b,執行B,調用本身(B第一次調用),傳入q,p,r(c,a,b),m=1
5,p=c,q=a,r=b,m=1,執行if,輸出c->b,返回B第一次調用
6,向下執行,執行完畢,返回A第一次調用
7,本次函數中p=a,q=b,r=c,m=3,向下執行,輸出a->c,執行B,調用本身(B第一次調用),傳入q,p,r(b,a,c),m=2
8,p=b,q=a,r=c,m=2,執行A,調用本身(A'第一次調用,注意是B函數調用中再次調用A) 傳入p,r,q(b,c,a)
9,p=b,q=c,r=a,m=1,執行if,輸出b->a,返回A'第一次調用
10,本次函數中p=b,q=a,r=c,m=2向下執行,輸出b->c,執行B,調用本身(B'的第一次調用,注意是B函數中再次調用B) 傳入q,p,r(a,b,c),m=1
11,p=a,q=b,r=c,m=1,執行if,輸出a->c返回B'第一次調用
12,向下執行,執行完畢,返回B第一次調用
13,向下執行,執行完畢,返回主函數

仔細分析每次調用時當前變數p,q,r中所代表的a,b,c,每次調用時,p,q,r都是新的變數
我看了你的問題，估計你把調用函數中的p,q,r變數與被調函數中p,q,r變數搞混了

/*
4,向下執行,執行B,調用本身(B第一次調用),由於本次函數中p=a,q=c,r=b,m=2,先輸出a->b,再傳入q=c,p=a,r=b,m=1
這里不是[4] move 3# from a to c嗎
*/
注意調用傳入的順序是q,p,r,傳入的值是c,a,b的順序，被調函數中是拿p,q,r的順序在接收，所以被調函數中值的順序就該是p=c,q=a,r=b,執行if就輸出c->b

不要想太復雜了，q,p,r是變數，用來存儲值的，而他只是個局部變數，每次調用函數後給q,p,r新分配的內存地址不一樣。比如本次函數中q,p,r中放的值分別是q=c,p=a,r=b，當執行調用函數時，給被調函數傳入的是變數的值，也就是說實際上傳入的是c,a,b
在被調函數中，p,q,r是新的局部變數，他接收來自調用函數中的值，行參接收值的順序與實參傳入值的順序是相對應的，因為實參傳入的順序是c,a,b，在行參接收值時也以這樣的順序接收,而行參變數的順序是p,q,r,所以被調函數中p=c,q=a,r=b

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

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

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

10. 漢諾塔問題演算法

純手打，自己理解的。看的東就給分吧...
例如n=3
3，A,B,C
{ 2，A,C,B---------------->{1,A,B,C ============>A->C
move(A,B) ============>A->B
1,C,A,B ============>C->B
}
move(A,C) ============>A->C
2,B,A,C------------------>{1,B,C,A ============>B->A
move(B,C) ============>B->C
1,A,B,C ============>A->C
}
}