tokenpockettokenpocketcom官网下载正版|斐波拉契

斐波那契数列_百度百科

数列_百度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心收藏查看我的收藏0有用+10斐波那契数列播报讨论上传视频称黄金分割数列本词条由中国科学院大学数学科学学院 参与编辑并审核，经科普中国·科学百科认证 。斐波那契数列（Fibonacci sequence），又称黄金分割数列 [1]，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定z义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。 [2]中文名斐波那契数列外文名Fibonacci sequence别    名黄金分割数列、兔子数列表达式F[n]=F[n-1]+F[n-2](n>=2,F[0]=1,F[1]=1)提出者莱昂纳多·斐波那契提出时间1202年适用领域代数应用学科数学目录1定义2由来3通项公式▪递推公式▪通项公式内容▪通项公式推导4特性▪平方与前后项▪与集合子集数量的关系▪奇数项求和▪偶数项求和▪平方求和▪隔项关系▪两倍项关系▪其他公式5应用▪与黄金分割比的关系▪杨辉三角▪矩形面积▪质数数量▪尾数循环▪自然界中“巧合”▪数字谜题▪影视作品中的斐波那契数列6推广▪斐波那契—卢卡斯数列▪广义斐波那契数列7相关的数学问题▪排列组合▪兔子繁殖问题定义播报编辑斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。由来播报编辑在数学历史上，欧洲黑暗时期过后，第一位有影响的数学家是斐波那契(L．Fibonacci，1170一1250)。他早年就随其父在北非师从阿拉伯人学习算学，后又游历地中海沿岸诸国，回意大利后写成《算经[xq2] 》，也翻译成《算盘书》。这部很有名的著作主要是一些源自古代中国、印度和希腊的数学问题的汇集，内容涉及整数和分数算法、开方法、二次和三次方程以及不定方程。特别是，在1228年的《算经》修订版上载有如下“兔子问题”： [3]如果每对兔子（一雄一雌）每月能生殖一对小兔子（也是一雄 一[xq3] 雌，下同），每对兔子第一个月没有生殖能力，但从第二个 月[xq4] 以后便能每月生一对小兔子.假定[xq5] 这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12 个月以后会有多少 对[xq6] 兔子呢？ 解释说明为：一个月[xq7] ：只有一对兔子；第二个月： 仍然只有一对兔子；第三个月：这对兔子生了一对小兔子， 共有 1+1=2 对兔子.第四个月[xq8] ：最初的一对兔子又生一对兔 子，共有 2+1=3 对兔子.则由第一个月到第十二个月兔子的 对数分别是：1，1，2，3，5，8，13，21，34，55，89，144， ……，后 人[xq9] 为了纪念提出兔子繁殖问题的斐波纳契， 将这个兔子数 列[xq10] 称为斐波那契数列， 即把 1，1，2，3，5，8，13，21，34……这样的数列称为斐波那契数列。 [4]通项公式播报编辑递推公式斐波那契数列：1，1，2，3，5，8，13，21，34，55，89…… ，以如下被以递归的方法定义：从第三项开始，每一项都等于前两项之和，显然这是一个线性递推数列。通项公式内容⑴如上，又称为“比内公式”，是用无理数表示有理数的一个范例。且由上式得到的值必为正整数。 [5]注：此时⑵ 通项公式推导（1）方法一：利用特征方程（线性代数解法）线性递推数列的特征方程为：解得：则：由公式得：解得（2）方法二：待定系数法构造等比数列1（初等代数解法）设常数，使得则时，有：联立以上个式子，得：上式可化简得：那么：（这是一个以为首项、以为末项、为公比的等比数列的各项的和）。， 的解为，则（3）方法三：待定系数法构造等比数列（初等代数解法）设得构造方程解得所以：由(1)、(2)式得：令：化简可得：（4）方法四：母函数法对于斐波那契数列，有:（）令那么有：因此.不难证明：因此再利用展开式于是就可以得其中因此可以得到：特性播报编辑平方与前后项从第二项开始（构成一个新数列，第一项为1，第二项为2，……），每个偶数项的平方都比前后两项之积多1，每个奇数项的平方都比前后两项之积少1。如：第二项 1 的平方比它的前一项 1 和它的后一项 2 的积 2 少 1，第三项 2 的平方比它的前一项 1 和它的后一项 3 的积 3 多 1。（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项 1 开始数，第 4 项 5 是奇数，但它是偶数项，如果认为 5 是奇数项，那就误解题意，怎么都说不通）证明经计算可得：与集合子集数量的关系斐波那契数列的第n+2项同时也代表了集合中所有不包含相邻正整数的子集个数。奇数项求和偶数项求和平方求和隔项关系两倍项关系其他公式如果，，，，……，则有：因，，则有：应用播报编辑与黄金分割比的关系这样一个完全是自然数的数列，通项公式是用无理数来表达的。而且当 趋向于无穷大时，前一项与后一项的比值越来越逼近黄金分割0.618（或者说后一项与前一项的比值小数部分越来越逼近 0.618）。 [2]………………越到后面， 的比值越接近黄金比。证明：由，两边同时除以由 得到： 若的极限存在，设其极限为 , 则 杨辉三角将杨辉三角左对齐，成图1所示排列，将同一斜行的数加起来，即得一数列 1、1、2、3、5、8、……公式表示如下：矩形面积斐波那契数列与矩形面积的生成相关，由此可以导出一个斐波那契数列的一个性质。斐波那契数列前几项的平方和可以看做不同大小的正方形，由于斐波那契的递推公式，它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积。则可以得到如下的恒等式：质数数量斐波那契数列的整除性与质数生成性每3个连续的数中有且只有一个被 2 整除，每4个连续的数中有且只有一个被 3 整除，每5个连续的数中有且只有一个被 5 整除，每6个连续的数中有且只有一个被 8 整除，每7个连续的数中有且只有一个被 13 整除，每8个连续的数中有且只有一个被 21 整除，每9个连续的数中有且只有一个被 34 整除，.......我们看到第5、7、11、13、17、23位分别是质数：5，13，89，233，1597，28657（第19位不是）尾数循环斐波那契数列的个位数：一个60步的循环：11235,83145,94370,77415,61785,38190,99875,27965,16730,33695,49325,72910…进一步，斐波那契数列的最后两位数是一个300步的循环，最后三位数是一个1500步的循环，最后四位数是一个15000步的循环，最后五位数是一个150000步的循环。自然界中“巧合”斐波那契数列表面看来似乎简单有趣，然而人们发现该数列不仅与黄金分割数，组合数学及概率论等一系列深刻的数学问题关系密切，甚至发现植物枝权与叶序分布、菠萝纹理与蜂房结构等大量的自然现象也遵从斐波那契数列的奇妙构造。 [6]例如，树木的生长，由于新生的枝条，往往需要一段“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段间隔，例如一年，以后长出一条新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年生的新枝则次年“休息”。这样，一株树木各个年份的枝桠数，便构成斐波那契数列。这个规律，就是生物学上著名的“鲁德维格定律”。另外，观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们花瓣数目具有斐波那契数：3、5、8、13、21……其中百合花花瓣数目为 3，梅花 5 瓣，飞燕草 8 瓣，万寿菊 13 瓣，向日葵 21 或 34 瓣，雏菊有 34、55 和 89 三个数目的花瓣。斐波那契螺旋：在大自然里存在着许多斐波那契螺旋线形态，向日葵花盘有着两组紧密盘旋的螺旋线，一组按照顺时针旋转的数目为21，另一组按照逆时 针旋转的数目为3 4，正 好是斐波 那契数列中相邻的两个 数且比值接近黄金分割比，而且排列的种子以中心为点四面发散形成的角度接近于黄金角；银河系中的四条主旋臂旋转分开组成大约为12度的角度，它所反映出来的螺旋形状和斐波那契螺旋线几乎完全相同；鹦鹉螺外壳截面形状为典型的斐波那契螺旋形，被认为是以斐氏数列形成的最完美的螺旋线。 [7]事实上许多常见的植物，如我们食用的青菜、包心菜、芹菜等的叶子排列也具有这个特性。尽管这些顺逆螺旋的数目并不固定，但它们也并不随机，它们是斐波那契序列中的相邻数字。这些植物懂得斐波那契数列吗？当然并非如此，它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”，它能使所有种子具有差不多的大小空间却又疏密得当，不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长的过程中一直都能最佳地利用空间(要考虑到叶子是一片一片逐渐地生长出来，而不是一下子同时出现的)，每片叶子和前一片叶子之间的角度应该是222．5度，这个角度被称为“黄金角度”，因为它和整个圆周360度之比是黄金分割数1．618033989⋯⋯的倒数，而这种生长方式就决定了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89条，甚至144条。 [8]数字谜题三角形的三边关系定理和斐波那契数列的一个联系：现有长为 144 cm 的铁丝，要截成n小段（n≥3），每段的长度不小于 1 cm，如果其中任意三小段都不能拼成三角形，则n的最大值为：由于形成三角形的充要条件是任何两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。截成的铁丝最小为 1，因此可以放 2 个 1，第三条线段就是 2（为了使得n最大，因此要使剩下来的铁丝尽可能长，因此每一条线段总是前面的相邻2段之和），依次为：1、1、2、3、5、8、13、21、34、55，以上各数之和为 143，与 144 相差 1，因此可以取最后一段为 56，这时 n 达到最大为 10。我们看到，“每段的长度不小于 1”这个条件起了控制全局的作用，正是这个最小数1 产生了斐波那契数列，如果把 1 换成其他数，递推关系保留了，但这个数列消失了。这里，三角形的三边关系定理和斐波那契数列发生了一个联系。在这个问题中，这个143是斐波那契数列的前项和，我们是把144超出143的部分加到最后的一个数上去，如果加到其他数上，就有3条线段可以构成三角形了。影视作品中的斐波那契数列斐波那契数列在欧美可谓是尽人皆知，于是在电影这种通俗艺术中也时常出现，比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现，在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名，多数人也就背过前几个数，并没有深入理解研究。在电视剧中也出现斐波那契数列，比如：日剧《考试之神》第五回，义嗣做全国模拟考试题中的最后一道数学题~在FOX 热播美剧《Fringe》中更是无数[xq1] 次引用，甚至作为全剧宣传海报的设计元素之一。推广播报编辑斐波那契—卢卡斯数列卢卡斯数列 1、3、4、7、11、18…，也具有斐波那契数列同样的性质。（我们可称之为斐波那契—卢卡斯递推：从第三项开始，每一项都等于前两项之和）卢卡斯数列的通项公式为这两个数列还有一种特殊的联系（如下表所示），，及12345678910…斐波那契数列F(n)11235813213455…卢卡斯数列L(n)13471118294776123…138215514437798725846765…类似的数列还有无限多个，我们称之为斐波那契—卢卡斯数列。如1，4，5，9，14，23…，因为1，4开头，可记作F[1，4]，斐波那契数列就是F[1，1]，卢卡斯数列就是F[1，3]，斐波那契—卢卡斯数列就是F[a，b]。斐波那契—卢卡斯数列之间的广泛联系：①任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列。如：F[1,4]n+F[1,3]n=F[2,7]n，F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1)，n12345678910…F[1,4]n14591423376097157…F[1,3]n13471118294776123…F[1,4]n-F[1,3]n0112358132134…F[1,4]n+F[1,3]n27916254166107173280…②任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得，如n12345678910…F[1,1](n)11235813213455…F[1,1](n-1)0112358132134…F[1,1](n-1)0112358132134…F[1,3]n13471118294776123…黄金特征与孪生斐波那契—卢卡斯数列斐波那契—卢卡斯数列的另一个共同性质：中间项的平方数与前后两项之积的差的绝对值是一个恒值，斐波那契数列：卢卡斯数列：|3*3-1*4|=|4*4-3*7|=…=5F[1,4]数列：|4*4-1*5|=11F[2,5]数列：|5*5-2*7|=11F[2,7]数列：|7*7-2*9|=31斐波那契数列这个值是1最小，也就是前后项之比接近黄金比例最快，我们称为黄金特征，黄金特征1的数列只有斐波那契数列，是独生数列。卢卡斯数列的黄金特征是5，也是独生数列。前两项互质的独生数列只有斐波那契数列和卢卡斯数列这两个数列。而F[1,4]与F[2,5]的黄金特征都是11，是孪生数列。F[2,7]也有孪生数列：F[3,8]。其他前两项互质的斐波那契—卢卡斯数列都是孪生数列，称为孪生斐波那契—卢卡斯数列。广义斐波那契数列斐波那契数列的黄金特征1，还让我们联想到佩尔数列：1，2，5，12，29，…，也有|2*2-1*5|=|5*5-2*12|=…=1（该类数列的这种特征值称为勾股特征）。佩尔数列Pn的递推规则：据此类推到所有根据前两项导出第三项的通用规则：，称为广义斐波那契数列。当时，我们得到斐波那契—卢卡斯数列。当时，我们得到佩尔—勾股弦数（跟边长为整数的直角三角形有关的数列集合）。当时，我们得到等差数列。其中时，我们得到自然数列1，2，3，4，5…自然数列的特征就是每个数的平方与前后两数之积的差为 1（等差数列的这种差值称为自然特征）。具有类似黄金特征、勾股特征、自然特征的广义——斐波那契数列 。当，时，我们得到等比数列1，2，4，8，16…相关的数学问题播报编辑排列组合有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第 10 级台阶有几种不同的走法?这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法……1，2，3，5，8，13…… 所以，登上十级，有 89 种走法。类似的，一枚均匀的硬币掷10次，问不连续出现正面的可能情形有：答案是种。求递推数列的通项公式由数学归纳法可以得到：，将斐波那契数列的通项式代入，化简就得结果。兔子繁殖问题一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死：我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对两个月后，生下一对小兔对数共有两对三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……依次类推可以列出下表：经过月数01234567891011…幼仔对数1011235813213455成兔对数01123581321345589总体对数1123581321345589144幼仔对数=前月成兔对数成兔对数=前月成兔对数+前月幼仔对数总体对数=本月成兔对数+本月幼仔对数可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项，即斐波那契数列。新手上路成长任务编辑入门编辑规则本人编辑我有疑问内容质疑在线客服官方贴吧意见反馈投诉建议举报不良信息未通过词条申诉投诉侵权信息封禁查询与解封©2024 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号 京公网安备110000020000

