C語言遞歸之漢諾塔和青蛙跳臺階問題

Posted on by

遞歸就是一個函數執行過程中調用自己，在c語言中有很多關於遞歸的經典問題，例如：斐波那契數列問題、漢諾塔問題等，在研究遞歸問題時我們要註意三點：
1.遞歸的結束條件
2.遞歸在每次進行過程中，都得離條件越來越近
3.相鄰兩次遞歸調用之間的關聯關系

漢諾塔問題：

有三根桿子A, B, C。A桿上有N個(N > 1)穿孔圓盤, 盤的尺寸由下到上依次變小.要求按下列規則將所有圓盤移至C桿：
1.每次隻能移動一個圓盤；
2.大盤不能疊在小盤上面，可將圓盤臨時置於B桿, 也可將從A桿移出的圓盤重新移回A桿, 但都必須尊循上述兩條規則。求移動的過程。

int step = 0; //設置全局變量step記錄步數
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;
}

運行結果：

在這裡插入圖片描述

青蛙跳臺階問題：

一隻青蛙一次可以跳上 1 級臺階，也可以跳上2 級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
當n = 1，隻有1中跳法；當n = 2時，有兩種跳法；當n = 3 時，有3種跳法；當n = 4時，有5種跳法；當n = 5時，有8種跳法。可以總結為f(n)=f(n-1)+f(n-2)，本質上與斐波那契數列相同。

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;
}

運行結果

在這裡插入圖片描述

到此這篇關於C語言遞歸之漢諾塔問題和青蛙跳臺階問題的文章就介紹到這瞭,更多相關C語言遞歸漢諾塔青蛙跳臺階內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

    None Found