当前课程知识点:组合数学 >  线性常系数递推关系 >  Fibonacci数列 >  Fibonacci兔子

返回《组合数学》慕课在线视频课程列表

Fibonacci兔子在线视频

Fibonacci兔子

下一节:Fibonacci恒等式

返回《组合数学》慕课在线视频列表

Fibonacci兔子课程教案、知识点、字幕

很高兴能和大家再次相聚

一起学习组合数学

要说起组合数学里面我最喜欢什么

我会毫不犹豫地说

就是斐波那契数

斐波那契数实在太神奇了

它的故事实际上是从一群兔子开始的

在第一个月两只小兔子相遇了

一雄一雌

在第二个月它们结婚了

第三个月它们生出了小兔子

而这生出来的小兔子也恰巧是两只

一雄一雌

而且这些兔子非常神奇

它们永生不死

那么请问你

如果在第五十个月

这兔子能达到多少只呢

这就是最有名的斐波那契兔子问题

那我们来分析一下

它到底怎么去计算呢

比如说我们来看

在第一个月的时候

两只兔子相遇了

而第二个月它们只是结婚了

所以个数没有发生变化

仍然是2只兔子

但是到了第三个月

因为它们生了小baby

所以现在变成了4只兔子

一共两对兔子

那么接下来它们的兔子照样可以成长

照样可以去结婚生子

所以在后面呢 我们会发现

每只兔子一旦成熟之后

它在下一个月都会生两只一雄一雌的兔子

而新生出来的兔子呢

它下一个月才慢慢成熟

直到下下个月才会生出新的兔子

那么我们分析一下

如说第四个月该多少只兔子呢

这时候我们发现

实际上有一部分兔子就来源于最老的那只兔子

它自己活下来了

同时它又新生了一对兔子

而这边呢

刚才第三个月的兔子呢

它又持续活到了第四个月

接着依次往复

所以我们会发现

每一个月的兔子来源于两个部分

一部分是上一个月的兔子依然在下个月活着

而另外一部分呢

是这个月新生出来的兔子

而新生的兔子

和什么数量相等呢

正好是在上上个月的兔子

这个月都会生小兔子

所以兔子的含量实际上包括两部分

一个部分也就是n减1个月它有多少只兔子

另外一部分来源于它的上上个月

也就是n减2个月有多少只兔子

这我们就列出了斐波那契兔子的一个递推公式

也就是说我们要求第n个月一共会有多少只兔子

用fn来表示的话

那么fn就等于fn减1加上fn减2

所以我们来看斐波那契序列

实际上斐波那契序列中第一个数就是1

第二个数呢

仍然是1

第三个数等于前面两个数之和

1加1等于2

接着往下

1加2等于3

2加3等于5

因此 我们就可以通过递推关系得到斐波那契数列

它的递推关系就是fn等于fn减1加上fn减2

一般情况下

我们认为为了能够算出f0的话

这里面的n应该大于等于2

那么除了它的关系之外

我们还需要递推式的初始值

这里面我们可以看到

如果要计算n等于2的时候

我们需要一个数值

f0

f0实际上等于0

因此在原来序列中

我们一定要注意

1、1、2、3、5是从1开始算起的

但是其实前面还有一个f0

也就是0

第二个数字呢

就应该是f1等于1

因此对于递推关系斐波那契数列来说

的初始值就是f0等于0

和f1等于1

这个序列非常重要

在我们经常提到的OEIS数据库中

它被列为是第45号序列

为什么它被称为是斐波那契数列呢

当然它和斐波那契密不可分

斐波那契

实际上是意大利的一位学者

它的本名并不叫斐波那契

斐波那契只是他的小名

他的真名实际上叫做

Leonardo of Pisa

可以看到

他就是意大利的比萨市的人

而他呢

实际上(呢)这个问题

也不是他始作俑者(始作俑者的感情色彩。。。)

在1105年的时候

印度学者就已经研究了长度为1

和长度为2的小方块

累加在一起摆成一条路的话

会有多少种不同的方案

实际上这就是

斐波那契最早的原形

而真正把它发扬光大的

就是Leonardo of Pisa