斐波那契数列（Fibonacci sequence）及相关结论 - 知乎

斐波那契数列（Fibonacci sequence）及相关结论 - 知乎切换模式写文章登录/注册斐波那契数列（Fibonacci sequence）及相关结论刘金堂一、定义斐波那契数列（Fibonacci sequence），又称黄金分割数列，因意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）1202年以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、55、89…… 这个数列从第 3 项开始，每一项都等于前两项之和。在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N） 二、通项公式1、递推公式：\begin{cases}F(0)=0\\F(1)=1\\F(n)=F(n - 1)+F(n - 2) \end{cases}\qquad(n\in N)\\2、通项公式： {F_n =\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]} \\证明一：（构造等比数列）设常数r和s满足： {F_{n}-r F_{n-1}=s\left(F_{n-1}-r F_{n-2}\right)} 即：F_{n}=(s+r) F_{n-1}-s r F_{n-2} 则r和s满足如下条件：\begin{aligned} &s+r=1 \\ &s r=-1 \end{aligned} \\由韦达定理知，r和s为一元二次方程 x^2-x-1=0 的两个根，不妨令r=\frac{1-\sqrt{5}}{2} \quad s=\frac{1+\sqrt{5}}{2} \\当 n\geq3 时，有\cfrac{F_{n}-r F_{n-1}}{F_{n-1}-r F_{n-2}}=s \\即\begin{gathered} \cfrac{F_{3}-r F_{2}}{F_{2}-r F_{1}}=s \\ \cfrac{F_{4}-r F_{3}}{F_{3}-r F_{2}}=s \\ \vdots \\ \cfrac{F_{n}-r F_{n-1}}{F_{n-1}-r F_{n-2}}=s \end{gathered} \\上式共 n-2 个式子，累乘得\cfrac{F_{n}-r F_{n-1}}{F_{2}-r F_{1}}=s^{n-2} \\由于 s = 1 - r ， F_1 = F_2 = 1 ，所以有F_{n}=s^{n-1}+r F_{n-1} \\将 F_{n-1} ， F_{n-2} 直到 F_{3} 按照上述递推关系式进行展开有\begin{aligned} F_{n} &=s^{n-1}+r F_{n-1}=s^{n-1}+r\left(s^{n-2}+r F_{n-2}\right) \\ &=s^{n-1}+r s^{n-2}+r^{2} F_{n-2}=s^{n-1}+r s^{n-2}+r^{2}\left(s^{n-3}+r F_{n-3}\right) \\ &=s^{n-1}+r s^{n-2}+r^{2} s^{n-3}+r^{3} F_{n-3}=\ldots \\ &=s^{n-1}+r s^{n-2}+r^{2} s^{n-3}+\ldots+r^{n-2} s+r^{n-1} F_{1} \\ &=s^{n-1}+r s^{n-2}+r^{2} s^{n-3}+\ldots+r^{n-2} s+r^{n-1} \end{aligned} \\可见 F_n 是首项为 s^{n-1} ，公比为 \cfrac{r}{s} ，末项为 r^{n-1} 的等比数列求和，根据等比数列求和公式有F_{n}=\frac{s^{n-1}\left(1-\left(\cfrac{r}{s}\right)^{n}\right)}{1-\cfrac{r}{s}}=\cfrac{s^{n}-r^{n}}{s-r} \\将r和s代入得斐波那契数列的通项公式F_n为\begin{aligned} F_{n} &=\cfrac{s^{n}-r^{n}}{s-r}=\cfrac{\left(\cfrac{1+\sqrt{5}}{2}\right)^{n}-\left(\cfrac{1-\sqrt{5}}{2}\right)^{n}}{\cfrac{1+\sqrt{5}}{2}-\cfrac{1-\sqrt{5}}{2}} \\ &=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right] \end{aligned} \\即 {F_n =\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]} \\方法二：特征根法F_n=F_{n-1}+F_{n-2} x^2=x+1 x_1=\cfrac{1+\sqrt5}{2},\;x_2=\cfrac{1-\sqrt5}{2} F_n=(\cfrac{1+\sqrt5}{2})^nC_1+(\cfrac{1-\sqrt5}{2})^nC_2 \therefore C_1=C_2=\cfrac{1}{\sqrt5} {F_n =\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}\right]} \\三、斐波那契数列与黄金分割斐波那契数列前一项与后一项之比的极限为黄金分割比。证明：由于{F_n =\cfrac{1}{\sqrt{5}}\left[\left(\cfrac{1+\sqrt{5}}{2}\right)^{n}-\left(\cfrac{1-\sqrt{5}}{2}\right)^{n}\right]} \\因此，斐波那契数列前一项与后一项之比为\begin{aligned} &\frac{F_{n}}{F_{n+1}}=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}=\frac{\frac{2}{1+\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{2}{1-\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}\\ &=\frac{\frac{\sqrt{5}-1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(-\frac{1+\sqrt{5}}{2}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}\\ &=\frac{\frac{\sqrt{5}-1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{\sqrt{5}-1}{2}-\sqrt{5}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}\\ &=\frac{\frac{\sqrt{5}-1}{2}\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\frac{\sqrt{5}-1}{2}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}+\frac{\sqrt{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}{\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}}\\ &=\frac{\sqrt{5}-1}{2}+\frac{\sqrt{5}}{\left(-\frac{3+\sqrt{5}}{2}\right)^{n+1}-1} \end{aligned} \\即{\cfrac{F_{n}}{F_{n+1}}=\cfrac{\sqrt{5}-1}{2}+\cfrac{\sqrt{5}}{\left(-\cfrac{3+\sqrt{5}}{2}\right)^{n+1}-1}} \\当 n \rightarrow+\infty 时，\cfrac{F_{n}}{F_{n+1}}=\cfrac{\sqrt{5}-1}{2} \\四、几个重要的结论1、前 n 项和公式： F_{1} +F_{2} +\cdots +F_{n} =F_{n+2} -1 \\ 证明：由于斐波那契数列的通项公式为： {F_n =\cfrac{1}{\sqrt{5}}\left[\left(\cfrac{1+\sqrt{5}}{2}\right)^{n}-\left(\cfrac{1-\sqrt{5}}{2}\right)^{n}\right]} \\其显然是两个等比数列的线性组合，因此我们可以利用等比数列的求和公式来计算斐波那契数列的前 n 项和。这里我们由定义和通项公式可以直接得到如下结论：\begin{align} &F_{1} +F_{2} +\cdots +F_{n} \\&=F_2+(F_{1} +F_{2} +\cdots +F_{n} )-F_2\\&=\cfrac{1}{\sqrt{5}}\left[\left(\cfrac{1+\sqrt{5}}{2}\right)^{n+2}-\left(\cfrac{1-\sqrt{5}}{2}\right)^{n+2}\right]-1 \end{align} 即 F_{1} +F_{2} +\cdots +F_{n} =F_{n+2} -1 成立。2、奇数项求和F_{1}+F_{3}+F_{5}+F_{7}+\cdots+F_{2 n-1}=F_{2 n} \\证明：\begin{aligned} F_{2 n} &=F_{2 n-1}+F_{2 n-2} \\ &=F_{2 n-1}+F_{2 n-3}+F_{2 n-4} \\ &=F_{2 n-1}+F_{2 n-3}+F_{2 n-5}+F_{2 n-6} \\ &=F_{2 n-1}+F_{2 n-3}+F_{2 n-5}+\ldots+F_{4} \\ &=F_{2 n-1}+F_{2 n-3}+F_{2 n-5}+\ldots+F_{3}+F_{2} \\ &=F_{2 n-1}+F_{2 n-3}+F_{2 n-5}+\ldots+F_{3}+F_{1} \end{aligned} \\3、 偶数项求和F_{2}+F_{4}+F_{6}+F_{8}+\cdots+F_{2 n}=F_{2 n+1}-1 \\证明：\begin{aligned} F_{2 n+1} &=F_{2 n}+F_{2 n-1} \\ &=F_{2 n}+F_{2 n-2}+F_{2 n-3} \\ &=F_{2 n}+F_{2 n-2}+F_{2 n-4}+F_{2 n-5} \\ &=F_{2 n}+F_{2 n-2}+F_{2 n-4}+\ldots+F_{4}+F_{3} \\ &=F_{2 n}+F_{2 n-2}+F_{2 n-4}+\ldots+F_{4}+F_{2}+F_{1} \end{aligned} \\移项便得到证明。4、 平方求和F_{1}^{2}+F_{2}^{2}+F_{3}^{2}+F_{4}^{2}+\cdots+F_{n}^{2}=F_{n} \cdot F_{n+1} \\证明：\begin{aligned} F_{n} \cdot F_{n+1} &=F_{n}\left(F_{n}+F_{n-1}\right)=F_{n}^{2}+F_{n-1} F_{n} \\ &=F_{n}^{2}+F_{n-1}\left(F_{n-1}+F_{n-2}\right)=F_{n}^{2}+F_{n-1}^{2}+F_{n-2} F_{n-1} \\ &=F_{n}^{2}+F_{n-1}^{2}+\ldots+F_{2}^{2}+F_{1} F_{2} \\ &=F_{n}^{2}+F_{n-1}^{2}+\ldots+F_{2}^{2}+F_{1}^{2} \end{aligned} \\五、一些重要恒等式 (1) 当 n \geq 0,n\in \mathbb{Z^{+}}时F_{1} +F_{2} +\cdots +F_{n} =F_{n+2} -1 \\ (2) 当 n \geq 0,n\in \mathbb{Z^{+}}时F_{2} + F_{4} +\cdots +F_{2n} = F_{2n+1} \\ (3) 当m, n \geq 0,则F_{m+n}=F_{m} F_{n}+F_{m-1} F_{n-1} \\ (4) 当n \geq 0,则\left(\begin{array}{c} n \\ 0 \end{array}\right)+\left(\begin{array}{c} n-1 \\ 1 \end{array}\right)+\left(\begin{array}{c} n-2 \\ 2 \end{array}\right)+\cdots=F_{n}\\ (5) 当n \geq 0,则\sum_{i \geq 0} \sum_{j \geq 0}\left(\begin{array}{c} n-i \\ j \end{array}\right)\left(\begin{array}{c} n-j \\ i \end{array}\right)=F_{2 n+1}\\ (6) 当n \geq 0,则F_{2 n-1}=\sum_{k=1}^{n}\left(\begin{array}{l} n \\ k \end{array}\right) F_{k-1}\\ (7) 当n \geq 4,则F_{n}^{3}+3 F_{n-3}^{3}+F_{n-4}^{3}=3 F_{n-1}^{2}+6 F_{n-2}^{3}\\ (8) 当n \geq 1,则F_{n}^{2}=F_{n+1} F_{n-1}+(-1)^{n} \\ (9) 当n \geq 0,则\sum_{k=0}^{n} F_{k}^{2}=F_{n} F_{n+1} \\ (10) 当n \geq 0,则F_{n}+F_{n-1}+\sum_{k=0}^{n-2}F_{k} 2^{n-2-k}=2^{n} \\ (11) 当m, p, t \geq 0,则F_{m+(t+1) p}=\sum_{i=0}^{p}\left(\begin{array}{l} p \\ i \end{array}\right) F_{t}^{i} F_{t-1}^{p-i} F_{m+i}\\ (12) 当n \geq 1, 则F_{1}+F_{3}+\cdots+F_{2 n-1}=F_{2 n}-1 \\ (13) 当n \geq 0, 则F_{n}^{2}+F_{n+1}^{2}=F_{2 n+2} \\ (14) 当n \geq 1, 则F_{n}^{2}-F_{n-2}^{2}=F_{2 n-1} \\ (15) 当n \geq 0, 则F_{2 n+2}=F_{n+1} F_{n+2}-F_{n-1} F_{n} \\ (16) 当n \geq 2, 则2 F_{n}=F_{n+1}+F_{n-2} \\ (17) 当n \geq 2, 则3 F_{n}=F_{n+2}+F_{n-2} \\ (18) 当n \geq 2, 则4 F_{n}=F_{n+2}+F_{n}+F_{n-2} \\ (19) 当n \geq 1, 则\left(F_{n-1} F_{n+2}\right)^{2}+\left(2 F_{n} F_{n+1}\right)^{2}=\left(F_{n+1} F_{n+2}-F_{n-1} F_{n}\right)^{2}=\left(F_{2 n+2}\right)^{2} \\ (20) 当 n \geq p,则F_{n+p}=\sum_{i=0}^{p}\left(\begin{array}{l}p \\ i\end{array}\right) F_{n-i} \\ (21) 当n \geq 0,则\sum_{k=0}^{n}(-1)^{k} F_{k}=1+(-1)^{n} F_{n-1} \\ (22) 当n \geq 0, 则\prod_{k=1}^{n}\left(1+\frac{(-1)^{k+1}}{F_{k}^{2}}\right)=\frac{F_{n+1}}{F_{n}} \\ (23) 当n \geq 0, 则F_{0}+F_{3}+F_{6}+\cdots+F_{3 n}=\frac{1}{2} F_{3 n+2} \\ (24) 当n \geq 1, 则F_{1}+F_{4}+F_{7}+\cdots+F_{3 n-1}=\frac{1}{2}\left(F_{3 n+1}-1\right) \\ (25) 当n \geq 1, 则F_{2}+F_{5}+F_{8}+\cdots+F_{3 n-2}=\frac{1}{2}\left(F_{3 n}-1\right) \\ (26) 当n \geq 0, 则F_{0}+F_{4}+F_{8}+\cdots+F_{4 n}=F_{2 n} F_{2 n+1} \\ (27) 当n \geq 1, 则F_{1}+F_{5}+F_{9}+\cdots+F_{4 n-3}=F_{2 n-1}^{2} \\ (28) 当n \geq 1, 则F_{2}+F_{6}+F_{10}+\cdots+F_{4 n-2}=F_{2 n-1} F_{2 n} \\ (29) 当n \geq 1, 则F_{3}+F_{7}+F_{11}+\cdots+F_{4 n-1}=F_{2 n-1} F_{2 n+1} \\ (30) 当n \geq 1, 则F_{n+3}^{2}+F_{n}^{2}=2 F_{n+1}^{2}+2 F_{n+2}^{2} \\ (31) 当n \geq 1, 则F_{n}^{4}=F_{n+2} F_{n+1} F_{n-1} F_{n-2}+1 \\(32) 当n \geq 0, 则 F_{1}+2 F_{2}+\cdots+n F_{n}=(n+1) F_{n+2}-F_{n+4}+3 \\（本内容收集整理于网络，放在这里备忘，如有错误请指正。）编辑于 2023-11-24 07:58・IP 属地甘肃斐波那契（Leonardo Fibonacci）数列斐波拉契数列​赞同 103​​6 条评论​分享​喜欢​收藏​申请

斐波那契_百度百科

_百度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心斐波那契播报讨论上传视频中世纪意大利数学家收藏查看我的收藏0有用+10斐波那契（Leonardo Pisano ,Fibonacci, Leonardo Bigollo，1175年-1250年），中世纪意大利数学家，是西方第一个研究斐波那契数的人，并将现代书写数和乘数的位值表示法系统引入欧洲。其写于1202年的著作《计算之书》中包含了许多希腊、埃及、阿拉伯、印度、甚至是中国数学相关内容。 [1]中文名斐波那契外文名Leonardo Pisano, Fibonacci, Leonardo Bigollo国    籍意大利出生日期1175年逝世日期1250年职    业数学家主要成就斐波那契数列代表作品《算盘全书》、《计算之书》父    亲Guilielmo（威廉）目录1人物背景▪家庭▪学习▪成就2人物轶事▪数列▪质数▪C计算代码3重要作品人物背景播报编辑家庭列奥纳多的父亲名为Guilielmo（威廉），外号Bonacci（意即「好、自然」或「简单」）。威廉是商人，在北非一带工作（今阿尔及利亚Bejaia），当时年轻的列奥纳多已经开始协助父亲工作，他学会了阿拉伯数字。学习有感使用阿拉伯数字比罗马数字更有效，列奥纳多前往地中海一带向当时著名的阿拉伯数学家学习，约于1200年回国。1202年，27岁的他将其所学写进《计算之书》（Liber Abaci）。这本书通过在记账、重量计算、利息、汇率和其他的应用，显示了新的数字系统的实用价值。这本书大大影响了欧洲人的思想，可是在三世纪后印制术发明之前，十进制数字并不流行。（例子：1482年，Ptolemaeus世界地图 ，Lienhart Holle在Ulm印制）成就列奥纳多曾成为热爱数学和科学的腓特烈二世(神圣罗马帝国的皇帝)的座上客。欧洲数学在希腊文明衰落之后长期处于停滞状态，直到12世纪才有复苏的迹象。这种复苏开始是受了翻译、传播希腊、阿拉伯著作的刺激。对希腊与东方古典数学成就的发掘、探讨，最终导致了文艺复兴时期（15～16世纪）欧洲数学的高涨。文艺复兴的前哨意大利，由于其特殊地理位置与贸易联系而成为东西方文化的熔炉。意大利学者早在12～13世纪就开始翻译、介绍希腊与阿拉伯的数学文献。在欧洲，黑暗时代以后第一位有影响的数学家斐波那契（约1175年～1250年），其拉丁文代表著作《计算之书》（Liber Abaci）和《几何实践》（Practica Geometriae）也是根据阿拉伯文与希腊文材料编译而成的，斐波那契即比萨的列奥纳多（Leonardo of Pisa），早年随父在北非从师阿拉伯人习算，后又游历地中海沿岸诸国，回意大利后即写成《计算之书》（Liber Abaci，1202，亦译作《算盘算经》）。《计算之书》最大的功绩是系统介绍印度记数法，影响并改变了欧洲数学的面貌。现传《算经》是1228年的修订版，其中还引进了著名的“斐波那契数列”。《几何实践》（Practica Geometriae， 1220）则着重叙述希腊几何与三角术。斐波那契其他数学著作还有《平方数书》（Liber Quadratorum，1225）、《花朵》（Flos，1225）等，前者专论二次丢番图方程，后者内容多为腓特烈二世（Frederick II）宫廷数学竞赛问题，其中包含一个三次方程/十2x2十10x～－20求解，斐波那契论证其根不能用尺规作出（即不可能是欧几里得的无理量），他还未加说明地给出了该方程的近似解（J一1.36880810785）。微积分的创立与解析几何的发明标志着文艺复兴后欧洲近代数学的兴起。微积分的思想根源部分（尤其是积分学）可以追溯到古代希腊、中国和印度人的著作。在牛顿和莱布尼茨最终制定微积分以前，又经过了近一个世纪的酝酿。在这个酝酿时期对微积分有直接贡献的先驱者包括开普勒、卡瓦列里、费马、笛卡尔、沃利斯和巴罗（1．Barrow，1630年～1677年）等一大批数学家。人物轶事播报编辑数列兔子问题斐波那契在《计算之书》中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有的兔子都不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔总数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；……依次类推可以列出下表：经过月数0123456789101112总体对数01123581321345589144兔子问题表中数字1，1，2，3，5，8－－－构成了一个序列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。这个数列是意大利中世纪数学家斐波那契在《计算之书》中提出的，这个级数的通项公式，除了具有an+2=an+an+1的性质外，还可以证明通项公式为：an=1/√5 [（1/2+√5/2）^ n-（1/2-√5/2）^n](n=1,2,3.....)（√5表示根号 5）。这个通项公式中虽然所有的an都是正整数，可是它们却是由一些无理数表示出来的。即在较高的序列，两个连续的“斐波纳契数”的序列相互分割将接近黄金比例（1.618:1或1:0.618）。例如：233/144，987/610……斐波那契数列还有两个有趣的性质：兔子问题⒈斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1；⒉任取相邻的四个斐波那契数，中间两数之积（内积）与两边两数之积（外积）相差1。质数斐波那契质数由斐波那契序列中的质数组成，是整数质数序列。第一组质数序列是：2，3，5，13，89，233，1597，28657，514229，433494437，2971215073……C计算代码1.

#include 

int fib(int x)

{

    if(x==1 || x==2)

    {

        return 1;

    }

    else

    {

        return fib(x-1)+fib(x-2);

    }

}

int main()

{

    int n=0;

    scanf("%d",&n);

    printf("%d",fib(n));

}

2.

#include 

int fib[1000001]={0,1,1};

int main()

{

    int n=0;

    scanf("%d",&n);

    for(int i=3;i<=n;i++)

    {

        fib[i]=fib[i-1]+fib[i-2];

    }

    printf("%d",fib[n]);

    return 0;

}重要作品播报编辑Liber Abaci（计算之书，1202年）。Practica Geometriae（几何实践，1220年）。Flos（花朵，1225年），Johannes of Palermo提出的问题的答案。Liber quadratorum（平方数书）关于丢番图方程的问题on Diophantine problems,that is,problems involving Diophantine equations.Di minor guisa（关于商业运算；已佚）《几何原本》第十卷的注释（已佚）拉丁文代表著作《珠算原理》新手上路成长任务编辑入门编辑规则本人编辑我有疑问内容质疑在线客服官方贴吧意见反馈投诉建议举报不良信息未通过词条申诉投诉侵权信息封禁查询与解封©2024 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号 京公网安备110000020000

斐波纳契数列 - 知乎

斐波纳契数列 - 知乎首页知乎知学堂发现等你来答​切换模式登录/注册斐波纳契数列斐波纳契数列（Fibonacci sequence）是数学界十分著名的数列，小说《达芬奇密码》中，卢浮宫馆长被人杀害陈尸在地板上，馆长脱光了衣服，摆成达·芬奇名画维特鲁威人并且留下了一些奇怪的密码…查看全部内容关注话题​管理​分享​百科讨论精华视频等待回答详细内容概述内容斐波纳契数列（Fibonacci sequence）是数学界十分著名的数列，小说《达芬奇密码》中，卢浮宫馆长被人杀害陈尸在地板上，馆长脱光了衣服，摆成达·芬奇名画维特鲁威人并且留下了一些奇怪的密码。这些让人难以琢磨的密码就是斐波纳契数列。其前几项是1，1，2，3，5，8，13，21，34，55，89，144·······，这个数列最大特点就是其中每一项都等于其前两项的和。从第三个数起，每个数与它后面那个数的比值，都很接近于0.618，正是“黄金分割”。斐波那契数列又称“兔子数列”、黄金分割数列。这个看上去很简单的数列，却总是出现在人们的眼前。蜻蜓翅膀、蜂巢、菠萝表面的突起等，都是按照这个数列排列的。许多花朵的花瓣数目也具有斐波纳契数列的排列规律，如玫瑰、菊花、向日葵等。斐波纳契和斐波纳契数列中世纪西欧经济开始繁荣，西方商人到东方经商的逐渐增多，意大利数学家斐波纳契就是其中的一位。斐波纳契这个名字其实是生活于12世纪末至13世纪上半叶的比萨的莱奥纳多的绰号，因为莱奥纳多的父亲名叫Guilielmo，外号Bonacci，而Fibonacci意即Bonacci之子。 他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团队聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，莱昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。斐波纳契斐波纳契在1202年所著、1228年修订再版的《算法之书》中提出了一个著名的兔子问题，大意是：若有一对幼兔，第二年长成年，第三年开始每年产下一对幼兔；所生每对幼兔也在第二年成年，第三年开始每年产下一对幼兔；依此类推，假定每次产下的幼兔都是一雌一雄，也没有生病和死亡，这样得到的每年存栏的兔子对数： u(1) = 1, u(2) = 1, u(3) =2, u(4) =3, u(5)=5, u(6) =8,······称为斐波纳契数列。设u(0) =0，则u(k)满足递推关系 u(k+2) = u(k) +u(k+1)，k= 0,1,2,···以及初始条件：u(0) =0，u(1) = 1。兔子和斐波纳契数列19世纪法国数学家比内（公元1786-1856）首先提出了斐波纳契数列的通项公式，故命名为比内公式：比内公式自然界中的斐波纳契数列不但兔子的生育遵循着斐波纳契数列的规律，自然界中树枝的分岔、植物的花瓣数目也符合这个数列的规律。有一位学者一片片的数过一朵重瓣芍药花的花瓣，最后得到的结果是233瓣, 233正好是斐波纳契数列中的一项。还有一位中学生物教师，采得一棵松塔， 剥去鳞片数其片数，最后数得的鳞片数目是144片，这一结果仍在斐波纳契数列内。植物学家在研究植物“叶序”（枝、叶及种子在植株上的排列与分布）时发现斐波纳契数列仍亦起着重要的作用。如向日葵的花盘，从花盘中心向外辐射出来的对数螺线弧把花盘分割成含有花籽的菱形小块，我们会发现顺时针方向伸展的螺线数目与逆时针方向伸展的螺线数目的比值一般是13/21、21/34、34/55或55/144。每个比值的分子，分母都是斐波那契数列中相邻的两项。显然，其比值的分子、分母的数值越大时，种子越多，向日葵的品种相对也较好。如此的原因很简单：这样的布局能使植物的生长疏密得当、最充分地利用阳光和空气，所以很多植物都在亿万年的进化过程中演变成了如今的模样。当然受气候或病虫害的影响，真实的植物往往没有完美的斐波纳契螺旋。向日葵的生长任何菊科植物如雏菊、翠菊等的花盘也都具有以上所述的特性，只是因为菊科植物花盘较小，不容易得到验证。但植物学家还是测算出了菊科植物延命菊花头状花序上的两族反向螺线条数的比是21/34。杉属植物的球果中出现的比值是5/8、8/13。我们观察莴头上的叶子，洋葱的层次，松果的圆锥螺线（两条反向螺线数目的比是5:8）及菠萝上瘤状物排列数目（8: 13）等,都可以看到上述相似的排列形式。“鲁德维格定律”斐波纳契螺旋线斐波纳契弧线也叫“黄金螺线”，第一，此趋势线以两个端点为准而画出，例如，最低点反向到最高点线上的两个点。三条弧线均以第二个点为中心画出，并在趋势线的斐波纳契水平: 38.2%，50%和61.8%交叉。斐波纳契弧线，是潜在的支持点和阻力点水平价格。斐波纳契弧线和斐波纳契扇形线常常在图表里同时绘画出。支持点和阻力点就是由这些线的交会点得出。要注意的是弧线的交叉点和价格曲线会根据图表数值范围而改变，因为弧线是圆周的一部分， 略它的形成总是一样的。黄金螺线将黄金螺线运用在摄影，能提高拍摄出出众的相片的几率。相对于三分法这个静态的方法，黄金螺线在我们用眼睛捕捉画面时提供了一个流动的线条。黄金螺线总在你的两面之内旋转，从顶部到底部，它可以使你的画面的构图更加的富于变化。总之，斐波纳契数列存在我们生活中的许多地方，虽然已有许多被我们所发现，但也许有更多的还有待我们去发现，与斐波纳契数列密切相关的黄金比例被运用在方方面面，但仍有待我们继续探索。参考文献：邱森，《线性代数探究性课题精编》，武汉大学出版社， 2011.Keith Ball,Strange Curves, Counting Rabbits, and other Mathematical Explorations,上海科技教育出版社; 第1版 (2011年12月5日).郭德才. 不可思议的斐波纳契数列[J]. 发明与创新:综合版, 2007(11):24-25.方陵生. 大自然中的斐波纳契数列之奇[J]. 科学与文化, 2004(9):19-20.罗文军. 数列中的一颗璀璨的明珠——斐波那契数列[J]., 2017(6).百科摘录1「知乎知识库」— 斐波纳契数列下的内容摘录einmal01斐波纳契数列（Fibonacci sequence）是数学界十分著名的数列，小说《达芬奇密码》中，卢浮宫馆长被人杀害陈尸在地板上，馆长脱光了衣服，摆成达·芬奇名画维特鲁威人并且留下了一些奇怪的密码。这些让人难以琢磨的密码就是斐波纳契数列。其前几项是1，1，2，3，5，8，13，21，34，55，89，144·······，这个数列最大特点就是其中每一项都等于其前两项的和。从第三个数起，每个数与它后面那个数的比值，都很接近于0.618，正是“黄金分割”。斐波那契数列又称“兔子数列”、黄金分割数列。这个看上去很简单的数列，却总是出现在人们的眼前。蜻蜓翅膀、蜂巢、菠萝表面的突起等，都是按照这个数列排列的。许多花朵的花瓣数目也具有斐波纳契数列的排列规律，如玫瑰、菊花、向日葵等。冯不悔 摘录于 2019-11-25浏览量308 万讨论量2741  帮助中心知乎隐私保护指引申请开通机构号联系我们 举报中心涉未成年举报网络谣言举报涉企虚假举报更多 关于知乎下载知乎知乎招聘知乎指南知乎协议更多京 ICP 证 110745 号 · 京 ICP 备 13052560 号 - 1 · 京公网安备 11010802020088 号 · 京网文[2022]2674-081 号 · 药品医疗器械网络信息服务备案（京）网药械信息备字（2022）第00334号 · 广播电视节目制作经营许可证:（京）字第06591号 · 服务热线：400-919-0001 · Investor Relations · © 2024 知乎 北京智者天下科技有限公司版权所有 · 违法和不良信息举报：010-82716601 · 举报邮箱：jubao@zhihu.

斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？ - 知乎

斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？ - 知乎首页知乎知学堂发现等你来答​切换模式登录/注册数学算法设计数列数学学习斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？关注者1,397被浏览916,365关注问题​写回答​邀请回答​好问题 13​添加评论​分享​27 个回答默认排序知乎用户​数学话题下的优秀答主一句话先回答问题：因为斐波那契数列在数学和生活以及自然界中都非常有用。下面我就尽我所能，讲述一下斐波那契数列。一、起源和定义斐波那契数列最早被提出是印度数学家Gopala，他在研究箱子包装物件长度恰好为1和2时的方法数时首先描述了这个数列。也就是这个问题：有n个台阶，你每次只能跨一阶或两阶，上楼有几种方法？而最早研究这个数列的当然就是斐波那契（Leonardo Fibonacci）了，他当时是为了描述如下情况的兔子生长数目：第一个月初有一对刚诞生的兔子第二个月之后（第三个月初）它们可以生育每月每对可生育的兔子会诞生下一对新兔子兔子永不死去这个数列出自他赫赫有名的大作《计算之书》（没有维基词条，坑），后来就被广泛的应用于各种场合了。这个数列是这么定义的：The On-Line Encyclopedia of Integer Sequences® (OEIS®)序号为A000045 - OEIS（注意，并非满足第三条的都是斐波那契数列，卢卡斯数列（A000032 - OEIS）也满足这一特点，但初始项定义不同）二、求解方法讲完了定义，再来说一说如何求对应的项。斐波那契数列是编程书中讲递归必提的，因为它是按照递归定义的。所以我们就从递归开始讲起。1.递归求解int Fib(int n)

{

return n < 2 ? 1 : (Fib(n-1) + Fib(n-2));

}这是编程最方便的解法，当然，也是效率最低的解法，原因是会出现大量的重复计算。为了避免这种情况，可以采用递推的方式。2.递推求解int Fib[1000];

Fib[0] = 0;Fib[1] = 1;

for(int i = 2;i < 1000;i++) Fib[i] = Fib[i-1] + Fib[i-2];递推的方法可以在O(n)的时间内求出Fib(n)的值。但是这实际还是不够好，因为当n很大时这个算法还是无能为力的。接下来就要来讲一个有意思的东西：矩阵。3.矩阵递推关系学过代数的人可以看出，下面这个式子是成立的：\begin{bmatrix}

Fib(n+1) \\

Fib(n)

\end {bmatrix}

=\begin{bmatrix}

1&1 \\

1&0

\end{bmatrix}

\begin{bmatrix}

Fib(n) \\

Fib(n-1)

\end{bmatrix}不停地利用这个式子迭代右边的列向量，会得到下面的式子：\begin{bmatrix}

Fib(n+1) \\

Fib(n)

\end {bmatrix}

=\begin{bmatrix}

1&1 \\

1&0

\end{bmatrix}^{n}

\begin{bmatrix}

Fib(1) \\

Fib(0)

\end{bmatrix}这样，问题就转化为如何计算这个矩阵的n次方了，可以采用快速幂的方法。快速幂_百度百科是利用结合律快速计算幂次的方法。比如我要计算2^{20} ，我们知道2^{20} = 2^{16} * 2^{4} ，而2^{2} 可以通过2^{1} \times 2^{1} 来计算，2^{4} 而可以通过2^{2}\times 2^{2} 计算，以此类推。通过这种方法，可以在O（lbn）的时间里计算出一个数的n次幂。快速幂的代码如下：int Qpow(int a,int n)

{

int ans = 1;

while(n)

{

if(n&1) ans *= a;

a *= a;

n >>= 1;

}

return ans;

}

将上述代码中的整型变量a变成矩阵，数的乘法变成矩阵乘法，就是矩阵快速幂了。比如用矩阵快速幂计算斐波那契数列：#include

#include

using namespace std;

const int MOD = 10000;

struct matrix//定义矩阵结构体

{

int m[2][2];

}ans, base;

matrix multi(matrix a, matrix b)//定义矩阵乘法

{

matrix tmp;

for(int i = 0; i < 2; ++i)

{

for(int j = 0; j < 2; ++j)

{

tmp.m[i][j] = 0;

for(int k = 0; k < 2; ++k)

tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;

}

}

return tmp;

}

int fast_mod(int n) // 求矩阵 base 的 n 次幂

{

base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;

base.m[1][1] = 0;

ans.m[0][0] = ans.m[1][1] = 1; // ans 初始化为单位矩阵

ans.m[0][1] = ans.m[1][0] = 0;

while(n)

{

if(n & 1) //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t

ans = multi(ans, base);

base = multi(base, base);

n >>= 1;

}

return ans.m[0][1];

}

int main()

{

int n;

while(scanf("%d", &n) && n != -1)

{

printf("%d\n", fast_mod(n));

}

return 0;

}

4.通项公式无论如何，对于一个数列，我们都是希望可以建立F(n)与n的关系，也就是通项公式，而用不同方法去求解通项公式也是很有意思的。（1）构造等比数列设f(n) + \alpha f(n-1) = \beta [f(n-1) + \alpha f(n-2)],化简得f(n)=(\beta -\alpha )f(n-1)+\alpha \beta f(n-2),比较系数得\beta -\alpha =1,\alpha \beta =1，解得\alpha =\frac{\sqrt{5}-1 }{2} ，\beta =\frac{\sqrt{5}+1 }{2} 由于f(n+1)+\alpha f(n)=[f(2)+\alpha f(1)]\beta ^{n-1} =\beta ^{n} 故有\frac{f(n+1)}{\beta ^{n+1}} +\frac{\alpha}{\beta } \frac{f(n)}{\beta ^{n} } =\frac{1}{\beta } ，设g(n)=\frac{f(n)}{\beta ^{n}} .则有g(n+1)+\frac{\alpha }{\beta } g(n)=\frac{1}{\beta } ,设g(n+1)+\lambda =-\frac{\alpha }{\beta } (g(n)+\lambda ),解得\lambda =-\frac{1}{\alpha +\beta } ，即{g(n)+\lambda }是等比数列。这样就有g(n)+\lambda=(-\frac{\alpha }{\beta } )^{n-1} (\frac{1}{\beta } +\lambda )到了现在，把上述解出的结果全部带入上式，稍作变形，我们就可以写出斐波那契数列的通项公式了f(n)=\frac{1}{\sqrt{5} } [(\frac{1+\sqrt{5} }{2} )^{n}-(\frac{1-\sqrt{5} }{2} )^{n}]这个方法还是比较麻烦的，但是非常基础。事实上还有其他更简单的方法。（2）线性代数解法这个解法首先用到\begin{bmatrix}

Fib(n+1) \\

Fib(n)

\end {bmatrix}

=\begin{bmatrix}

1&1 \\

1&0

\end{bmatrix}^{n}

\begin{bmatrix}

Fib(1) \\

Fib(0)

\end{bmatrix}公式，如果可以找到矩阵P使得PAP^{-1}为对角阵，我们就可以求出通项。下面需要一些高等代数知识，没学过的可直接跳过。首先令|\lambda E-A|=0,解得两个特征根\lambda_{1}=\frac{1-\sqrt{5} }{2} ,

\lambda_{2}=\frac{1+\sqrt{5} }{2} 两个特征向量为\alpha _{1}=[1,\frac{1+\sqrt{5} }{2} ] ^{T},\alpha _{2}=[1,\frac{-1+\sqrt{5} }{2} ] ^{T},则P=\begin{bmatrix}

1&1 \\

\frac{1+\sqrt{5}}{2} & \frac{\sqrt{5}-1}{2}

\end{bmatrix},

P^{-1}=\begin{bmatrix}

\frac{1-\sqrt{5}}{2}&1 \\

\frac{1+\sqrt{5}}{2}&-1

\end{bmatrix}而(PAP^{-1})^{n}=PAP^{-1}PAP^{-1}...PAP^{-1}=PA(P^{-1}P)A(P^{-1}P)A...AP^{-1}=PA^{n}P^{-1}解出A^{n}=P^{-1}(PAP^{-1})^{n}P,中间矩阵的n次方可以直接求出来：\begin{bmatrix}

\frac {1-\sqrt{5}}{2}&0 \\

0&\frac {1+\sqrt{5}}{2}

\end{bmatrix}^{n}=

\begin{bmatrix}

(\frac {1-\sqrt{5}}{2})^{n}&0\\

0&(\frac {1+\sqrt{5}}{2})^n

\end{bmatrix}然后可以轻易得到通项公式，上边已经给出，这里不再赘述。（3）特征方程解法通过方法（2），我们可以推导出一般的线性递推数列的通项求解方法，也就是特征方程法。我们可以发现，对于这种数列，通项总是可以表示为f(n)=C_{1} \lambda _{1}^{n} +C_{2} \lambda _{2}^{n}的形式，因此可以直接利用已知项求解C_{1}，C_{2} 。具体做法如下：a.由递推数列构造特征方程x^{2}=x+1，解出两个特征值\lambda_{1}=\frac{1-\sqrt{5} }{2} ,

\lambda_{2}=\frac{1+\sqrt{5} }{2} 。b.带入f(0),f(1),列出如下方程：C_{1} +C_{1} =0\frac{1-\sqrt{5} }{2} C_{1} +\frac{1+\sqrt{5} }{2} C_{2} =1解得C_{1} =-\frac{1}{\sqrt{5} } ,C_{2} =\frac{1}{\sqrt{5} } .这样直接写出通项公式，是比较简单的做法。（4）母函数法（此方法涉及组合数学知识）设斐波那契数列的母函数为G(x),即G(x)=F_{0} +F_{1}x+F_{2}x^{2}+L+F_{n}x^{n}=1+x+(F_{0}+F_{1})x^{2}+L+(F_{n-1} +F_{n-2})x^{n}=1+(x+F_{1}x^{2}+F_{2}x^{3}+L+)+(F_{0}x^{2}+F_{1}x^3+L)=1+(x+x^{2})G(x)解得G(x)=\frac{1}{1-x-x^{2}} =\frac{1}{\sqrt{5} } \frac{1+\sqrt{5} }{2}\frac{1}{1-\frac{1+\sqrt{5} }{2}x} -\frac{1}{\sqrt{5} } \frac{1-\sqrt{5} }{2}\frac{1}{1-\frac{1-\sqrt{5} }{2}x}再由幂级数展开公式\frac{1}{1-x}=1+x+x^{2}+……合并同类项并与G(x)的系数比较即可。到这里，求解斐波那契数列通项的方法就说的差不多了。无论是计算机求解还是数学推导，都体现出了非常多的技巧。而斐波那契数列的许多特性，就更加有意思了。三、斐波那契数列的数学性质1.与黄金比的关系由通项公式，求相邻两项的商的极限，结果是黄金比，所以斐波那契数列又称为黄金比数列。斐波那契数列和黄金比还和一个有趣的数学概念——连分数有关：2.一些简单的规律（1）任意连续四个斐波那契数，可以构造出一个毕达哥拉斯三元组。如取1,1,2,3.中间两数相乘再乘2 ==》 4外层2数乘积==》3中间两数平方和==》5得到3,4,5.下一组是5,12,13,，有兴趣的读者可以再试着推一推，证明也是容易的。（2）整除性每3个连续的斐波那契数有且只有一个被2整除，每4个连续的斐波那契数有且只有一个被3整除，每5个连续的斐波那契数有且只有一个被5整除，每6个连续的斐波那契数有且只有一个被8整除，每7个连续的斐波那契数有且只有一个被13整除，…………每n个连续的斐波那契数有且只有一个被f(n)整除.（3）一些恒等式3.杨辉三角中的斐波那契数列如图所示，每条斜线上的数的和就构成斐波那契数列。即有f(n)=C_{n-1}^{0} +C_{n-2}^{1}+L+C_{n-1-m}^{m}4.相关数列：卢卡斯（Lucas）数列卢卡斯数列的定义除了第0项为2之外，与斐波那契数列完全一致。即其通项公式为：卢卡斯数列和斐波那契数列有这些关系：F_{2n}=F_{n}L_{n} 5F_{n}=L_{n-1}+L_{n+1}L_{n}^{2}=5 F_{n}^{2}+4(-1)^{n}\lim_{n \rightarrow \infty }{\frac{L_{n}}{F_{n}} } =\sqrt{5} L_{n}=F_{n-1}+F_{n+1}5.组合数学（1）一些恒等式（2）同余特性(F(m),F(n))=(m,n)F(m)|F(n)\Leftrightarrow m|n当p为大于5的素数时，有：F(p-(\frac{p}{5}))\equiv 0(modp) F(p)\equiv (\frac{p}{5}) (modp) F(p+(\frac{p}{5}))\equiv 1(modp) 其中斐波那契数列还有许许多多的性质，我就不再一一介绍了。跑题了这么久，终于开始要真正回答问题了：斐波那契数列有什么用？四、斐波那契数列的应用1.算法a.斐波那契堆斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质，可用于实现合并优先队列。特点是不涉及删除元素的操作有O(1)的平摊时间，用途包括稠密图每次Decrease－key只要O(1)的平摊时间，和二项堆的O(lgn)相比是巨大的改进。斐波那契堆由一组最小堆构成，这些最小堆是有根的无序树。可以进行插入、查找、合并和删除等操作1）插入：创建一个仅包含一个节点的新的斐波纳契堆，然后执行堆合并2）查找：由于用一个指针指向了具有最小值的根节点，因此查找最小的节点是平凡的操作。3）合并：简单合并两个斐波纳契堆的根表。即把两个斐波纳契堆的所有树的根首尾衔接并置。4）删除（释放）最小节点分为三步：查找最小的根节点并删除它，其所有的子节点都加入堆的根表，即它的子树都成为堆所包含的树；需要查找并维护堆的最小根节点，但这耗时较大。为此，同时完成堆的维护：对堆当前包含的树的度数从低到高，迭代执行具有相同度数的树的合并并实现最小树化调整，使得堆包含的树具有不同的度数。这一步使用一个数组，数组下标为根节点的度数，数组的值为指向该根节点指针。如果发现具有相同度数的其他根节点则合并两棵树并维护该数组的状态。对当前堆的所有根节点查找最小的根节点。5）降低一个点的键值：对一个节点的键值降低后，自键值降低的节点开始自下而上的迭代执行下述操作，直至到根节点或一个未被标记（marked）节点为止：如果当前节点键值小于其父节点的键值，则把该节点及其子树摘下来作为堆的新树的根节点；其原父节点如果是被标记（marked）节点，则也被摘下来作为堆的新树的根节点；如果其原父节点不是被标记（marked）节点且不是根节点，则其原父节点被加标记。如果堆的新树的根节点被标记（marked），则去除该标记。6）删除节点：把被删除节点的键值调整为负无穷小，然后执行“降低一个节点的键值”算法，然后再执行“删除最小节点”算法。斐波那契堆b.欧几里得算法的时间复杂度欧几里得算法是求解两个正整数最大公约数的算法，又称辗转相除法。代码如下：int gcd(int a,int b)

{

return b ? gcd(b,a%b) : a;

}在最坏的情况下，我们可以证明，若a较小，需要计算的次数为n，则a>F(n-1).虽然说一般分析的时候会当成对数阶，但数论最常用的欧几里得算法竟然与斐波那契数列有关，也确实是很让人吃惊呢。2.物理学：氢原子能级问题假定我们现在有一些氢气原子，一个电子最初所处的位置是最低的能级（Ground lever of energy），属于稳定状态。它能获得一个能量子或二个能量子（Quanta of energy）而使它上升到第一能级或者第二能级。但是在第一级的电子如失掉一个能量子就会下降到最低能级，它如获得一个能量子就会上升到第二级来。现在研究气体吸收和放出能量的情形，假定最初电子是处在稳定状态即零能级，然后让它吸收能量，这电子可以跳到第1能级或第2能级。然后再让这气体放射能量，这时电子在1级能级的就要下降到0能级，而在第2能级的可能下降到0能级或者第1能级的位置去。电子所处的状态可能的情形是：1、2、3、5、8、13、21…种。这是斐波那契数列的一部份。3.自然界：植物的生长科学家发现，一些植物的花瓣、萼片、果实的数目以及排列的方式上，都有一个神奇的规律，它们都非常符合著名的斐波那契数列。例如：蓟，它们的头部几乎呈球状。在下图中，你可以看到两条不同方向的螺旋。我们可以数一下，顺时针旋转的（和左边那条旋转方向相同）螺旋一共有13条，而逆时针旋转的则有21条。此外还有菊花、向日葵、松果、菠萝等都是按这种方式生长的。还有菠萝、松子等，也都符合这个特点，一般会出现34,55，89和144这几个数字。最后上一张“斐波那契树”的图片：是的，这玩意就长这样，这种植物是存在的。4.波浪理论与股市这个答主不懂，大家可自行阅读文章波浪理论斐波那契数列与黄金分割率。不过波浪的形状确实符合下边要说的斐波那契螺旋：5.斐波那契螺旋斐波那契螺旋又称黄金螺旋，在自然界中广泛存在。如图是一个边长为斐波那契数列的正方形组成的矩形。（加一句：看着这个图，是不是能发现是显而易见的？）这样连起来就是斐波那契螺旋了贝壳螺旋轮廓线向日葵的生长神奇的花6.建筑学7.据说一个小男孩参考斐波那契数列发明了太阳能电池树：一名13岁的男孩根据斐波那契数列发明了太阳能电池树，其产生的电力比太阳能光伏电池阵列多20-50%。斐波那契数列类似从0和1开始，之后的数是之前两数的和，如0，1，1，2，3，5，8，13，21...Aidan Dwye在观察树枝分叉时发现它的分布模式类似斐波那契数列，这是大自然演化的一种结果，可能有助于树叶进行光合作用。因此，Dwye猜想为什么不按照斐波那契数列排列太阳能电池？他设计了太阳能电池树，发现它的输出电力提高了20%，每天接受光照的时间延长了2.5小时。8.斐波那契螺旋形的摇椅妈妈摇椅是设计师Patrick Messier为自己的妻子兼合作伙伴Sophie Fournier设计的，当时他们刚有了第一个宝宝。当Sophie宣布自己怀孕时，她说想要一把摇椅，但发现没有一把摇椅能满足美观舒适的标准，于是Patrick决定自己做一把。于是就有了这把妈妈摇椅。像是一个飘在空中的丝带，由一片纤维玻璃做成，曲线服从斐波那契数列分布，经过特殊的高光聚氨酯处理。五、数学上的扩展（1）广义斐波那契数列定义：a+b,ab\in Z,数列f(n)满足：其通项为：当a+b=1,ab=-1时即为斐波那契数列。（2）反斐波那契数列定义：g(n+2)=g(n)-g(n+1)反斐波那契数列相邻项比值的极限为-0.618。（3）巴都万数列(A000931 - OEIS)斐波那契数列可以刻画矩形，而巴都万数列则刻画的是三角形。其定义如下：(4)未解之谜：角谷猜想对一个正整数，若为奇数则乘3加1，若为偶数则除以2，通过有限次这样的操作，能否使得该数变成1？这个猜想和斐波那契数列又很大关系，具体的可以看角谷猜想的斐波那契数列现象。六、总结斐波那契数列是各个学科中都出现的小滑头，它许多漂亮的性质让我们着迷。上文我所描述的这些只是它的冰山一角，权当抛砖引玉。大家读完了我的答案，还可以再结合自己的专业去看一些相关的资料，更好的去了解这个有趣的数列。七、参考文献[1]http://www.hytc.cn/xsjl/szh/lec5.pdf[2]斐波那契数列_一米阳光[3]斐波那契数列的规律性[4]13岁男孩根据斐波那契数列发明太阳能电池树_cnBeta 人物_cnBeta.COM[5]服从斐波那契数列分布的妈妈摇椅[6]从斐波那契数列到黄金分割[7]斐波那契《计算之书》的研究.pdf 全文 文档投稿网[8]斐波那契数列['9]費氏數列[10]巴都萬數列[11]http://zh.wikipedia.org/wiki/%E5%8D%A2%E5%8D%A1%E6%96%AF%E6%95%B0[12]角谷猜想的斐波那契数列现象[13]The On-Line Encyclopedia of Integer Sequences® (OEIS®)[14]波浪理论斐波那契数列与黄金分割率编辑于 2015-04-27 13:25​赞同 2488​​115 条评论​分享​收藏​喜欢收起​知乎用户​数学话题下的优秀答主首先，斐波拉契数列和黄金分割有关，即相邻两项前后比值区域黄金分割数。这个是很著名的一点。其次，自然界中有很多现象满足斐波拉契数列，比如向日葵的种子分布。再次，斐波拉契数列在数学中和很多东西有关。比如杨辉三角的“对角和”就是它。同样在组合数学，二进制，数论（连分数）等方面都是可以见到它。它甚至可用来估计theta函数的某些值。甚至于希尔伯特第十问题（丢番图方程）的不可解反例就是可以从它构造而来。详情可见Fibonacci numberYuri Matiyasevich【来看解决第十问题的帅哥了】发布于 2015-02-08 15:03​赞同 38​​4 条评论​分享​收藏​喜欢

数学故事|自然界里的斐波那契数列 - 知乎

数学故事|自然界里的斐波那契数列 - 知乎首发于数学故事切换模式写文章登录/注册数学故事|自然界里的斐波那契数列万物皆数学高中我们学习了两类特殊数列，今天我们来看自然界普遍存在的数列：斐波那契数列指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）：我们这里讨论几个例子。 雄蜂家谱蜜蜂有一个家庭。在蜂巢中，有三种类型的蜂：不工作的雄蜂，工作的雌蜂（称为工蜂），还有蜂王。雄蜂从未受精的卵孵化，这意味着他只有一个母亲而没有父亲（但确实有一个祖父），而雌蜂从受精的卵孵化，因此需要一个母亲（蜂王）和一个父亲（一个雄蜂）。在图１中，我们从名为“阿蜂”的雄蜂，开始追踪其祖先。 “阿蜂”是雄蜂，来自未受精的卵，因此只需要雌蜂就可以生他，其父辈只有一个母亲，所以第二行的雄性0，雌性1，总数是1。但是，产卵的雌性一定有一个母亲和一个父亲， “阿蜂”的祖父辈，是“阿蜂”的母亲的双亲，因此，第三行的雄性1，雌性1，总数是2。“阿蜂”的曾祖父辈，总数是3（外祖母有有双亲，外祖父只有一个母亲），第四行的雄性1，雌性2，总数是3。然后继续这种模式：每个雄性的直接祖先是一个雌性，而一个雌性的祖先是一个雄性和一个雌性。在图１右边是每行蜜蜂数量的摘要。令人惊奇的是，在右边的每一列中，都出现斐波那契数列。 图1蜜蜂家谱在图1中，辈分低在上面，辈分高的在下面，与我们常见的家谱相反。在网络上介绍“雄蜂家谱”的文章，也有的把辈分高的画在上面，这样左面就是倒三角形形状，但是，右面的斐波那契数列也成为从下到上的排列。 光学反射光学领域为我们提供了斐波那契数的一个很好的应用。假设两块玻璃板面对面靠在一起放置，并希望计算可能的反射次数。第一种情况是没有反射，光源正好穿过两块玻璃板，如图２最上层所示。光线有一条路径。下一种情况是有一个反射。在这种情况下，光可以有两种可能的路径。它可以从两个界面反射，如图２第二排所示。假设光线在这两块玻璃板中反射两次。然后会有三种可能的反射，如图２第三排所示。如果光线被反射三次，那么有五种可能的光线路径，如图２第四排所示。光线经过四次反射，会产生八种可能的路径，如图２第五排所示。 图２　光线反射 叶序在植物学中，叶序是植物茎上叶子的排列。叶序螺旋在自然界形成了一类独特的模式。在植物学领域，叶序被认为是最显著的现象和最困难的课题。然而，叶序现象很简单，因为所有显示螺旋的叶序系统，多属于斐波那契型整数序列。“叶序学”是研究植物叶片和其他器官所表现出的形态的学科。在这类系统研究中常见斐波那契数列，一直吸引着植物学家和数学家。在一部名为《Phyllotaxis: A Systemic Study in Plant Morphogenesis（叶序学：植物形态发生的系统研究）》400页的专著（参考资料[2]）中，出现“Fibonacci（斐波那契）”名字达285次。书中从事实和理论的叶序之间的比较中得出结论。例如，书中有一个表（Table 7.12），统计超过650种物种的8种模式和12750个观测数据，其中11641个出现斐波那契模式<1,2,3,5,8，…＞，占91.3％。书中详细分析了松果和向日葵的种子呈黄金分割比螺旋，但也指出，有许多的植物并不遵循这个规律。早在18世纪，查尔斯·博内（Charles Bonnet，1720–1793）就指出，在植物的螺旋叶序中，顺时针和逆时针方向，通常是斐波那契数列中两个连续的数。以松果为例，在图３（Ａ和Ｂ）中，清晰可见8个逆时针螺旋和13个顺时针螺旋（8和13是斐波那契数列中两个连续的数）。在几何和黄金分割比的计算中，５是一个非常特殊的数字。不仅φ和五边形和五角星之间有关系，而且这个数字也是斐波那契数列的数字。事实上，许多最常见和最美丽的植物和花卉，包括玫瑰科的植物和花卉，都表现出这种完美的黄金对称。非洲螺旋芦荟植物中有五种逆时针方向的螺旋（图３－C）。 图３　植物螺旋（图片来自网络）还有一些花瓣的生长方式与斐波那契数列一致，例如（参考资料[３]），1瓣：白色百合花（white cally lily），3花瓣：百合（lily）、鸢尾（iris），5花瓣：毛茛（buttercup）、野玫瑰（wild rose）、龙葵（columbine），8花瓣：飞燕草（delphiniums），13花瓣：豚草、玉米万寿菊、金银花，21花瓣：紫菀（aster）、黑眼苏珊（black-eyed susan）、菊苣（chicory），34花瓣：车前草（plantain）、除虫菊（pyrethrum），55，89花瓣：米迦勒菊（michaelmas daisies），菊科（the asteraceae family）。没有人真正知道在植物中这些模式是如何和为什么发生的。是基因问题吗？有人解释是一朵花的叶子跟随太阳。这听起来很有说服力，但还不能解释海洋生物的形态。 微观结构的斐波那契数中国科学院的专家在研究微观结构时候，发现一个新的线索：瓜果外形可能是个力学问题，而非基因问题。对于材料科学家来说，如何在设计的图案中以均匀的尺寸和形状制造出高度有序的微纳米结构是一个巨大的挑战。通过控制冷却时的几何形状和应力，中国科学院研究人员引导一种微观结构在其表面自组装成三角形镶嵌和斐波那契数图案。他们的论文“由核/壳微观结构上的应力驱动的三角形和斐波那契数模式”，发表在2005年8月5日的《科学》杂志上。曹则贤教授与中国科学院物理研究所的合作者，利用银核和氧化硅壳，研究直径约10微米的微结构中的应力。他们首先将Ag2O和SiO2的混合物加热到1270k的衬底上，这个温度略高于银的熔点，但低于SiO2的熔点，然后让系统一步一步地冷却下来。研究人员发现，壳的收缩比内核小得多，因此壳上出现了凹凸不平的图案。这些凸起以不同的形式出现，大小和形状明显一致，这取决于主要支承面的几何形状。通过操纵银核和二氧化硅壳构成的无机微结构上的应力产生了斐波那契螺旋图案。斐波那契模式的自发组合在实验室中很少被实现，科学家的结果表明，植物模式可能是由球形和锥形表面的相互排斥实体来模拟的。图4　银核和二氧化硅壳构成的无机微结构上的应力产生了斐波那契螺旋图案 DNA中发现的黄金分割比DNA即脱氧核糖核酸，是染色体主要组成成分，同时也是主要遗传物质。人体内的每个细胞都含有九十二条DNA链（共有二十三对染色体，共四十六条，每对染色体由两条DNA链组成）。细胞中的DNA呈双链螺旋，称为B-DNA。这个DNA的螺旋结构中有一个双槽（图5-A），主槽（Major　groove）和次槽（Minor　groove）的比值，大约是21埃对13埃，比值近似于φ。它的双螺旋螺旋的每一个完整周期测量34埃长21埃宽。34和21当然是斐波那契数列中的连续的两个数，它们的比值，1.6190476非常接近φ，1.6180339。DNA横截面的图像（图5-B），揭示了一个清晰的10边几何学，一个十角形的基础。一个十边形本质上是两个五边形（图5-C和D），其中一个与另一个旋转36度，因此双螺旋的每个螺旋必须描绘出一个五边形的形状。五边形的对角线与边的比值是φ。所以，不管从哪个角度看它，哪怕是最小的元素，DNA和生命，都是用φ和黄金分割构造的。 图5　DNA中的斐波那契数 在量子世界中发现的黄金分割比欧洲著名物理研究机构HZB研究团队，与牛津大学等研究机构的同事合作，首次观测到隐藏在固态物质中的纳米对称性。他们测量了对称性的特征，显示出著名的黄金分割比相同的属性。2010年1月8日在《科学》杂志上发表这些发现。在原子尺度上，粒子的行为不像我们在宏观原子世界中所知道的那样。新特性的出现是海森堡测不准原理的结果。研究人员观察到原子链就像一根纳米级的吉他弦。来自自旋之间的相互作用，导致它们产生磁共振。对于这些相互作用，他们发现了一系列的共振音符：前两个音符显示出完美的相互关系，频率（音调）是1.618…，这是著名的黄金分割比，它反映了量子系统的一个美丽特性——隐藏的对称性。 图6　磁场用于将自旋链调整到量子临界状态 螺旋星系对于螺旋星系，也可以观察到斐波那契螺旋。我们自己的银河系就是这样一个天体。银河系中的某些其他实体也表现出黄金分割比。它是在土星和土星环直径的比值中发现的。它也是金星和地球与太阳距离的比值。有趣的是，这两颗行星的转速之比也得出了黄金分割比。黄金螺旋是基于黄金分割比。黄金螺旋总是以这个比例增加——螺旋每转四分之一圈，它就会变宽一倍φ。在这里，黄金螺旋正好与螺旋星系相吻合。银河系有许多旋臂，围绕着一个厚度约为10000光年的中心核心。每个旋臂都有大约12度的对数螺旋。螺旋的形状和黄金螺旋是一样的，黄金矩形可以画在任何螺旋星系上。 图6银河系是螺旋星系 时空的拓扑结构南非比勒陀利亚大学的扬·博伊恩斯（Jan Boeyens）博士和威特沃特斯兰德大学的弗朗西斯·萨克里博士共同研究表明：黄金分割比也可在时空的拓扑结构中发现，而且这一比率可能决定了宇宙中特定事物的成形。博伊恩斯特别指出，螺旋的形状也符合黄金分割率。这表明，宇宙中的几何形状最终还是服从这个数学属性。研究人员称，黄金分割率之所以无处不在，是因为它是一个时空特性。博伊恩斯的这篇论文标题是《数论与科学的统一Number theory and the unity of science》（参考资料[13]），文中指出，“假定黄金分割率具有宇宙属性，最具说服力的例子是无处不在的对数螺线。”突出的例子有漩涡星系(M51)、菊石、鹦鹉螺贝壳、卡特里娜飓风以及太阳系中行星、卫星、小行星和行星环的分布。文中并附有如下图片（图7）。图7在自然发现的对数螺旋的例子：（从左到右）漩涡星系，鹦鹉螺壳，飓风卡特里娜和菊石资料来源于网络，侵权删关注置顶公众号：第一时间获取最新数学学习资料及有趣的数学科普文章、故事。数学|资料|学习|科普编辑于 2021-08-29 09:02数学科普数学数列​赞同 30​​1 条评论​分享​喜欢​收藏​申请转载​文章被以下专栏收录数学故事每日一个数学故事或者数

斐波那契（Leonardo Fibonacci） - 知乎

斐波那契（Leonardo Fibonacci） - 知乎首页知乎知学堂发现等你来答​切换模式登录/注册斐波那契（Leonardo Fibonacci）斐波那契，又称比萨的列奥纳多（约1175年－约1250年）是一位意大利的数学家。因发现了“斐波那契数列”而闻名于世...查看全部内容关注话题​管理​分享​百科讨论精华视频等待回答详细内容简介斐波那契，又称比萨的列奥纳多（约1175年－约1250年）是一位意大利的数学家。因发现了“斐波那契数列”而闻名于世。生平斐波那契是一位数学家，生于公元1175年，籍贯是比萨，卒于1250年。他是第一个研究了印度和阿拉伯数学理论的欧洲人。斐波那契数列因他解决兔子繁殖的应用题而引入，故又称为“兔子数列”。除此之外，他对欧洲数学的另一大贡献就是引进阿拉伯数字，从而取代了复杂的罗马计数法。家庭斐波那契的父亲名为Guilielmo（威廉），外号Bonacci（意即好、自然或简单）。因此列奥纳多就得到了外号斐波那契 (Fibonacci，意即filius Bonacci，Bonacci之子）。威廉是商人，在北非一带工作（今阿尔及利亚Bejaia），当时年轻的列奥纳多已经开始协助父亲工作，他学会了阿拉伯数字。代表作品《Liber Abaci》（计算之书，1202年）。《Practica Geometriae》（几何实践，1220年）。《Flos》（花朵，1225年），Johannes of Palermo提出的问题的答案。《Liber quadratorum》（平方数书）关于丢番图方程的问题on Diophantine problems,that is,problems involving Diophantine equations.《Di minor guisa》（关于商业运算；己佚）《几何原本》第十卷的注释（已佚）拉丁文代表著作《珠算原理》主要成就斐波那契是西方第一个研究斐波那契数的人，并将现代书写数和乘数的位值表示法系统引入欧洲。其写于1202年的著作《计算之书》中包涵了许多希腊、埃及、阿拉伯、印度、甚至是中国数学相关内容。斐波那契数列斐波那契在《计算之书》中提出一个在理想假设条件下兔子成长率的问题，并自行求解此问题。所求得的各代兔子的个数可形成一个数列，也就是斐波那契数，不过列奥纳多不是最早提到数列的数学家，此数列最早是由印度数学家在第6世纪时所发现[1]，但因为列奥纳多才使西方知道此一数列，因此而得名。斐波那契数的特点是每一个数都是前二个数的和。头二项是0和1，此数列的前几项如下： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 ...随着斐波那契数的增加，相邻二项斐波那契数相除的商会接近黄金比例（近似值为1 : 1.618或0.618 : 1）[2]浏览量340 万讨论量2320  帮助中心知乎隐私保护指引申请开通机构号联系我们 举报中心涉未成年举报网络谣言举报涉企虚假举报更多 关于知乎下载知乎知乎招聘知乎指南知乎协议更多京 ICP 证 110745 号 · 京 ICP 备 13052560 号 - 1 · 京公网安备 11010802020088 号 · 京网文[2022]2674-081 号 · 药品医疗器械网络信息服务备案（京）网药械信息备字（2022）第00334号 · 广播电视节目制作经营许可证:（京）字第06591号 · 服务热线：400-919-0001 · Investor Relations · © 2024 知乎 北京智者天下科技有限公司版权所有 · 违法和不良信息举报：010-82716601 · 举报邮箱：jubao@zhihu.

斐波那契数（0,1,1,2,3,5,8,13，...）

斐波那契数（0,1,1,2,3,5,8,13，...）

RT

首页/数学/数字/斐波那契数

斐波那契数字和序列

斐波那契数列是一个数字序列，其中每个数字是前两个数字的总和，但前两个数字分别为0和1。

斐波那契数列公式

黄金比例收敛

斐波那契序列表

斐波那契数列计算器

Fibonacci函数的C ++代码

斐波那契数列公式

例如：

F 0 = 0

F 1 = 1

F 2 = F 1 + F 0 = 1 + 0 = 1

F 3 = F 2 + F 1 = 1 + 1 = 2

F 4 = F 3 + F 2 = 2 + 1 = 3

F 5 = F 4 + F 3 = 3 + 2 = 5

...

黄金比例收敛

两个连续斐波那契数之比收敛于黄金比例：

φ是黄金比例=（1 +√ 5）/ 2≈1.61803399

斐波那契序列表

n

˚F ñ

0

0

1

1

2

1

3

2

4

3

5

5

6

8

7

13

8

21

9

34

10

55

11

89

12

144

13

233

14

377

15

610

16

987

17

1597

18

2584

19

4181

20

6765

斐波那契数列计算器

待定

斐波那契函数的C代码

double Fibonacci(unsigned int n)

{

    double f_n =n;

    double f_n1=0.0;

    double f_n2=1.0;

 

    if( n / 1 ) {

        for(int

k=2; k<=n; k++) {

           

f_n  = f_n1 + f_n2;

           

f_n2 = f_n1;

           

f_n1 = f_n;

        }

    }

 

    return f_n;

}

 

Advertising

号码

常数

指数

斐波那契数

乘法表

数字系统

百万分之一（ppm）

英里数（‰）

百分比（％）

素数

零号

快速表格

推荐网站

发送反馈

关于

 

首页| 网页| 数学| 电力| 计算器| 转换器| 工具类

© 2024

RT | 关于| 使用条款| 隐私政策| 管理Cookies

该网站使用Cookie来改善您的体验，分析流量并展示广告。学到更多

确定 管理设置

斐波拉契序列_百度百科

序列_百度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心收藏查看我的收藏0有用+10斐波拉契序列播报讨论上传视频现代书写数和乘数的位值表示法系统的定理本词条缺少概述图，补充相关内容使词条更完整，还能快速升级，赶紧来编辑吧！斐波拉契序列是现代书写数和乘数的位值表示法系统的定理。中文名斐波拉契序列外文名Fibonaccisequence提出者列奥纳多，又称斐波那契适用领域计算机.编程应用学科数学.计算机.编程目录1详细写法2详细算法3推导过程详细写法播报编辑#include

int main( )

{

int n;

int f1,f2,f3;

int i;

f1=1;

f2=2;

printf("请输入您需要求的想的序列：");

scanf("%d",&n);

if(1 == n)

{

f3=1;

}

else if(n==2)

{

f3=2;

}

else

{

for(i=3;i＜=n;i++)

{

f3=f1+f2;

f1=f2;

f2=f3;

}

}

printf("%d\n",f3);

return 0;

}详细算法播报编辑n=1

f3=1

n=2

f3=2

n=3

i=3;i＜=3;成立

f3=1+2

f1=2

f2=3

++i;4＜=3;不成立

f3=3

n=4

i=3;i＜=3;成立

f3=1+2

f1=2

f2=3

++i;4＜=4;成立

f3=2+3

f1=3

f2=5

++i;5＜=4;不成立

f3=5

n=5

i=3;i＜=3;成立

f3=1+2

f1=2

f2=3

++i;4＜=4;成立

f3=2+3

f1=3

f2=5

++i;5＜=5;成立

f3=3+5

f1=5

f2=8

++i;6＜=5;不成立

f3=8

n=6

i=3;i＜=3;成立

f3=1+2

f1=2

f2=3

++i;4＜=4;成立

f3=2+3

f1=3

f2=5

++i;5＜=5;成立

f3=3+5

f1=5

f2=8

++i;6＜=6;成立

f3=5+8

f1=8

f2=12

++i;7＜=6不成立

f3=13推导过程播报编辑比萨的列奥纳多，又称斐波那契（Leonardo Pisano ,Fibonacci, Leonardo Bigollo，1175年-1250年），意大利数学家，西方第一个研究斐波那契数，并将现代书写数和乘数的位值表示法系统引入欧洲。斐波那契数列：　斐波那契在《算盘书》中提出了一个有趣的兔子问题：　一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？　我们不妨拿新出生的一对小兔子分析一下： 第一个月小兔子没有繁殖能力，所以还是一对; 　 两个月后，生下一对小兔总数共有两对; 　三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对; 　……　依次类推可以列出下表：　经过月数 0 1 2 3 4 5 6 7 8 9 10 11 12 幼仔对数 0 0 1 1 2 3 5 8 13 21 34 55 89 成兔对数 1 1 1 2 3 5 8 13 21 34 55 89 144 总体对数 1 1 2 3 5 8 13 21 34 55 89 144 233 　表中数字1，1，2，3，5，8－－－构成了一个序列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。 这个数列是意大利中世纪数学家斐波那契在《算盘书》中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)/的性质外，还可以证明通项公式为：这个通项公式中虽然所有的an都是正整数，可是它们却是由一些无理数表示出来的。 　即在较高的序列，两个连续的“斐波纳契数”的序列相互分割将接近黄金比例（1.618:1或1:0.618）。 　 例如：233/144，987/610、、、、斐波那契数列还有两个有趣的性质　1.斐波那契数列中任一项的平方数都等于跟它相邻的前后两项的乘积加1或减1; 　 2.任取相邻的四个斐波那契数，中间两数之积（内积）与两边两数之积（外积）相差1. 　 同样我们还可以有t阶斐波那契数列，通过递推数列a(n+t)=a(n+t-1)+a(n+t-2)+...+a(n),其中a(1)=a(2)=1,以及对于3-t＜=n＜=0,有a(n)=0. 　给出了t阶斐波那契数列的通项公式: 　[r^(n-1)(r-1)/((t+1)r-2t)], 其中r是方程x^{t+1}-2x^t+1=0的唯一一个大于1的正数根（可以看出r非常接近2）。新手上路成长任务编辑入门编辑规则本人编辑我有疑问内容质疑在线客服官方贴吧意见反馈投诉建议举报不良信息未通过词条申诉投诉侵权信息封禁查询与解封©2024 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号 京公网安备110000020000

斐波那契数列 - OI Wiki

数列 - OI Wiki 跳转至 OI Wiki 斐波那契数列 正在初始化搜索引擎 OI-wiki/OI-wiki 简介 比赛相关 工具软件 语言基础 算法基础 搜索 动态规划 字符串 数学 数据结构 图论 计算几何 杂项 专题 关于 Hulu OI Wiki OI-wiki/OI-wiki 简介 简介 Getting Started 关于本项目 如何参与 OI Wiki 不是什么 格式手册 数学符号表 F.A.Q. 用 Docker 部署 OI Wiki 镜像站列表 致谢 比赛相关 比赛相关 比赛相关简介 赛事 赛事 OI 赛事与赛制 ICPC/CCPC 赛事与赛制 题型 题型 题型概述 交互题 学习路线 学习资源 技巧 技巧 读入、输出优化 分段打表 常见错误 常见技巧 出题 工具软件 工具软件 工具软件简介 代码编辑工具 代码编辑工具 Vim Emacs VS Code Atom Eclipse Notepad++ Kate Dev-C++ CLion Geany Xcode GUIDE Sublime Text CP Editor 评测工具 评测工具 评测工具简介 Arbiter Cena CCR Plus Lemon 命令行 编译器 WSL (Windows 10) Special Judge Testlib Testlib Testlib 简介 通用 Generator Validator Interactor Checker Polygon OJ 工具 LaTeX 入门 Git 语言基础 语言基础 语言基础简介 C++ 基础 C++ 基础 Hello, World! C++ 语法基础 变量 运算 流程控制语句 流程控制语句 分支 循环 高级数据类型 高级数据类型 数组 结构体 联合体 指针 函数 文件操作 C++ 标准库 C++ 标准库 C++ 标准库简介 STL 容器 STL 容器 STL 容器简介 迭代器 序列式容器 关联式容器 无序关联式容器 容器适配器 STL 算法 bitset string pair C++ 进阶 C++ 进阶 类 命名空间 值类别 重载运算符 引用 常值 新版 C++ 特性 Lambda 表达式 pb_ds pb_ds pb_ds 简介 堆 平衡树 编译优化 C++ 与其他常用语言的区别 Pascal 转 C++ 急救 Python 速成 Java 速成 Java 进阶 算法基础 算法基础 算法基础简介 复杂度 枚举 模拟 递归 & 分治 贪心 排序 排序 排序简介 选择排序 冒泡排序 插入排序 计数排序 基数排序 快速排序 归并排序 堆排序 桶排序 希尔排序 锦标赛排序 tim排序 排序相关 STL 排序应用 前缀和 & 差分 二分 倍增 构造 搜索 搜索 搜索部分简介 DFS（搜索） BFS（搜索） 双向搜索 启发式搜索 A* 迭代加深搜索 IDA* 回溯法 Dancing Links Alpha-Beta 剪枝 优化 动态规划 动态规划 动态规划部分简介 动态规划基础 记忆化搜索 背包 DP 区间 DP DAG 上的 DP 树形 DP 状压 DP 数位 DP 插头 DP 计数 DP 动态 DP 概率 DP DP 优化 DP 优化 单调队列/单调栈优化 斜率优化 四边形不等式优化 状态设计优化 其它 DP 方法 字符串 字符串 字符串部分简介 字符串基础 标准库 字符串匹配 字符串哈希 字典树 (Trie) 前缀函数与 KMP 算法 Boyer–Moore 算法 Z 函数（扩展 KMP） 自动机 AC 自动机 后缀数组 (SA) 后缀数组 (SA) 后缀数组简介 最优原地后缀排序算法 后缀自动机 (SAM) 后缀平衡树 广义后缀自动机 后缀树 Manacher 回文树 序列自动机 最小表示法 Lyndon 分解 Main–Lorentz 算法 数学 数学 数学部分简介 符号 进位制 位运算 二进制集合操作 平衡三进制 高精度计算 快速幂 置换和排列 弧度制与坐标系 复数 数论 数论 数论基础 素数 最大公约数 数论分块 欧拉函数 筛法 Meissel–Lehmer 算法 分解质因数 裴蜀定理 类欧几里德算法 欧拉定理 & 费马小定理 乘法逆元 线性同余方程 中国剩余定理 升幂引理 威尔逊定理 卢卡斯定理 同余方程 二次剩余 原根 离散对数 剩余 莫比乌斯反演 杜教筛 Powerful Number 筛 Min_25 筛 洲阁筛 连分数 Stern–Brocot 树与 Farey 序列 二次域 循环连分数 Pell 方程 多项式与生成函数 多项式与生成函数 多项式与生成函数简介 代数基本定理 快速傅里叶变换 快速数论变换 快速沃尔什变换 Chirp Z 变换 多项式牛顿迭代 多项式多点求值|快速插值 多项式初等函数 常系数齐次线性递推 多项式平移|连续点值平移 符号化方法 普通生成函数 指数生成函数 狄利克雷生成函数 组合数学 组合数学 排列组合 抽屉原理 容斥原理 康托展开 斐波那契数列 斐波那契数列 目录 卢卡斯数列 斐波那契数列通项公式 解析解 卢卡斯数列通项公式 矩阵形式 快速倍增法 性质 斐波那契数列与卢卡斯数列的关系 斐波那契编码 模意义下周期性 皮萨诺周期 习题 错位排列 卡特兰数 斯特林数 贝尔数 伯努利数 Entringer Number Eulerian Number 分拆数 范德蒙德卷积 图论计数 线性代数 线性代数 线性代数简介 向量 内积和外积 矩阵 初等变换 行列式 线性空间 线性基 线性映射 特征多项式 对角化 Jordan标准型 线性规划 线性规划 线性规划简介 单纯形算法 群论 群论 群论简介 置换群 概率论 概率论 基本概念 条件概率与独立性 随机变量 随机变量的数字特征 概率不等式 博弈论 博弈论 博弈论简介 公平组合游戏 非公平组合游戏 反常游戏 数值算法 数值算法 插值 数值积分 高斯消元 牛顿迭代法 傅里叶-莫茨金消元法 序理论 杨氏矩阵 Schreier–Sims 算法 Berlekamp–Massey 算法 数据结构 数据结构 数据结构部分简介 栈 队列 链表 哈希表 并查集 并查集 并查集 并查集复杂度 堆 堆 堆简介 二叉堆 配对堆 左偏树 块状数据结构 块状数据结构 分块思想 块状数组 块状链表 树分块 Sqrt Tree 单调栈 单调队列 ST 表 树状数组 线段树 李超线段树 区间最值操作 & 区间历史最值 划分树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 二叉搜索树 & 平衡树 Treap Splay 树 WBLT Size Balanced Tree AVL 树 B 树 B+ 树 替罪羊树 Leafy Tree 笛卡尔树 红黑树 左偏红黑树 AA 树 2-3 树 2-3-4 树 跳表 可持久化数据结构 可持久化数据结构 可持久化数据结构简介 可持久化线段树 可持久化块状数组 可持久化平衡树 可持久化字典树 可持久化可并堆 树套树 树套树 线段树套线段树 平衡树套线段树 线段树套平衡树 树状数组套权值线段树 分块套树状数组 K-D Tree 动态树 动态树 Link Cut Tree 全局平衡二叉树 Euler Tour Tree Top Tree 析合树 PQ 树 手指树 霍夫曼树 图论 图论 图论部分简介 图论相关概念 图的存储 DFS（图论） BFS（图论） 树上问题 树上问题 树基础 树的直径 最近公共祖先 树的重心 树链剖分 树上启发式合并 虚树 树分治 动态树分治 AHU 算法 树哈希 树上随机游走 矩阵树定理 有向无环图 拓扑排序 最小生成树 斯坦纳树 最小树形图 最小直径生成树 最短路 拆点 差分约束 k 短路 同余最短路 连通性相关 连通性相关 强连通分量 双连通分量 割点和桥 圆方树 点/边连通度 环计数问题 2-SAT 欧拉图 哈密顿图 二分图 最小环 平面图 图的着色 网络流 网络流 网络流简介 最大流 最小割 费用流 上下界网络流 Stoer–Wagner 算法 图的匹配 图的匹配 图匹配 增广路 二分图最大匹配 二分图最大权匹配 一般图最大匹配 一般图最大权匹配 Prüfer 序列 LGV 引理 弦图 最大团搜索算法 支配树 图上随机游走 计算几何 计算几何 计算几何部分简介 二维计算几何基础 三维计算几何基础 距离 Pick 定理 三角剖分 凸包 扫描线 旋转卡壳 半平面交 平面最近点对 随机增量法 反演变换 计算几何杂项 杂项 杂项 杂项简介 离散化 双指针 离线算法 离线算法 离线算法简介 CDQ 分治 整体二分 莫队算法 莫队算法 莫队算法简介 普通莫队算法 带修改莫队 树上莫队 回滚莫队 二维莫队 莫队二次离线 莫队配合 bitset 分数规划 随机化 随机化 随机函数 随机化技巧 爬山算法 模拟退火 悬线法 计算理论基础 字节顺序 约瑟夫问题 格雷码 表达式求值 在一台机器上规划任务 主元素问题 Garsia–Wachs 算法 15-puzzle Kahan 求和 珂朵莉树/颜色段均摊 专题 专题 RMQ 并查集应用 括号序列 线段树与离线询问 关于 Hulu 关于 Hulu 关于 Hulu 目录 卢卡斯数列 斐波那契数列通项公式 解析解 卢卡斯数列通项公式 矩阵形式 快速倍增法 性质 斐波那契数列与卢卡斯数列的关系 斐波那契编码 模意义下周期性 皮萨诺周期 习题 斐波那契数列斐波那契数列（The Fibonacci sequence，OEIS A000045）的定义如下：该数列的前几项如下：卢卡斯数列卢卡斯数列（The Lucas sequence，OEIS A000032）的定义如下：该数列的前几项如下：研究斐波那契数列，很多时候需要借助卢卡斯数列为工具。斐波那契数列通项公式第 个斐波那契数可以在 的时间内使用递推公式计算。但我们仍有更快速的方法计算。解析解解析解即公式解。我们有斐波那契数列的通项公式（Binet's Formula）：这个公式可以很容易地用归纳法证明，当然也可以通过生成函数的概念推导，或者解一个方程得到。当然你可能发现，这个公式分子的第二项总是小于 ，并且它以指数级的速度减小。因此我们可以把这个公式写成这里的中括号表示取离它最近的整数。这两个公式在计算的时候要求极高的精确度，因此在实践中很少用到。但是请不要忽视！结合模意义下二次剩余和逆元的概念，在 OI 中使用这个公式仍是有用的。卢卡斯数列通项公式我们有卢卡斯数列的通项公式：与斐波那契数列非常相似。事实上有：也就是说， 和 恰好构成 二项式展开再合并同类项后的分子系数。也就是说，Pell 方程的全体解，恰好是恰好是卢卡斯数列和斐波那契数列。因此有矩阵形式斐波那契数列的递推可以用矩阵乘法的形式表达：设 ，我们得到于是我们可以用矩阵乘法在 的时间内计算斐波那契数列。此外，前一节讲述的公式也可通过矩阵对角化的技巧来得到。快速倍增法使用上面的方法我们可以得到以下等式：于是可以通过这样的方法快速计算两个相邻的斐波那契数（常数比矩乘小）。代码如下，返回值是一个二元组 。 1

2

3

4

5

6

7

8

9

10pair fib(int n) {

if (n == 0) return {0, 1};

auto p = fib(n >> 1);

int c = p.first * (2 * p.second - p.first);

int d = p.first * p.first + p.second * p.second;

if (n & 1)

return {d, c + d};

else

return {c, d};

}

性质斐波那契数列拥有许多有趣的性质，这里列举出一部分简单的性质：卡西尼性质（Cassini's identity）：。附加性质：。取上一条性质中 ，我们得到 。由上一条性质可以归纳证明，。上述性质可逆，即 。GCD 性质：。以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度（具体参见 维基 - 拉梅）。斐波那契数列与卢卡斯数列的关系不难发现，关于卢卡斯数列与斐波那契数列的等式，与三角函数公式具有很高的相似性。比如：与很像。以及与很像。因此，卢卡斯数列与余弦函数很像，而斐波那契数列与正弦函数很像。比如，根据可以得到两下标之和的等式：于是推论就有二倍下标的等式：这也是一种快速倍增下标的办法。同样地，也可以仿照三角函数的公式，比如奇偶性、和差化积、积化和差、半角、万能代换等等，推理出更多有关卢卡斯数列与斐波那契数列的相应等式。斐波那契编码我们可以利用斐波那契数列为正整数编码。根据 齐肯多夫定理，任何自然数 可以被唯一地表示成一些斐波那契数的和：并且 （即不能使用两个相邻的斐波那契数）于是我们可以用 的编码表示一个正整数，其中 则表示 被使用。编码末位我们强制给它加一个 1（这样会出现两个相邻的 1），表示这一串编码结束。举几个例子：给 编码的过程可以使用贪心算法解决：从大到小枚举斐波那契数 ，直到 。把 减掉 ，在编码的 的位置上放一个 1（编码从左到右以 0 为起点）。如果 为正，回到步骤 1。最后在编码末位添加一个 1，表示编码的结束位置。解码过程同理，先删掉末位的 1，对于编码为 1 的位置 （编码从左到右以 0 为起点），累加一个 到答案。最后的答案就是原数字。模意义下周期性考虑模 意义下的斐波那契数列，可以容易地使用抽屉原理证明，该数列是有周期性的。考虑模意义下前 个斐波那契数对（两个相邻数配对）： 的剩余系大小为 ，意味着在前 个数对中必有两个相同的数对，于是这两个数对可以往后生成相同的斐波那契数列，那么他们就是周期性的。皮萨诺周期模 意义下斐波那契数列的最小正周期被称为 皮萨诺周期（Pisano periods,OEIS A001175）。皮萨诺周期总是不超过 ，且只有在满足 的形式时才取到等号。当需要计算第 项斐波那契数模 的值的时候，如果 非常大，就需要计算斐波那契数模 的周期。当然，只需要计算周期，不一定是最小正周期。容易验证，斐波那契数模 的最小正周期是 ，模 的最小正周期是 。显然，如果 与 互素， 的皮萨诺周期就是 的皮萨诺周期与 的皮萨诺周期的最小公倍数。计算周期还需要以下结论：结论 1：对于奇素数 ， 是斐波那契数模 的周期。即，奇素数 的皮萨诺周期整除 。证明：此时 。由二项式展开：因为 和 两项都同余于 ，与 和 一致，所以 是周期。结论 2：对于奇素数 ， 是斐波那契数模 的周期。即，奇素数 的皮萨诺周期整除 。证明：此时 。由二项式展开：模 之后，在 式中，只有 项留了下来；在 式中，有 、、，三项留了下来。于是 和 两项与 和 一致，所以 是周期。结论 3：对于素数 ， 是斐波那契数模 的周期，等价于 是斐波那契数模 的周期。特别地， 是模 的皮萨诺周期，等价于 是模 的皮萨诺周期。证明：这里的证明需要把 看作一个整体。由于：因此：因为反方向也可以推导，所以 是斐波那契数模 的周期，等价于：当 是奇素数时，由 升幂引理，有：当 时，由 升幂引理，有：代入 为 和 ， 为 和 ，上述条件也就等价于：因此也等价于 是斐波那契数模 的周期。因为周期等价，所以最小正周期也等价。三个结论证完。据此可以写出代码： 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40struct prime {

unsigned long long p;

int times;

};

struct prime pp[2048];

int pptop;

unsigned long long get_cycle_from_mod(

unsigned long long mod) // 这里求解的只是周期，不一定是最小正周期

{

pptop = 0;

srand(time(0));

while (n != 1) {

__int128_t factor = (__int128_t)10000000000 * 10000000000;

min_factor(mod, &factor); // 计算最小素因数

struct prime temp;

temp.p = factor;

for (temp.times = 0; mod % factor == 0; temp.times++) {

mod /= factor;

}

pp[pptop] = temp;

pptop++;

}

unsigned long long m = 1;

for (int i = 0; i < pptop; ++i) {

int g;

if (pp[i].p == 2) {

g = 3;

} else if (pp[i].p == 5) {

g = 20;

} else if (pp[i].p % 5 == 1 || pp[i].p % 5 == 4) {

g = pp[i].p - 1;

} else {

g = (pp[i].p + 1) << 1;

}

m = lcm(m, g * qpow(pp[i].p, pp[i].times - 1));

}

return m;

}

习题SPOJ - Euclid Algorithm RevisitedSPOJ - Fibonacci SumHackerRank - Is FiboProject Euler - Even Fibonacci numbers洛谷 P4000 斐波那契数列 本页面主要译自博文 Числа Фибоначчи 与其英文翻译版 Fibonacci Numbers。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。本页面最近更新：2023/9/5 22:13:33，更新历史发现错误？想一起完善？ 在 GitHub 上编辑此页！本页面贡献者：dkz051, Enter-tainer, EntropyIncreaser, FFjet, Great-designer, ImpleLee, jifbt, Junyan721113, ouuan, sshwy, Tiphereth-A, Xeonacid本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用Copyright © 2016 - 2024 OI Wiki Team Made with Material for MkDocs 最近更新：7ff011ae, 2024-03-