漢諾塔遞歸演算法c語言

㈠ c語言漢諾塔程序

將以下內容全部復制到新建的源文件中：（本人自己寫的，因為你那課本上的代碼，沒解釋，書寫不規范，很難理解清楚，所以我直接新寫了一個完整的代碼，附帶詳細說明）
#include <stdio.h>
//漢諾塔x層塔從A塔整體搬到C塔，中間臨時B塔。
//x層塔是從大到小往上疊放。每次移動只能移動一層塔。並且在移動過程中必須保證小層在上邊
//藉助B塔可以將x層塔全部從A搬到C上，並且符合要求（在移動過程中大的那塊在下邊，小的那塊在上邊）
int main()
{
void tower(int x,char a,char b,char c); //聲明函數
int x=5,a='A',b='B',c='C'; //x表示有5層塔，具體要多少層自己修改這個值。abc分別表示ABC塔。

tower(x,a,b,c); //x層塔從a移動到c的全過程，主程序只有這條有效語句

return 0;
}

//以下是tower函數的定義
//參數解析：x層塔放在a上，b是中間塔，c是目標塔。即x層塔要從a搬到c上。
//此函數實現x層塔從a整體轉移到c上。以及這個過程是怎麼搬的全部過程。
void tower(int x,char a,char b,char c)
{
if(x==1)printf("將%d從%c放到%c\n",x,a,c); //只有1層塔時，直接從a搬到c上。
else //不止1層塔，則先將x-1層塔從a按照規律搬到b上，再將最後一塊從a搬到c上，最後再將b上的x-1層塔按照規律搬到c上。
{
tower(x-1,a,c,b); //先將x-1層塔從a按照規律搬到b上，注意參數b放在最後，因為放在最後的參數是准備搬過去的目標塔。
printf("將%d從%c放到%c\n",x,a,c); //將最後一塊從a搬到c上
tower(x-1,b,a,c); //最後再將b上的x-1層塔按照規律搬到c上，注意參數b放在開頭，因為x-1層是要從b上搬過去的。
}
}

㈡ c語言用遞歸實現漢諾塔

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

