跳臺(tái)階問題-創(chuàng)新互聯(lián)

文章目錄
  • 跳臺(tái)階問題
  • 遞歸方式
  • 非遞歸方式
  • C語言代碼實(shí)現(xiàn)
  • 二、C++
  • 總結(jié)

創(chuàng)新互聯(lián)公司專注骨干網(wǎng)絡(luò)服務(wù)器租用十余年，服務(wù)更有保障！服務(wù)器租用，BGP機(jī)房服務(wù)器托管 成都服務(wù)器租用，成都服務(wù)器托管，骨干網(wǎng)絡(luò)帶寬，享受低延遲，高速訪問。靈活、實(shí)現(xiàn)低成本的共享或公網(wǎng)數(shù)據(jù)中心高速帶寬的專屬高性能服務(wù)器。
跳臺(tái)階問題

題目：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

分析：青蛙每次只有一階或者兩階兩種跳法，那么：
假設(shè)第一次跳的是一階，那么剩下的n-1個(gè)臺(tái)階，跳法是f(n-1)
假設(shè)第一次跳的是兩階，那么剩下的n-2個(gè)臺(tái)階，跳法是f(n-2)
由上面兩種假設(shè)可得：f(n) = f(n-1) + f(n-2)
由實(shí)際情況可知：f(1) = 1，f(2) = 2
最終得出的是一個(gè)斐波那契數(shù)列：
| 1，n = 1
f(n) = | 2, n = 2
| f(n-1) + f(n -2), n >2

遞歸方式

這種方法是最低級(jí)的做法，有很多重復(fù)計(jì)算，效率很低。利用數(shù)列的思想，直接寫出An的表達(dá)式，An = An-1 +An-2

int D_jump_floor(int n)//遞歸
{if (n<= 2)
	{return n;
	}
	else
	{return D_jump_floor(n - 2) + D_jump_floor(n - 1);
	}
}
非遞歸方式

根據(jù)斐波那契數(shù)列推導(dǎo)，從下往上算，避免重復(fù)計(jì)算，提高效率

int FD_jump_floor(int n)//非遞歸
{int a1 = 1;//第一個(gè)數(shù)
	int a2 = 2;//第二個(gè)數(shù)
	int sum;
	if(n ==1)
	{sum =1;
	}
	else if(n==2)
	{sum = 2;
	}
	else 
	{for(int i = 3;i<=n;i++)
    	{	sum = a1 + a2;
	    	a1 = a2;
	    	a2 = sum;
		}
		return sum;
	}

}
C語言代碼實(shí)現(xiàn)
#include#includeint D_jump_floor(int n)//遞歸
{if (n<= 2)
	{return n;
	}
	else
	{return D_jump_floor(n - 2) + D_jump_floor(n - 1);
	}
}

int FD_jump_floor(int n)//非遞歸
{int a = 1;//第一個(gè)數(shù)
	int b = 2;//第二個(gè)數(shù)
	int c = a;//把c賦值為a
	while (n >2)
	{c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{int n = 0;
	printf("請(qǐng)輸入跳的臺(tái)階數(shù)：");
	scanf("%d", &n);
	int ret1 = D_jump_floor(n);
	int ret2 = FD_jump_floor(n);
	printf("%d\n", ret1);
	printf("%d\n", ret2);
	system("pause");
	return 0;
}
二、C++
總結(jié)

遞歸比較無腦，但是時(shí)間復(fù)雜度長

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：跳臺(tái)階問題-創(chuàng)新互聯(lián)
分享URL：http://muchs.cn/article42/dpehhc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)公司、企業(yè)建站、虛擬主機(jī)、微信小程序、品牌網(wǎng)站設(shè)計(jì)

廣告

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

網(wǎng)站托管運(yùn)營