漢諾塔c語言遞歸流程圖,漢諾塔c程序的遞歸原理

本文目錄一覽：

• 1、求漢諾塔遞歸全過程的演算法詳解圖，記得一定要是圖釋哦！！！
• 2、c語言用遞歸實現漢諾塔
• 3、漢諾塔流程圖
• 4、求C漢諾塔遞歸過程詳解
• 5、漢諾塔n=4(4個盤)c語言遞歸編程代碼
• 6、漢諾塔問題的遞歸演算法流程圖

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

圖解是什麼意思呀。

這個演算法 那麼簡單沒必要搞得那麼複雜吧。

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語言用遞歸實現漢諾塔

見代碼注釋，還有不懂可以問。

#include stdio.h

void move(char x,char y)

{

    printf(“%c–%c\n”,x,y);

}

//hannuota函數的作用：把n個圓盤從one柱子藉助two柱子放到three柱子 

void hannuota(int n,char one,char two,char three)

{

    if(n==1)//如果只有一個柱子 

        move(one,three);//直接移動即可 

    else

    {

        hannuota(n-1,one,three,two);//先把one柱子上的n-1個圓盤藉助three柱子移動到柱子two 

        move(one,three);//把第一個柱子的剩下那一個(第n個)移動到第三個柱子

//由於原來one柱子上的n-1個圓盤已經移動到了two柱子上，因此不會有圓盤擋住n圓盤出來 

        hannuota(n-1,two,one,three);

        //最後再把那n-1個圓盤從two柱子藉助one柱子移動到three柱子

//(上面第一句話hannuota(n-1,one,three,two)已經移動到了two柱子，因此這裡是從two柱子移動到three柱子) 

    }

}

int main()

{

    int m;

    printf(“input the number of diskes:”);

    scanf(“%d”,m);

    printf(“The step to move %d diskes:\n”,m);

    hannuota(m,’A’,’B’,’C’);

    return 0;

}

漢諾塔流程圖

你好！

漢諾塔流程圖：

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();}

遞歸其實是嵌套調用,

所謂嵌套調用,就是在一個函數里調用另一個函數,

main函數不能被調用的,

所以遞歸就是有限次的嵌套調用本身函數

每次調用,系統都會重新分配內存,

返回時就返回上次調用他的那塊內存中的調用函數處,

這樣理解應該很簡單了

漢諾塔流程圖解析：

這裡面的遞歸涉及一個漢諾塔的演算法問題,具體講明白的話有點麻煩,總體思路是假設盤子全在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

補充：流程圖步驟畫了好久額，有什麼疑問發我郵箱315946173@qq.com

求C漢諾塔遞歸過程詳解

解決漢諾塔的基本思想是先把n個盤子除了最下面的盤子以外的所有盤子從第一根柱子（初始柱子）移動到中間那個柱子上（輔助柱子），然後把最下面的盤子移動到最後一根柱子上（目標柱子）。最後把剩下的盤子移動到目標柱子上。這樣，然而，完成第一步和第三步也同樣是一個移動n-1個盤子的漢諾塔問題。於是，遞歸調用在這裡不可避免。程序你已經寫的很清楚，給你解釋一下。現把你的程序畫上行以便說明。

1

#include

“stdio.h”

2

main()

3

{void

hanoi(int,char,char,char);

4

int

m;

5

printf(“input

the

number

of

disks:”);

6

scanf(“%d”,m);

7

printf(“The

step

to

moving

%d

disks:\n”,m);

8

hanoi(m,’A’,’B’,’C’);

9

}

10

void

hanoi(int

n,char

a,char

b,char

c)

11

{//void

move(char,char);

12

if(n==1)

move(a,c);

13

else

14

{hanoi(n-1,a,c,b);

15

move(a,c);

16

hanoi(n-1,b,a,c);

17

}

18

}

19

void

move(char

x,char

y)

20

{printf(“%c–%c\n”,x,y);

21

}

