1樓：匿名使用者
找本講資料結構或演算法的書，看一下遞迴那章。
c語言算漢諾塔，遞迴時的輸出是怎麼一步一步來的？如圖，求大神幫忙
2樓：匿名使用者
例如，n=3，三個柱子是a b c
那麼是這樣：
呼叫的層次已經用製表符分開
hanoi(3, a, b, c)=>
hanoi(2, a, c, b)=>
hanoi(1, a, b, c)
=>move(1, a, c)
move(a, b)
hanoi(1, c, a, b)
=>move(c, b)
move(a, c)
hanoi(2, b, a, c)=>
hanoi(1, b, c, a)=>
move(1, b, a)
move(b, c)
hanoi(1, a, b, c)=>
move(1, a, c)
求真正理解漢諾塔問題的程式設計大神回答一下，當n=3時，用c語言編寫的漢諾塔遞迴呼叫**的詳細執行過程
3樓：汗會欣
/* 漢諾塔 hannota.c */
#include
/*解法：
如果柱子標為abc，要由a搬至c，在只有乙個盤子時，就將它直接搬至c，當有兩個盤子，就將b當作輔助柱。
如果盤數超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：a->b、a->c、b->c這三個步驟，而被遮住的部份，其實就是進入程式的遞迴處理。
事實上，若有n個盤子，則移動完畢所需之次數為2^n-1；
所以當盤數為64時，則 64所需次數為：2^63=8446744073709551615為5.05390248594782e+16年，
也就是約5000世紀，如果對這數字沒什么概念，就假設每秒鐘搬乙個盤子好了，也要約5850億年左右
*/void hannota ( int n,char a,char b,char c )
else
}int main()
4樓：我愛上那女孩
一開始我接觸漢諾塔也是很不解，隨著**量的積累，現在很容易就看懂了，因此樓主主要還是對遞迴函式的理解不夠深刻，建議你多寫一些遞迴程式，熟練了自己就能理解。
圓盤邏輯移動過程+程式遞迴過程分析
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。
5樓：匿名使用者
理解漢諾塔問題，可以先拋開遞迴這件事，就問題本身來討論，先不要看程式。
三個柱子上，小的圓盤一定在大的上面。把a柱上的盤子n號盤子移到b柱上，分成兩步，1）把n之前的移走，2）把n號盤移到b柱上，3)把n之前的盤子移回來。
先把這個問題本身搞清楚，再來討論程式實現。
把n之前的盤子移走這個事，不是簡單的一次就可以移走的，這是乙個過程。
這個過程要借助c柱，
移動n-1個盤子的過程，與移動n個盤子的過程相比，除了數量少乙個，目標是a到c，沒有本質的不同，這也是使用遞迴的基礎。
把解決問題的過程弄明白了，再來看程式就比較容易了。
n=3，移動3個盤子
實際上我們如果手工去做，要這樣，
1# a-b
2# a-c
1# b-c
3# a-b，這時3#已經就位。
1# c-a
2# c-b
1# a-b
這是移動3個盤子，從a-b。
要移動第4個盤子，這時就可以做了 4# a-c，然後重複前面的過程，把3個盤子移動到過來。
不過剛才移動的3個盤子是a-b，現在則是b-c，但基本的過程是一樣的。
具體 的程式看百科看吧。
求c語言漢諾塔原始碼（遞迴和非遞迴都要）
6樓：匿名使用者
遞迴演算法是我前些天寫的，非遞迴是剛才找的，裡面含遞迴和非遞迴。
遞迴演算法：
#include
//遞迴求漢諾塔問題
void hanoi(int n, char a, char b, char c, int *time)
}//列印出每一步的路徑
void move(char a, char c)
int main(void)
非遞迴演算法：
#include
#define maxstack 10 /* 棧的最大深度 */
int c = 1; /* 乙個全域性變數，表示目前移動的步數 */
struct hanoi ;
void move(char x, int n, char y) /* 移動函式，表示把某個盤從某根針移動到另一根針 */
void hanoi(int n, char x, char y, char z) /* 漢諾塔的遞迴演算法 */
}void push(struct hanoi *p, int top, char x, char y, char z,int n)
void unreverse_hanoi(struct hanoi *p) /* 漢諾塔的非遞迴演算法 */
if (p[top].n == 1)
if (top >= 0) }}
int main(void)
7樓：券商論
#include
//漢諾塔x層塔從a塔整體搬到c塔，中間臨時b塔。
//x層塔是從大到小往上疊放。每次移動只能移動一層塔。並且在移動過程中必須保證小層在上邊
//借助b塔可以將x層塔全部從a搬到c上，並且符合要求（在移動過程中大的那塊在下邊，小的那塊在上邊）
int main()
//以下是tower函式的定義
//引數解析：x層塔放在a上，b是中間塔，c是目標塔。即x層塔要從a搬到c上。
//此函式實現x層塔從a整體轉移到c上。以及這個過程是怎麼搬的全部過程。
void tower(int x,char a,char b,char c)}
求漢諾塔遞迴全過程的演算法詳解圖，記得一定要是圖釋哦！！！
8樓：匿名使用者
**是什麼意思呀。
這個演算法 那麼簡單沒必要搞得那麼複雜吧。
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 ...+ 111111111111111111111111111111
這個問題就可以使用遞迴
原因你懂了吧。
至於爬樓梯問題，無限級分類 問題等一些遞迴問題，那不過時小菜一碟。
一句話：後一步驟依賴前一步驟並且二者聯絡具有規律性，運用遞迴必然成功。
c之漢諾塔問題，C 之漢諾塔問題
我沒研究過漢諾塔，但是c c 有很多時候是可以用陣列來解決問題而避免使用指標的。漢諾塔是乙個經典的遞迴問題 不需要用到指標的 遞迴思想就是 如果只有乙個盤子 那麼 把盤子直接移到目的柱 有兩個盤子 把最上面乙個移動到中間柱 把最下面的乙個移動到目的柱 然後把中間的移動到目的柱當規模為n的時候也就是這...
c語言求詳細過程
第一句 定義整形陣列 a 0 0 1,a 0 1 2,a 0 2 0 a 1 0 3,a 1 1 4,a 1 2 0 a 2 0 5,a 2 1 6,a 2 2 0 定義整形變數 i，j 未賦初值 s 0 首先，迴圈體確定 for i 1 i 3 i 一級迴圈 當i 1時，i 3成立，執行後續操作，...
c語言遞迴求階乘，c語言怎麼用遞迴呼叫函式的方法求n的階乘？
問明 舉例 用遞迴方法求n include int main int n int y printf input a integer number scanf d n y fac n printf d d n n,y return 0 int fac int n int f if n 0 printf...