C語言漢諾塔

要看懂遞歸程序，往往應(yīng)先從最簡(jiǎn)單情況看起。

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比海西網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式海西網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋海西地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。

先看hanoi(1, one, two, three)的情況。這時(shí)直接將one柱上的一個(gè)盤子搬到three柱上。注意，這里one柱或three柱到底是A、B還是C并不重要，要記住的是函數(shù)第二個(gè)參數(shù)代表的柱上的一個(gè)盤被搬到第四個(gè)參數(shù)代表的柱上。為方便，將這個(gè)動(dòng)作記為：

one =》three

再看hanoi(2, one, two, three)的情況?？紤]到hanoi(1)的情況已經(jīng)分析過了，可知這時(shí)實(shí)際上將產(chǎn)生三個(gè)動(dòng)作，分別是：

one =》two

one =》three

two =》three

很顯然，這實(shí)際上相當(dāng)于將one柱上的兩個(gè)盤直接搬到three柱上。

再看hanoi(3, one, two, three)的情況。分析

hanoi(2, one , three, two)

one =》three

hanoi(2, two, one, three)

即：先將one柱上的兩個(gè)盤搬到two柱上，再將one柱上的一個(gè)盤搬到three柱上，最后再將two柱上的兩個(gè)盤搬到three柱上。這不就等于將one柱上的三個(gè)盤直接搬到three柱上嗎？

運(yùn)用歸納法可知，對(duì)任意n，

hanoi(n-1, one , three, two)

one =》three

hanoi(n-1, two, one, three)

就是先將one柱上的n-1個(gè)盤搬到two柱上，再將one柱上的一個(gè)盤搬到three柱上，最后再將two柱上的n-1個(gè)盤搬到three柱上。這就是我們所需要的結(jié)果！

C語言漢諾塔程序

將以下內(nèi)容全部復(fù)制到新建的源文件中：（本人自己寫的，因?yàn)槟隳钦n本上的代碼，沒解釋，書寫不規(guī)范，很難理解清楚，所以我直接新寫了一個(gè)完整的代碼，附帶詳細(xì)說明）

#include stdio.h

//漢諾塔x層塔從A塔整體搬到C塔，中間臨時(shí)B塔。

//x層塔是從大到小往上疊放。每次移動(dòng)只能移動(dòng)一層塔。并且在移動(dòng)過程中必須保證小層在上邊

//借助B塔可以將x層塔全部從A搬到C上，并且符合要求（在移動(dòng)過程中大的那塊在下邊，小的那塊在上邊）

int main()

{

void tower(int x,char a,char b,char c); //聲明函數(shù)

int x=5,a='A',b='B',c='C'; //x表示有5層塔，具體要多少層自己修改這個(gè)值。abc分別表示ABC塔。

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

return 0;

}

//以下是tower函數(shù)的定義

//參數(shù)解析：x層塔放在a上，b是中間塔，c是目標(biāo)塔。即x層塔要從a搬到c上。

//此函數(shù)實(shí)現(xiàn)x層塔從a整體轉(zhuǎn)移到c上。以及這個(gè)過程是怎么搬的全部過程。

void tower(int x,char a,char b,char c)

{

if(x==1)printf("將%d從%c放到%c\n",x,a,c); //只有1層塔時(shí)，直接從a搬到c上。

else //不止1層塔，則先將x-1層塔從a按照規(guī)律搬到b上，再將最后一塊從a搬到c上，最后再將b上的x-1層塔按照規(guī)律搬到c上。

{

tower(x-1,a,c,b); //先將x-1層塔從a按照規(guī)律搬到b上，注意參數(shù)b放在最后，因?yàn)榉旁谧詈蟮膮?shù)是準(zhǔn)備搬過去的目標(biāo)塔。

printf("將%d從%c放到%c\n",x,a,c); //將最后一塊從a搬到c上

tower(x-1,b,a,c); //最后再將b上的x-1層塔按照規(guī)律搬到c上，注意參數(shù)b放在開頭，因?yàn)閤-1層是要從b上搬過去的。

}

}

