文档章节

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

陶邦仁
 陶邦仁
发布于 2012/09/12 22:33
字数 584
阅读 300
收藏 3
点赞 0
评论 0

一只羊的寿命是五年 他会在二岁和四岁 分别产下一只羊 如果一个牧场第一年引进一只羊 请问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哈哈~

© 著作权归作者所有

共有 人打赏支持
陶邦仁
粉丝 1555
博文 388
码字总数 1483822
作品 0
海淀
技术主管
算法分析_Index

常用算法 String indexOf 之BF、KMP算法 非递归方法实现对TB级文件目录的全遍历 一道新浪面试算法题,两行代码搞定,有兴趣的看看 斐波那契数列:一道100年后羊圈羊的数量算法题 白话算法 白...

陶邦仁 ⋅ 2014/03/24 ⋅ 0

C:单链表的循环和递归实现

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

kongming07 ⋅ 2017/12/13 ⋅ 0

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

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

闰土大叔 ⋅ 06/07 ⋅ 0

使用非递归的方式实现菲波那切数列

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

J星星点灯 ⋅ 2017/10/16 ⋅ 0

Python每日一题:第四题

今天来学一下Python之禅和他朋友们的第四题 题目 image 数列从0和1开始,之后的斐波那契系数由之前的两数相加而得出,例如斐波那契数列的前10个数是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34。用 ...

Treehl ⋅ 2017/11/20 ⋅ 0

python有趣的小编程

斐波那契数列的计算 描述 斐波那契数列(Fibonacci sequence),又称黄金分割数列,由意大利数学家Leonardo Fibonacci于1202年提出,并以其名字命名。该数列F(n)定义如下:F(0)=0, F(1)=1,...

巍峨大山 ⋅ 2017/01/04 ⋅ 5

斐波那契数列面试题解法(java)

斐波那契数列经常出现在程序员面试的题目中,本文总结一下斐波那契数列的解法 斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)...

qq_19259415 ⋅ 2017/11/13 ⋅ 0

斐波那契数列与生成器

斐波那契数列相信大家都不会陌生, 公式 F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) 网上有n种解法 这里我们讲的是斐波那契数列和生成器,Python笔试喜欢考的一题 看到了吧,...

翼动动空 ⋅ 2016/05/08 ⋅ 0

巴什博奕,威佐夫博奕,尼姆博奕,斐波那契博弈模板

原文:http://blog.csdn.net/lz161530245/article/details/77453107 1.巴什博奕 只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。 显然,如果...

hushhw ⋅ 2017/12/09 ⋅ 0

神奇兔子数列

假设第1个月有1对刚诞生的兔子,第2个月进入成熟期,第3个月开始生育兔子,而1对成熟的兔子每月会生1对兔子,兔子永不死去……那么,由1对初生兔子开始,12个月后会有多少对兔子呢? 兔子数列...

rainchxy ⋅ 2017/11/30 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

解决CentOS6、7,/etc/sysconfig/下没有iptables的问题

一、Centos 6版本解决办法: 1.任意运行一条iptables防火墙规则配置命令: iptables -P OUTPUT ACCEPT 2.对iptables服务进行保存: service iptables save 3.重启iptables服务: service ...

寰宇01 ⋅ 33分钟前 ⋅ 2

数据库备份和恢复

备份:mysqldump -u root -p 数据库>磁盘路径 恢复:mysql -u root -p 数据库<sql脚本的磁盘路径

anlve ⋅ 今天 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 今天 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 今天 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 今天 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 今天 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 今天 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部