C語言遞歸之漢諾塔和青蛙跳臺階問題
遞歸就是一個函數(shù)執(zhí)行過程中調(diào)用自己,在c語言中有很多關(guān)于遞歸的經(jīng)典問題,例如:斐波那契數(shù)列問題、漢諾塔問題等,在研究遞歸問題時我們要注意三點:
1.遞歸的結(jié)束條件
2.遞歸在每次進行過程中,都得離條件越來越近
3.相鄰兩次遞歸調(diào)用之間的關(guān)聯(lián)關(guān)系
漢諾塔問題:
有三根桿子A, B, C。A桿上有N個(N > 1)穿孔圓盤, 盤的尺寸由下到上依次變小.要求按下列規(guī)則將所有圓盤移至C桿:
1.每次只能移動一個圓盤;
2.大盤不能疊在小盤上面,可將圓盤臨時置于B桿, 也可將從A桿移出的圓盤重新移回A桿, 但都必須尊循上述兩條規(guī)則。求移動的過程。
int step = 0; //設(shè)置全局變量step記錄步數(shù) void move(int i,char form,char to){ printf("第%d步,將第%d個盤子從%c移動到%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個A柱上的盤子通過C柱移動到B柱 move(n, a, c); //將A柱上編號為n的盤子移動到C柱 Hanio(n - 1, b, a, c); //再將B柱上的第n-1個盤子通過A柱移動到C柱 } int main(){ int n; printf("請輸入漢諾塔中有多少個圓盤:\n"); scanf("%d", &n); Hanio(n, 'A', 'B', 'C'); //將n個圓盤從A柱通過B柱移動到C柱 system("pause"); return 0; }
運行結(jié)果:
青蛙跳臺階問題:
一只青蛙一次可以跳上 1 級臺階,也可以跳上2 級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
當n = 1,只有1中跳法;當n = 2時,有兩種跳法;當n = 3 時,有3種跳法;當n = 4時,有5種跳法;當n = 5時,有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("您的輸入錯誤\n"); return n; }else { return Frog(n - 1) + Frog(n - 2); } } int main(){ int n; printf("請輸入有幾級臺階:\n"); scanf("%d", &n); int result = Frog(n); if(n >= 0){ printf("青蛙有%d種跳法\n", result); } system("pause"); return 0; }
運行結(jié)果
到此這篇關(guān)于C語言遞歸之漢諾塔問題和青蛙跳臺階問題的文章就介紹到這了,更多相關(guān)C語言遞歸漢諾塔青蛙跳臺階內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SQL Server中的數(shù)據(jù)復(fù)制到的Access中的函數(shù)
SQL Server中的數(shù)據(jù)復(fù)制到的Access中,表的結(jié)構(gòu)相同 不要提用openrowset,因為Access文件和SQL Server不在一臺機器上2008-11-11