c語言用遞歸實(shí)現(xiàn)漢諾塔

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

#include?stdio.h

void?move(char?x,char?y)

{

printf("%c--%c\n",x,y);

}

//hannuota函數(shù)的作用：把n個(gè)圓盤從one柱子借助two柱子放到three柱子?

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

{

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

move(one,three);//直接移動(dòng)即可?

else

{

hannuota(n-1,one,three,two);//先把one柱子上的n-1個(gè)圓盤借助three柱子移動(dòng)到柱子two?

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

//由于原來one柱子上的n-1個(gè)圓盤已經(jīng)移動(dòng)到了two柱子上，因此不會(huì)有圓盤擋住n圓盤出來?

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

//最后再把那n-1個(gè)圓盤從two柱子借助one柱子移動(dòng)到three柱子

//(上面第一句話hannuota(n-1,one,three,two)已經(jīng)移動(dòng)到了two柱子，因此這里是從two柱子移動(dòng)到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;

}

用C語言代碼來編寫含漢諾塔問題,利用堆棧來實(shí)現(xiàn).求代碼

算法思想

對(duì)于漢諾塔問題，當(dāng)只移動(dòng)一個(gè)圓盤時(shí)，直接將圓盤從 A 針移動(dòng)到 C 針。若移動(dòng)的圓盤為 n(n1)，則分成幾步走：把 (n-1) 個(gè)圓盤從 A 針移動(dòng)到 B 針（借助 C 針）；A 針上的最后一個(gè)圓盤移動(dòng)到 C 針；B 針上的 (n-1) 個(gè)圓盤移動(dòng)到 C 針（借助 A 針）。每做一遍，移動(dòng)的圓盤少一個(gè)，逐次遞減，最后當(dāng) n 為 1 時(shí)，完成整個(gè)移動(dòng)過程。

因此，解決漢諾塔問題可設(shè)計(jì)一個(gè)遞歸函數(shù)，利用遞歸實(shí)現(xiàn)圓盤的整個(gè)移動(dòng)過程，問題的解決過程是對(duì)實(shí)際操作的模擬。

程序代碼

#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語言漢諾塔

我先回答最后一個(gè)問題，move只有輸出是因?yàn)椋覀儽緛砭筒恍枰娴呐矂?dòng)它，也沒辦法真的挪動(dòng)它，只要打印挪動(dòng)方法就可以了

n=3的情況中

我們要做的是把三個(gè)盤子挪到第三個(gè)柱子

hanoi函數(shù)的功能是，把最小的n個(gè)盤子從one柱挪到three柱

步驟1 首先把前n-1個(gè)盤子從one柱挪到two柱，這樣就可以最大盤上面就什么都沒有了

步驟2 直接把最大的盤子挪到three了

步驟3 然后再把那n-1個(gè)從two柱挪到one柱

為了實(shí)現(xiàn)步驟1，也是一樣的方法

我們把前兩個(gè)盤子挪到two,需要下面三個(gè)步驟

步驟1 首先把前n-2個(gè)盤子從one柱挪到three柱，這樣就可以最大盤上面就什么都沒有了

步驟2 直接把最大的盤子挪到two了

步驟3 然后再把那n-2個(gè)從three柱挪到two柱

原先的步驟3也是一樣的道理

理解遞歸，并不需要完全搞清楚執(zhí)行順序，只需要把遞歸調(diào)用的關(guān)系找到就行了

另外，你可以在hanoi開始就把n,one,two,three打印出來，可以很清晰的看到執(zhí)行過程

當(dāng)前題目：c語言編寫漢諾塔函數(shù) 漢諾塔循環(huán)求解C語言
文章URL：http://jinyejixie.com/article22/hejjjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、電子商務(wù)、網(wǎng)站改版、網(wǎng)站建設(shè)、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)