#include<stdio.h>
voidmove(charx,chary)
{
printf("%c-->%c
",x,y);
}
//hannuota函數的作用：把n個圓盤從one柱子藉助two柱子放到three柱子
voidhannuota(intn,charone,chartwo,charthree)
{
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柱子)
}
}
intmain()
{
intm;
printf("inputthenumberofdiskes:");
scanf("%d",&m);
printf("Thesteptomove%ddiskes:
",m);
hannuota(m,'A','B','C');
return0;
}

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

㈣ 求C語言漢諾塔源碼（遞歸和非遞歸都要）

遞歸演算法是我前些天寫的，非遞歸是剛才找的，裡面含遞歸和非遞歸。\x0d\x0a遞歸演算法：\x0d\x0a#include \x0d\x0a//遞歸求漢諾塔問題\x0d\x0avoid hanoi(int n, char A, char B, char C, int *time)\x0d\x0a{\x0d\x0aif (n>=1)\x0d\x0a{\x0d\x0a hanoi(n-1, A, C, B, time);\x0d\x0a move(A, C);\x0d\x0a (*time)++;\x0d\x0a hanoi(n-1, B, A, C, time);\x0d\x0a }\x0d\x0a}\x0d\x0a//列印出每一步的路徑\x0d\x0avoid move(char a, char c)\x0d\x0a{\x0d\x0aprintf(" %c-->%c\n", a, c);\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint n, time = 0;;\x0d\x0aprintf("請輸入漢諾塔的盤數:");\x0d\x0ascanf("%d", &n);\x0d\x0aprintf("%d個盤的漢諾塔移動方法是：", n);\x0d\x0aprintf("\n");\x0d\x0ahanoi(n, 'A', 'B', 'C', &time);\x0d\x0aprintf("移動了%d次\n", time);\x0d\x0asystem("pause");\x0d\x0areturn 0;\x0d\x0a}\x0d\x0a\x0d\x0a非遞歸演算法：\x0d\x0a#include \x0d\x0a\x0d\x0a#define MAXSTACK 10 /* 棧的最大深度 */\x0d\x0a\x0d\x0aint c = 1; /* 一個全局變數，表示目前移動的步數 */\x0d\x0a\x0d\x0astruct hanoi { /* 存儲漢諾塔的結構，包括盤的數目和三個盤的名稱 */\x0d\x0aint n;\x0d\x0achar x, y, z;\x0d\x0a};\x0d\x0a\x0d\x0avoid move(char x, int n, char y) /* 移動函數，表示把某個盤從某根針移動到另一根針 */\x0d\x0a{\x0d\x0aprintf("%d-> %d from %c -> %c\n", c++, n, x, y);\x0d\x0a}\x0d\x0a\x0d\x0avoid hanoi(int n, char x, char y, char z) /* 漢諾塔的遞歸演算法 */\x0d\x0a{\x0d\x0aif (1 == n)\x0d\x0amove(x, 1, z);\x0d\x0aelse {\x0d\x0ahanoi(n - 1, x, z, y);\x0d\x0amove(x, n, z);\x0d\x0ahanoi(n - 1, y, x, z);\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0avoid push(struct hanoi *p, int top, char x, char y, char z,int n)\x0d\x0a{\x0d\x0ap[top+1].n = n - 1;\x0d\x0ap[top+1].x = x;\x0d\x0ap[top+1].y = y;\x0d\x0ap[top+1].z = z;\x0d\x0a}\x0d\x0a\x0d\x0avoid unreverse_hanoi(struct hanoi *p) /* 漢諾塔的非遞歸演算法 */\x0d\x0a{\x0d\x0aint top = 0;\x0d\x0a\x0d\x0awhile (top >= 0) {\x0d\x0awhile (p[top].n > 1) { /* 向左走到盡頭 */\x0d\x0a push(p, top, p[top].x, p[top].z, p[top].y, p[top].n);\x0d\x0a top++;\x0d\x0a}\x0d\x0aif (p[top].n == 1) { /* 葉子結點 */\x0d\x0a move(p[top].x, 1, p[top].z);\x0d\x0a top--;\x0d\x0a}\x0d\x0aif (top >= 0) { /* 向右走一步 */\x0d\x0a move(p[top].x, p[top].n, p[top].z);\x0d\x0a top--;\x0d\x0a push(p, top, p[top+1].y, p[top+1].x, p[top+1].z, p[top+1].n);\x0d\x0a top++;\x0d\x0a}\x0d\x0a}\x0d\x0a}\x0d\x0a\x0d\x0aint main(void)\x0d\x0a{\x0d\x0aint i;\x0d\x0aprintf("遞歸:\n");\x0d\x0ahanoi(3, 'x', 'y', 'z');\x0d\x0aprintf("非遞歸:\n");\x0d\x0astruct hanoi p[MAXSTACK];\x0d\x0ac = 1;\x0d\x0ap[0].n = 3;\x0d\x0ap[0].x = 'x', p[0].y = 'y', p[0].z = 'z';\x0d\x0aunreverse_hanoi(p);\x0d\x0a\x0d\x0areturn 0;\x0d\x0a}

㈤ 用C語言代碼來編寫含漢諾塔問題,利用堆棧來實現.求代碼

演算法思想
對於漢諾塔問題，當只移動一個圓盤時，直接將圓盤從 A 針移動到 C 針。若移動的圓盤為 n(n>1)，則分成幾步走：把 (n-1) 個圓盤從 A 針移動到 B 針（藉助 C 針）；A 針上的最後一個圓盤移動到 C 針；B 針上的 (n-1) 個圓盤移動到 C 針（藉助 A 針）。每做一遍，移動的圓盤少一個，逐次遞減，最後當 n 為 1 時，完成整個移動過程。
因此，解決漢諾塔問題可設計一個遞歸函數，利用遞歸實現圓盤的整個移動過程，問題的解決過程是對實際操作的模擬。
程序代碼
#include <stdio.h>
int main()
{
int hanoi(int,char,char,char);
int n,counter;
printf("Input the number of diskes：");
scanf("%d",&n);
printf("\n");
counter=hanoi(n,'A','B','C');
return 0;
}
int hanoi(int n,char x,char y,char z)
{
int move(char,int,char);
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
return 0;
}
int move(char getone,int n,char putone)
{
static int k=1;
printf("%2d:%3d # %c---%c\n",k,n,getone,putone);
if(k++%3==0)
printf("\n");
return 0;
}

㈥ 漢諾塔c語言怎麼解釋 不懂每步具體說明

漢諾塔的一個經典案例就是用遞歸法解決問題
A、B、C三根柱子上放盤子
開始盤子都在A上
盤子必須按照小上打下的順序放置
要求每次只能移動一個盤子
要將A上的盤子都移到B上。
分析：
設有n個盤子在A上，當n=1時
只要將盤子從A->B
即可
當n>1時此問題可分解為以下步驟
1>
把n-1個盤子從柱子A移到C
2>
把第n個盤子從A移到B
3>
把n-1個盤子從C移到B
這是具體的演算法
如果你不懂遞歸的話
這個程序就不好懂。
我給出一個遞歸的演算法實現，你看看
#include
"stdio.h"
int
Hanoi(char
x,char
y,char
z,int
n)
{
if(n==1)
//對應第一種可能
{
printf("1:
%c
->%c\n",x,y);
}
else
//對應第二種可能
{
Hanoi(x,z,y,n-1);
//第二種可能的第一中移動方法
printf("%d:
%c
->%c\n",n,x,y);
Hanoi(z,y,x,n-1);
//第二種可能的第二種移動方法
}
return
0;
}
int
main()
{
int
n;
printf("請輸入漢諾塔的高度：");
scanf("%d",&n);
printf("移動方案是：(系數代表第幾個盤子
從上往下計數)\n");
Hanoi('A','B','C',n);
return
0;
}
VC
6．0下編譯成功！
這是典型的遞歸用法。
你看這個程序應該跟明確些。

㈦ 如何做一個C語言編程的漢諾塔游戲

#includex0dx0a void move(char x,char y)x0dx0a {x0dx0a printf("%c-->%c\n",x,y);x0dx0a }x0dx0a void hanoi(int n,char one ,char two,char three)x0dx0a {x0dx0a if(n==1) move(one,three);x0dx0a elsex0dx0a {x0dx0a hanoi(n-1,one,three,two);x0dx0a move(one,three);x0dx0a hanoi(n-1,two,one,three);x0dx0a }x0dx0a }x0dx0a main()x0dx0a {x0dx0a int m;x0dx0a printf("input the number of disks:");x0dx0a scanf("%d",&m);x0dx0a printf("the step to moving %3d diskes:\n",m);x0dx0a hanoi(m,'A','B','C');x0dx0a }x0dx0a演算法介紹：x0dx0a 其實演算法非常簡單，當盤子的個數為n時，移動的次數應等於2^n _ 1（有興趣的可以自己證明試試看）。後來一位美國學者發現一種出人意料的簡單方法，只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上，根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；x0dx0a 若n為奇數，按順時針方向依次擺放 A C B。x0dx0a （1）按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。x0dx0a （2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤。這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。x0dx0a （3）反復進行（1）（2）操作，最後就能按規定完成漢諾塔的移動。x0dx0a 所以結果非常簡單，就是按照移動規則向一個方向移動金片：x0dx0a 如3階漢諾塔的移動：A→C,A→B,C→B,A→C,B→A,B→C,A→Cx0dx0a 漢諾塔問題也是程序設計中的經典遞歸問題，下面我們將給出遞歸和非遞歸的不同實現源代碼。