清雨的自助餐
| 时间限制： | C/C++语言 1000MS；其他语言 3000MS |
| 内存限制： | C/C++语言 131072KB；其他语言 655360KB |
题目描述
清雨又在吃自助餐了。
排在清雨面前的有N种食物，排成一排，清雨可以选择其中的若干种食物，但是不能连续选择相邻的食物。因为清雨很挑食，当所有食物都不合口味时，他可以一种都不选，即一个都不选也算为一种方法。
请问他有多少种选择食物的方法呢？
输入
一个整数n（1 <= n <= 90）
输出
一个正整数表示答案
样例输入
3
样例输出
5
Hint
样例解释：有3种食物，方案为1、2、3、13、不选，共5种
题目分析
设面对 个食物时，清雨有
种选法。
则，据题意：
若第 个食物被选中，则必有第
个不被选中，这种情况有
种；
若第 个食物未被选中，这种情况有
种。
故，有 成立。
所以这个题目实质上是一个斐波那契数列。代码如下：
#include <stdio.h>
int main()
{
int n;
long long s[91];
scanf("%d",&n);
s[0]=1;
s[1]=2;
for (int i=2;i<n;i++)
s[i]=s[i-1]+s[i-2];
printf("%lld\n",s[n]);
}
部分结果：
image.png
网友评论