文档章节

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

陶邦仁
 陶邦仁
发布于 2012/09/12 22:33
字数 584
阅读 308
收藏 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哈哈~

© 著作权归作者所有

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

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

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

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

闰土大叔
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
科普向 - 趣味的斐波那契数列

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

ssssyoki
08/11
0
0
Fibonacci 斐波那契数列的几种写法、时间复杂度对比

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

菜鸟学Python
07/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

w, vmstat, top, sar, nload命令查看系统状态信息

w/uptime 查看系统负载 cat /proc/cpuinfo 查看cpu核数 vmstat 监控系统状态,用法 vmstat 1,关键的几列: r, b, swpd, si, so, bi, bo, us, wa top 查看进程使用资源情况 top -c 显示详细的...

野雪球
今天
1
0
小白创建一个spring boot项目

进入 https://start.spring.io/

lilugirl
今天
2
0
Alibaba Java诊断利器Arthas实践--使用redefine排查应用奇怪的日志来源

背景 随着应用越来越复杂,依赖越来越多,日志系统越来越混乱,有时会出现一些奇怪的日志,比如: [] [] [] No credential found 那么怎样排查这些奇怪的日志从哪里打印出来的呢?因为搞不清...

hengyunabc
今天
2
0
home hosts

home hosts lwk@qwfys:~$ cat /etc/hosts127.0.0.1 localhost127.0.1.1 qwfys192.168.56.101vm600.qwfys.com39.108.212.91alpha1.ppy.com39.108.117.122alpha2.p......

qwfys
今天
3
0
大数据教程(6.1)hadoop生态圈介绍及就业前景

1. HADOOP背景介绍 1.1、什么是HADOOP 1.HADOOP是apache旗下的一套开源软件平台 2.HADOOP提供的功能:利用服务器集群,根据用户的自定义业务逻辑,对海量数据进行分布式处理 3.HADOOP的核心组...

em_aaron
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部