文章目錄

• 跳臺階問題
• 遞歸方式
• 非遞歸方式
• C語言代碼實現(xiàn)
• 二、C++
• 總結(jié)

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

---

跳臺階問題

題目：一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。

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

---

遞歸方式

這種方法是最低級的做法，有很多重復(fù)計算，效率很低。利用數(shù)列的思想，直接寫出An的表達式，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ù)計算，提高效率

int FD_jump_floor(int n)//非遞歸
{int a1 = 1;//第一個數(shù)
	int a2 = 2;//第二個數(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語言代碼實現(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;//第一個數(shù)
	int b = 2;//第二個數(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("請輸入跳的臺階數(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é)

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

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

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

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

廣告

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