快捷導(dǎo)航

C語(yǔ)言遞歸之漢諾塔和青蛙跳臺(tái)階問(wèn)題

更新時(shí)間：2021年04月09日 14:48:37 作者：一只當(dāng)歸

這篇文章主要介紹了C語(yǔ)言遞歸之漢諾塔問(wèn)題和青蛙跳臺(tái)階問(wèn)題,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

遞歸就是一個(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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: