爱奇艺 2019校招 Android方向试卷在线考试
编程题|20.0分2/2
清雨的自助餐
时间限制：C/C 语言 1000MS；其他语言 3000MS 内存限制：C/C 语言 131072KB；其他语言 655360KB
题目描述：
清雨又在吃自助餐了。
排在清雨面前的有N种食物，排成一排，清雨可以选择其中的若干种食物，但是不能连续选择相邻的食物。因为清雨很挑食，当所有食物都不合口味时，他可以一种都不选，即一个都不选也算为一种方法。
请问他有多少种选择食物的方法呢？
输入
一个整数n（1 <= n <= 90）
输出
一个正整数表示答案
样例输入
3
样例输出
5
Hint
样例解释：有3种食物，方案为1、2、3、13、不选，共5种
思路：
刚开始以为深搜，然后发现到了最大90的时候运行出不来，超时。
结果一一列举发现，1个数字，选择或者不选，a[1]=2种情况
2个数字，1， 2， 不选，a[2]=3种情况
3个数字, 1， 2， 3， 13， 不选，a[3]=5种情况
4个数字，1， 2， 3， 4， 13， 14， 24， 不选，a[4]=8种情况
=========这不就是前两项和累加吗？斐波那契额啊
AC代码：
代码语言：javascript复制import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
cin.close();
System.out.println(fibonacci(n));
}
private static long fibonacci(int n) {
long y1 = 2, y2 = 3, y3 = 5, y = 0;
for (int i = 4; i <= n; i) {
y = y3 y2;
y2 = y3;
y3 = y;
}
if (n == 1)
return y1;
if (n == 2)
return y2;
if (n == 3)
return y3;
return y;
}
}记住一定要返回为long，数据很大，用int只能通过21%
