清雨的自助餐(斐波那契数列的应用)
发布日期:2021-06-30 19:56:01
浏览次数:2
分类:技术文章
本文共 1204 字,大约阅读时间需要 4 分钟。
爱奇艺 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代码:
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%
=======================Talk is cheap, show me the code==========================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/82889679 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年05月04日 15时17分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Mysql 之主从复制
2019-04-30
LVS负载均衡------NAT模式
2019-04-30
squid代理-----透明代理模式
2019-04-30
squid代理介绍----ACL控制应用+sarg日志分析+反向代理
2019-04-30
redis集群之主从模式+哨兵模式
2019-04-30
JavaScript原生开关灯效果
2019-04-30
企业邮箱如何申请注册,邮箱申请如何免费注册?
2019-04-30
微信企业邮箱,手机邮箱格式地址怎么写?
2019-04-30
公司如何申请企业邮箱,公司邮箱怎么申请,公司企业邮箱哪个好?
2019-04-30
电子邮箱账号怎么申请,怎样申请邮箱账号呢
2019-04-30
邮箱怎么发邮件,邮件发信量多少,职场新人怎么发汇报邮件呢?
2019-04-30
maven 多层次pom 新引入包,编译成功,还是没有将包引入到本地
2019-04-30
leetCode2 两数相加
2019-04-30
【工具使用】使用pip与conda安装、更新与卸载Pytorch和torchvision
2019-04-30
【工具使用】Google免费云环境Colaboratory使用
2019-04-30
【深度学习笔记】卷积层,全连接层,池化层的相关输出参数计算
2019-04-30