他做了什么呢

实际上他写的一本书

在1202年的时候

他写的一本叫做

《算盘全书》的书

这本书第一次

向西方世界

给大家介绍了东方数学的魅力

所以有人也说到

说除了希腊数学之外

西方的数学大部分都源于

斐波那契

而斐波那契

为什么有这样的机会

能够去东方学数学呢

离不开他的家族背景

他的父亲

实际上就是在

Leonardo of Pisa他二十二岁的时候

带着他一块去了

东方 印度 阿拉伯

所以在那里

他能够有机会接触到

东方的数学

尤其是印度的数学

而他回到了意大利之后

把这些发扬光大

所以我们可以看到

其实东西合璧

才是真正数学走的一条必经之路

说到这里呢

我们回头再看

为什么我说斐波那契数太神奇了

大家一定还很熟悉

我们的杨辉三角吧

而斐波那契数列

和杨辉三角密不可分

以往我们总是两两的去加

这样杨辉三角的数字

如果我们把它

斜着一条一条加过来的话

发现每一条线的和

正好就是斐波那契数

而斐波那契数

是自然界的秘密法则

我们看一颗树

一颗树成长起来以后

它就会分枝开叶

它会分成不同的枝条

而它的枝条数目

一定是满足斐波那契数列的

也就是

1、2、3、5、8依次向上

我们再看那些花朵

你去找世界上所有的花朵

它的花瓣数目

一定是斐波那契数

学术界为了探究

斐波那契数列的秘密

在1963年

专门设立了一个刊物

就叫做TheFibonacci Quarterly

专门刊登

这个序列发现的新研究

它太神奇了

在数学上

有很多意想不到的结果

会发现

它的每一位数字

在每六十位会重复

而最后的两位数字

每三百位都会重复

每三位数字

到了一千五百个

就会不断重复

而这样的pattern

会不断地循环往复

而同时我们会发现

在斐波那契序列中

每三个数

就可以被2整除

而每第四个数

就可以被3整除

每第五个数可以被5整除

每第六个数可以被8整除

而这些除数

同样是斐波那契序列的

那么说到整除

自然大家就想

那有没有素数呢

实际上一个非常神秘的数字

被称为是Fibonacci prime

大家知道

素数是我们数论中一颗奇葩

而斐波那契又是那么有魅力

它们两个既然可以结合在一起

什么叫做Fibonacci prime

也就是说在斐波那契数列中

有多少个素数我拿出来

就可以构成一个序列

这个序列在OEIS中

被列为是5478号

而我们可以看到

除了n等于4这个序号之外

所有的斐波那契素数

序号都是素数

但是反过来

并不是所有序号

都是素数的斐波那契数

都是素数

这时候大家就会想了

那么在斐波那契数中

到底有多少个素数呢

会不会随着斐波那契

无穷地涨下去

它的素数

也会无穷地增加呢

到目前为止

这样一个想法仍然是猜想

没有得到证明

而我们已经找到的

最大的素数

实际上它也是斐波那契数

它的位数

已经达到了

17103位

所以可以看到

研究斐波那契数

实际上也帮我们找到了一个途径

去研究素数

看到斐波那契数

有这么多美丽的性质

我们自然就想一想

数学上

它会有什么样不同的表现呢

下一节

我们来分析斐波那契数的数学表现

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(1)

--采访武永卫老师

-第一周作业

--作业说明

--H

--U

--G

--作业讨论区说明

-第一周演示程序

--程序讨论区说明

--幻方生成器

--换方计数

--屏幕解锁方案数

--欧拉路计数

--共享程序

小乒乓球的组合之旅

-加减乘除来计数

--计数的基本法则

-排列还是组合

--排列还是组合

--小乒乓球的组合之旅--排列还是组合

--格路模型与组合恒等式

-各种各样的排列

--圆排列和项链排列

--圆排列和项链排列--习题

--多重排列

--多重排列--练习

-多样的组合

--可重组合

--不相邻组合

--小乒乓球的组合之旅--多样的组合

-钟声里的全排列

--钟声里的全排列

--钟声里的全排列

--字典序法

--SJT算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Fibonacci兔子笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。