文章

7

粉丝

116

获赞

2

访问

4.9k

头像
吃糖果 题解:递推
P1197 北京大学上机题
发布于2023年5月17日 14:53
阅读数 712

分析:
该题的问题是问有多少种不同的吃完巧克力的方案,而不是需要多少天的问题,所以天数只起迷惑作用。
我们假设盒内有1块巧克力,每次吃1或2块,求方法数;假设有2块巧克力,每次吃1或2块,求方法数;假设有3块巧克力,每次吃1或2块…类比下去会发现这个题就是走台阶问题(对于走台阶问题应该是比较熟悉的),巧克力数就是台阶数,每次能迈1或2阶。

巧克力数    方法数
1    1
2    2
3    3
4    5
…    …
可得递推式: f(n) = f(n-1)+f(n-2)

编程如下:

#include <iostream>
using namespace std;

int main()
{
    int n; //糖果数
    while (cin>>n) {
		int a[100] = {0}; //存储方法数
		a[1] = 1;
		a[0] = 1;
		for(int i=2;i<=n;i++){
			a[i] = a[i-1]+a[i-2];
		}
		cout<<a[n]<<endl;
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发