當前位置:網站首頁>青蛙跳臺階問題(和進階)

青蛙跳臺階問題(和進階)

2022-01-27 02:20:33 m0_62616069

一只青蛙一次可以最多跳2級臺階,求青蛙跳上n級臺階有多種跳法?

當 n=1時,青蛙只有一種跳法;

當n=2時,青蛙有兩種跳法;

當n=3時,有三種跳法,我們可以先跳一級再跳1級;先跳1級,再跳1級;一級一級的跳;共三種跳法;

當n=4時,我們可以先跳一級臺階,再跳3級臺階;還有一種跳法是先跳2級臺階,再跳2級臺階;因為跳三級臺階有三種跳法,所以2+3=5;

當n=5時,我們可以先跳1級臺階,再跳4級臺階;先跳2級臺階,再跳3級臺階;總跳法為3級臺階+4級臺階的跳法;

當n=m的時候,總跳法為(n-1)級臺階的跳法+(n-2)級臺階的跳法;

得到公式:f(n)=f(n-1)+f(n-2)

代碼實現:

int Jump(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else
	{
		return Jump(n - 1) + Jump(n - 2);
	}
}
int main()
{
	int get = 0;
	scanf("%d", &get);
	int method=Jump(get);
	printf("%d", method);
	return 0;
}

進階:一只青蛙一次可以最多跳m級臺階,求青蛙跳上n級臺階有多種跳法?

由第一個問題其實我們已經知道了這種問題的規律

假設m=3,那麼當n>3時,f(n)=f(n-1)+f(n-2)+f(n-3);

假設m=h,那麼當m>h時,f(n)=f(n-1)+f(n-2)+f(n-3)+。。。+f(n-h);

假設m=5,n=10;那麼我們就要求臺階1到5的不同跳法,當n=3時,青蛙最多可以跳3級,當n=4時,青蛙做多可以跳4級臺階,那麼對於求這些有個規律,n^2-1;   那麼我們就可以更簡便的求結果了;

代碼實現:

int add(int n, int m)
{
	int num = 0;
	for (int i = 1; i <= m; i++)
	{
		if (n == i)
		{ 
			return pow(2, i- 1);
		}
			
	}
	for (int i = 1; i <= m; i++)
	{
		num += add(n - i, m);
	}
	return num;
}
int main()
{
	int n = 0;
	int m = 0;
	scanf("%d %d", &n, &m);
	printf("%d", add(n, m));
	return 0;
}

代碼優化:

上述解法是用遞歸的問題解决的,但是,使用遞歸的辦法來解决效率不高,因為會有重複計算的問題,


 

因此我們可以用加法+迭代的方式進行計算,但是原理和上述解法一樣

代碼實現:

int main()
{
	int get[101] = { 0 };
	int a = 0;
	int b = 0;
	
	scanf("%d %d", &a, &b);
	for (int i = 1; i <= b; i++)
	{
			*(get+i)=pow(2,i - 1);	
	}

	for (int i = b+1; i <= a; i++)
	{
		for (int n = i-b; n <i; n++)
		{
			get[i] += get[n];
		}
	}
	printf("%d", get[a]);
	return 0;
}

 

版權聲明
本文為[m0_62616069]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201270220333944.html

隨機推薦