文档章节

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

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

© 著作权归作者所有

共有 人打赏支持
陶邦仁
粉丝 1588
博文 420
码字总数 1483822
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[MicroPython]STM32F407开发板驱动OLED液晶屏

1.实验目的 1.学习在PC机系统中扩展简单I/O 接口的方法。 2.进一步学习编制数据输出程序的设计方法。 3.学习 F407 Micropython开发板控制OLED显示字符。 2.所需元器件 F407 Micropython开发板...

bodasisiter
18分钟前
0
0
php require和include 相对路径一个有趣的坑

以前总是被教育,不要使用相对路径,这样性能比较差,但是相对路径的问题不仅仅是性能哦,看下面这里例子 这是项目结构 .├── main.php├── t│ ├── t1.php│ └── t2.php└─...

anoty
19分钟前
9
0
x64技术之SSDT_Hook

测试环境: 虚拟机: Windows 7 64bit 过PG工具 驱动加载工具 PCHunter64 系统自带的计算器和任务管理器等 实现思路: 实际思路与win32的思路一样.都是替换SSDT表里边的函数地址.不过微软被搞怕...

simpower
20分钟前
0
0
TreeMap源码分析,看了都说好

一、简介 TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很...

Java小铺
30分钟前
0
0
协变、逆变

概念 假设 A、B表示类型 ≤ 表示继承关系 f<⋅>表示类型转换 若A ≤ B,则 A是B的子类,B是A的超类 协变、逆变 什么是型变?型变(type variance)允许对类型进行子类型转换。 为了下面讲解先...

obaniu
36分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部