當m=4時，程序走到第8行，調用函數hanoi(int

n,char

a,char

b,char

c)。此時，實參把值傳遞給了形參，於是此時，n=4,a=A,b=B,c=C。我把第11行的void

move(char,char);

注釋掉了，應該知道這一句的意思。因為這一行雖然可以讓程序更加完整，但是解釋的時候加上它會很麻煩。程序走到第12行，因為此時n=4,而不等於1，程序直接走第13行。於是調用第14行的hanoi(n-1,a,c,b)。這是一個遞歸調用。此時，n=3,a=A,c=B,b=C。要清楚，A，B，C代表的意義。A代表初始柱子，B代表輔助柱子，C代表目標柱子。而a代表第一根柱子,b代表第二根柱子,c代表第三根柱子。這是不一樣的。程序繼續走，到12行時n依然不等於1。走到14行調用hanoi(n-1,a,c,b)。此時，n=2,a=A,c=C,b=B。程序再走，到12行時n依然不等於1，走到14行調用hanoi(n-1,a,c,b)。此時，n=1,a=A,c=B,b=C。程序走到12行時發現n=1,程序開始走15行。調用move(char

x,char

y)到20行時輸出A–B。調用結束，回到上一個調用即n=2,a=A,c=C,b=B。程序回到第15行，輸出

A–B。再走第16行，調用hanoi(n-1,b,a,c)。此時n=1,b=A,a=B,c=C。程序回到12行再調用19行輸出B–C。調用結束，回到上一個調用n=3,a=A,c=B,b=C。程序走到15行，輸出A–C，這時，第一根柱子上有一個盤子，第二根柱子上有一個盤子，第三根柱子上有兩個盤子。再調用16行就可以完成把第三根柱子里的所有盤子都移動到第二根柱子上。這樣。我們就完成了整體目標的第一步。把n個盤子除了最下面的盤子以外的所有盤子從第一根柱子（初始柱子）移動到中間那個柱子上（輔助柱子），調用完成後程序回到15行，此時n=3,a=A,c=B,b=C。15行時輸出A–C，這時便完成了整體目標的第二步，最下面的盤子移動到最後一根柱子上（目標柱子）。再根據程序走到16行，經過跟14行類似的一系列的遞歸調用，我們就可以完成最終目標了。

漢諾塔n=4(4個盤)c語言遞歸編程代碼

/****************************

漢諾塔的演算法就3個步驟：

第一，把a上的n-1個盤通過c移動到b。

第二，把a上的最下面的盤移到c。a成了空的。

第三，因為n-1個盤全在b上了，所以把b當做a.

重複以上步驟就好了。所以演算法看起來就簡單多了。

******************************/

#includestdio.h

static int m=0;

void move(int n,char a,char b,char c)

{

    if(n==1)

      { 

        m++;

        printf(“第 %d 次移動:\n”, m );

        printf(“\t%c-%c\n”,a,c);    //當n只有1個的時候直接從a移動到c

        }

    else

    {

        move(n-1,a,c,b);                    //第n-1個要從a通過c移動到b

        m++;

        printf(“第 %d 次移動:\n”, m );

        printf(“\t%c-%c\n”,a,c);

        move(n-1,b,a,c);            //n-1個移動過來之後b變開始盤，b通過a移動到c，這邊很難理解

    }

}

int main()

{

    int n=4;

    //printf(“請輸入要移動的塊數：”);

   // scanf(“%d”,n);

    move(n,’a’,’b’,’c’);

    return 0;

}

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

#include stdio.h

void hano(int n,char a,char b,char c)

{

if(n==1)

printf(“\t將%d個碟片從%c移動到%c\n”,n,a,c);

else {

hano(n-1,a,c,b);

printf(“\t將第%d個碟片從%c移動到%c\n”,n,a,c);

hano(n-1,b,a,c);

}

}

main()

{

int n;

printf(“輸入將要移動多少個盤子n:”);

scanf(“%d”,n);

printf(“遞歸結果：\n”);

hano(n,’x’,’y’,’z’);

}