C語(yǔ)言遞歸之漢諾塔和青蛙跳臺(tái)階問(wèn)題
遞歸就是一個(gè)函數(shù)執(zhí)行過(guò)程中調(diào)用自己,在c語(yǔ)言中有很多關(guān)于遞歸的經(jīng)典問(wèn)題,例如:斐波那契數(shù)列問(wèn)題、漢諾塔問(wèn)題等,在研究遞歸問(wèn)題時(shí)我們要注意三點(diǎn):
1.遞歸的結(jié)束條件
2.遞歸在每次進(jìn)行過(guò)程中,都得離條件越來(lái)越近
3.相鄰兩次遞歸調(diào)用之間的關(guān)聯(lián)關(guān)系
漢諾塔問(wèn)題:
有三根桿子A, B, C。A桿上有N個(gè)(N > 1)穿孔圓盤(pán), 盤(pán)的尺寸由下到上依次變小.要求按下列規(guī)則將所有圓盤(pán)移至C桿:
1.每次只能移動(dòng)一個(gè)圓盤(pán);
2.大盤(pán)不能疊在小盤(pán)上面,可將圓盤(pán)臨時(shí)置于B桿, 也可將從A桿移出的圓盤(pán)重新移回A桿, 但都必須尊循上述兩條規(guī)則。求移動(dòng)的過(guò)程。
int step = 0; //設(shè)置全局變量step記錄步數(shù) void move(int i,char form,char to){ printf("第%d步,將第%d個(gè)盤(pán)子從%c移動(dòng)到%c\n", ++step,i,form, to); } void Hanio(int n,char a,char b,char c){ if (n == 0) { return; } Hanio(n - 1,a,c,b); //第n-1個(gè)A柱上的盤(pán)子通過(guò)C柱移動(dòng)到B柱 move(n, a, c); //將A柱上編號(hào)為n的盤(pán)子移動(dòng)到C柱 Hanio(n - 1, b, a, c); //再將B柱上的第n-1個(gè)盤(pán)子通過(guò)A柱移動(dòng)到C柱 } int main(){ int n; printf("請(qǐng)輸入漢諾塔中有多少個(gè)圓盤(pán):\n"); scanf("%d", &n); Hanio(n, 'A', 'B', 'C'); //將n個(gè)圓盤(pán)從A柱通過(guò)B柱移動(dòng)到C柱 system("pause"); return 0; }
運(yùn)行結(jié)果:
青蛙跳臺(tái)階問(wèn)題:
一只青蛙一次可以跳上 1 級(jí)臺(tái)階,也可以跳上2 級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。
當(dāng)n = 1,只有1中跳法;當(dāng)n = 2時(shí),有兩種跳法;當(dāng)n = 3 時(shí),有3種跳法;當(dāng)n = 4時(shí),有5種跳法;當(dāng)n = 5時(shí),有8種跳法??梢钥偨Y(jié)為f(n)=f(n-1)+f(n-2),本質(zhì)上與斐波那契數(shù)列相同。
int Frog(int n){ if (n <= 2 && n >= 0) { return n; } else if (n < 0) { printf("您的輸入錯(cuò)誤\n"); return n; }else { return Frog(n - 1) + Frog(n - 2); } } int main(){ int n; printf("請(qǐng)輸入有幾級(jí)臺(tái)階:\n"); scanf("%d", &n); int result = Frog(n); if(n >= 0){ printf("青蛙有%d種跳法\n", result); } system("pause"); return 0; }
運(yùn)行結(jié)果
到此這篇關(guān)于C語(yǔ)言遞歸之漢諾塔問(wèn)題和青蛙跳臺(tái)階問(wèn)題的文章就介紹到這了,更多相關(guān)C語(yǔ)言遞歸漢諾塔青蛙跳臺(tái)階內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
在C語(yǔ)言中調(diào)用C++做的動(dòng)態(tài)鏈接庫(kù)
如果你有一個(gè)c++做的動(dòng)態(tài)鏈接庫(kù).so文件,而你只有一些相關(guān)類(lèi)的聲明,那么你如何用c調(diào)用呢,別著急,本文通過(guò)一個(gè)小小的例子,讓你能夠很爽的搞定.2016-05-05SQL Server中的數(shù)據(jù)復(fù)制到的Access中的函數(shù)
SQL Server中的數(shù)據(jù)復(fù)制到的Access中,表的結(jié)構(gòu)相同 不要提用openrowset,因?yàn)锳ccess文件和SQL Server不在一臺(tái)機(jī)器上2008-11-11教你5分鐘輕松搞定內(nèi)存字節(jié)對(duì)齊
隨便google一下,人家就可以跟你解釋的,一大堆的道理,我們沒(méi)怎么多時(shí)間,討論為何要對(duì)齊.直入主題,怎么判斷內(nèi)存對(duì)齊規(guī)則,sizeof的結(jié)果怎么來(lái)的,請(qǐng)牢記以下3條原則2013-09-09C語(yǔ)言實(shí)現(xiàn)隨機(jī)發(fā)牌
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)隨機(jī)發(fā)牌,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-04-04C++實(shí)現(xiàn)自定義撤銷(xiāo)重做功能的示例代碼
在使用c++做界面開(kāi)發(fā)的時(shí)候,尤其是實(shí)現(xiàn)白板功能時(shí)需要自己實(shí)現(xiàn)一套撤銷(xiāo)重做功能.如果是qt則有QUndoable對(duì)象,可以直接拿來(lái)用。但是如果是使用gdi繪圖,則可能需要自己實(shí)現(xiàn)了。本文就來(lái)用C++實(shí)現(xiàn)自定義撤銷(xiāo)重做功能,需要的可以參考一下2022-12-12