文档章节

斐波那契数列:一道100年后羊圈羊的数量算法题

陶邦仁
 陶邦仁
发布于 2012/09/12 22:33
字数 584
阅读 309
收藏 3

一只羊的寿命是五年 他会在二岁和四岁 分别产下一只羊 如果一个牧场第一年引进一只羊 请问N年后 这个羊圈 有几只羊?(不考虑羊的交配以及疾病等因素)

先说下分析思路:

1)由题意得知:在N年内,所有羊仅在偶数年生育;羊的寿命为五年;

2)将羊圈看成一个大的容器,羊圈中最终的数量=羊的出生数量-羊的死亡数量。

以下先列出20年之内,每年羊的出生数量、羊的死亡数量:

偶数年              出生数量               死亡数量                   增长数量

0                      1                          0                              1

2                      1                          0                              1 

4                      2                          0                              2

6                      3                          1                              2

8                      5                          1                              4 

10                    8                          2                              6

12                    13                        3                              10

14                    21                        5                              16

16                    34                        8                              26

18                    55                        13                            42

20                    89                        21                            68

观察20年内羊的增长数量得知,从第6年开始,偶数年增长数量为斐波那契数列:2,4,6,10,16,26,42,68,....

所以,在N年内,羊的总数量=1+1+2+(从第6年至N年内每偶数年的增长数量斐波那契数列总和);

以上就是本思路,不多说了,直接上代码:

   /**
     * 获得N年后羊总数量
     * @param year 多少年
     * @return
     */
    public static long getTotalCountByYear(int year){
        if(year%2!=0) year--;
        long _1thCount = 2;// 第6年增长数量
        long _2thCount = 4;// 第8年增长数量
        long _3rdCount = _2thCount+_1thCount;// 第10年增长数量
        long totalCount = _1thCount+_2thCount+_3rdCount;
        System.out.print(_1thCount+","+_2thCount+","+_3rdCount+",");
        for(int i=12;i<=year;i=i+2){
            _1thCount = _2thCount;
            _2thCount = _3rdCount;
            _3rdCount = _2thCount+_1thCount;
            totalCount = totalCount + _3rdCount;
            System.out.print(_3rdCount+",");
        }
        return 1+1+2+totalCount;
    }

由以上方法得出100年之后羊圈羊的数量:40730022148,而且和之前的一些算法相比,在效率方面也很高。。。所以真正的性能优化,在很大程度上取决于算法,而算法优化,更是取决于所选的思路。

由此题看来,还真应了那句话,“给我一个女人,我就能创造出一个民族。。。“O(∩_∩)O哈哈~

© 著作权归作者所有

共有 人打赏支持
陶邦仁
粉丝 1636
博文 420
码字总数 1483887
作品 0
海淀
技术主管
私信 提问
C:单链表的循环和递归实现

两天前,C语言课上讲了单链表的实现,下课回到寝室立马开始动手写,中间还是出了几个BUG,不过最终首先用循环实现了最简单的单链表 之后我尝试用递归实现,发现对于建立单链表而言递归比循环...

kongming07
2017/12/13
0
0
太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

面试攒经验,let's go! 值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考...

闰土大叔
2018/06/07
0
0
使用非递归的方式实现菲波那切数列

题目要求:编写程序在控制台输出斐波那契数列前20项,每输出5个数换行 方法一:public class Fibonacci1{ //定义三个变量方法 public static void main(String[] args) { int a=1, b=1, c=0...

J星星点灯
2017/10/16
0
0
Fibonacci 斐波那契数列的几种写法、时间复杂度对比

  单身汪节早已被商家重新定义,除了买买买还可以做点什么?我看在家修炼编程技术是不错的选择,「用Python实现斐波那契数列」是我们在知识星球中每周给大家安排的一道题,你也可以先思考一...

菜鸟学Python
2018/07/31
0
0
科普向 - 趣味的斐波那契数列

1.从一道面试题开始 每个程序员从第一次接触计算机编程语言到真正作为工程师进行项目开发,都一定都见过下面这道题目: 很多个台阶,可以一次走一个台阶,也可以一次走两个台阶,那么走台阶时...

ssssyoki
2018/08/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

WEB 开发总结

事务处理 事务的4个基本特征 1.Atomic(原子性),事务中包含的操作被看做是一个整体的业务单元,这个业务单元中的操作要么全部成功,要么全部失败,不会出现部分成功,部分失败的场景。 2....

北漂的我
6分钟前
0
0
thinkphp5 利用七牛云 将amr格式语音文件转为mp3

$card_id 是我的本地的文件 将问价名字的后缀名去掉注意access_token的有效期public function ceshi1($card_id){ $mediaid = substr($card_id, 0, -4); $accessKey = ...

小小小壮
10分钟前
0
0
数据区域之堆栈

java虚拟机在执行java程序的过程中会把它所管理的内存划分为若干个不同的数据区域, 这些区域都有各自的用途,创建和销毁时间 图: 程序计数器是一个较小的内存空间,它的作用可以看做是当前...

恋码之子
11分钟前
0
0
新的一年,来看看大数据与AI的未来展望

本文由云+社区发表 作者:堵俊平 在数据爆炸与智能革命的新时代,新的平台与应用层出不穷,开源项目推动了前沿技术和业界生态快速发展。本次分享将以技术和生态两大视角来看大数据和人工智能...

腾讯云加社区
11分钟前
1
0
死磕源码系列(ReentrantLock)

前言 在高并发领域,ReentrantLock有着广泛的用处,防止多线程带来的并发问题 对于源码,很多人和我一开始一样都觉得非常神秘 这次我将对ReentrantLock进行全方面的揭秘 核心 AbstractQueued...

石日天
12分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部