• 正在加载中...
  • 斐波那契数列

    斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。

    编辑摘要

    基本信息 编辑信息模块

    中文名称: 斐波那契数列 外文名: Fibonacci sequence
    别称: 黄金分割数列、兔子数列 表达式: F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
    提出者: 列昂纳多·斐波那契 提出时间: 1202年
    应用学科: 数学 适用领域范围: 代数等多个领域
    c语言中: FIB数列 适合领域: 代数

    目录

    定义

    斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........

    自然中的斐波那契数列 自然中的斐波那契数列

    这个数列从第3项开始,每一项都等于前两项之和。

    斐波那契数列的定义者,是意大利数学家列昂纳多·斐波那契(Leonardo Fibonacci),生于公元1170年,卒于1250年,籍贯是比萨。他被人称作“比萨的列昂纳多”。1202年,他撰写了《算盘全书》(Liber Abacci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事,派驻地点于阿尔及利亚地区,列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯等地研究数学。

    通项公式/斐波那契数列 编辑

    递推公式

    斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

    如果设F(n)为该数列的第n项(n∈N*),那么这句话可以写成如下形式::F(n)=F(n-1)+F(n-2)

    显然这是一个线性递推数列。

    通项公式

    斐波那契数列 斐波那契数列

    (如上,又称为“比内公式”,是用无理数表示有理数的一个范例。)

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    注:此时

    通项公式推导

    方法一:利用特征方程(线性代数解法)

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    线性递推数列的特征方程为:
      x²=x+1
      解得 

    .
      则

      ∵

      ∴
     
      解得

      

    方法二:待定系数法构造等比数列1(初等代数解法)

    设常数r,s .

    斐波那契数列 斐波那契数列

    使得

    则r+s=1,-rs=1

    n≥3时,有

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    ……

    斐波那契数列 斐波那契数列

    联立以上n-2个式子,得:

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    ∵ ,

    上式可化简得:

    斐波那契数列 斐波那契数列

    那么

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    ……

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    (这是一个以 为首项、以 为末项、 为公比的等比数列的各项的和)。

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    , 的解为

    斐波那契数列 斐波那契数列

    方法三:待定系数法构造等比数列2(初等代数解法)

    斐波那契数列 斐波那契数列

    斐波那契数列 斐波那契数列

    斐波那契数列 斐波那契数列

    构造方程

    斐波那契数列 斐波那契数列

    解得 ,所以

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    由(1)(2)式得

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    化简可得

    斐波那契数列 斐波那契数列

    方法四:母函数法。

    对于斐波那契数列{a},有a=a=1,a=a+a(n>2时)

    令S(x)=ax+ax+…+ax +...

    那么有S(x)*(1-x-x)=ax+(a-a)x+…+(a-a-a)x +...=x

    斐波那契数列 斐波那契数列

    因此S(x)= .

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    不难证明1-x-x=-(x+ )(x+ )=(1- *x)(1- *x).

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    因此S(x)= *[x/(1- *x)-x/(1- *x)].

    再利用展开式1/(1-x)=1+x+x+x+…+x +…

    于是就可以得S(x)=bx+bx+…+bx +…

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    其中b= *[( ) - ( ) ].

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    因此可以得到a=b= *[( )- ( )]

    与黄金分割

    关系

    有趣的是,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当n趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618(或者说后一项与前一项的比值小数部分越来越逼近0.618)。

    1÷1=1,1÷2=0.5,2÷3=0.666...,3÷5=0.6,5÷8=0.625…………,55÷89=0.617977……………144÷233=0.618025…46368÷75025=0.6180339886…...

    越到后面,这些比值越接近黄金比.

    证明

    斐波那契数列 斐波那契数列
    斐波那契数列 斐波那契数列

    两边同时除以 得到:

    斐波那契数列 斐波那契数列

    斐波那契数列 斐波那契数列

    若 的极限存在,设其极限为x,

    斐波那契数列 斐波那契数列

    则 。

    斐波那契数列 斐波那契数列

    所以 。

    斐波那契数列 斐波那契数列

    由于

    斐波那契数列 斐波那契数列

    解得

    所以极限是黄金分割比。

    特性/斐波那契数列 编辑

    平方与前后项

    从第二项开始,每个偶数项的平方都比前后两项之积少1,每个奇数项的平方都比前后两项之积多1。

    如:第二项1的平方比它的前一项1和它的后一项2的积2少1,第三项2的平方比它的前一项1和它的后一项3的积3多1。

    (注: 奇数项和偶数项是 指项数的奇偶,而并不是指数列的数字本身的奇偶,比如从数列第二项1开始数,第4项5是奇数,但它是偶数项,如果认为5是奇数项,那就误解题意,怎么都说不通)

    证明经计算可得:[f(n)]^2-f(n-1)f(n+1)=(-1)^(n-1)

    与集合子集

    斐波那契数列的第n+2项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。

    奇数项求和

    斐波那契数列 斐波那契数列

    偶数项求和

    斐波那契数列 斐波那契数列

    平方求和

    斐波那契数列 斐波那契数列

    隔项关系

    f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

    两倍项关系

    f(2n)/f(n)=f(n-1)+f(n+1)

    其他公式

    斐波那契数列 斐波那契数列

    应用/斐波那契数列 编辑

    生活斐波那契

    合并图册 合并图册

    斐波那契数列中的斐波那契数会经常出现在我们的眼前——比如松果、凤梨、树叶的排列、某些花朵的花瓣数(典型的有向日葵花瓣),蜂巢,蜻蜓翅膀,超越数e(可以推出更多),黄金矩形、黄金分割、等角螺线,十二平均律等。

    斐波那契数与植物花瓣3………………………

    百合和蝴蝶花5……………………

    蓝花耧斗菜、金凤花、飞燕草、毛茛花8………………………

    翠雀花13………………………

    金盏和玫瑰21……………………

    紫宛34、55、89……………雏菊

    斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如,在树木的枝干上选一片叶子,记其为数0,然后依序点数叶子(假定没有折损),直到到达与那些叶子正对的位置,则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比。多数的叶序比呈现为斐波那契数的比。

    黄金分割

    随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887..…

    杨辉三角

    将杨辉三角左对齐,成如图所示排列,将同一斜行的数加起来,即得一数列1、1、2、3、5、8、……

    斐波那契数列 斐波那契数列

    公式表示如下:

    f⑴=C(0,0)=1。

    f⑵=C(1,0)=1。

    f⑶=C(2,0)+C(1,1)=1+1=2。

    f⑷=C(3,0)+C(2,1)=1+2=3。

    f⑸=C(4,0)+C(3,1)+C(2,2)=1+3+1=5。

    f⑹=C(5,0)+C(4,1)+C(3,2)=1+4+3=8。

    f⑺=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13。

    ……

    f(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)

    矩形面积

    斐波那契数列与矩形面积的生成相关,由此可以导出一个斐波那契数列的一个性质。

    斐波那契数列 斐波那契数列

    斐波那契数列前几项的平方和可以看做不同大小的正方形,由于斐波那契的递推公式,它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积。则可以得到如下的恒等式:

    斐波那契数列 斐波那契数列

    质数数量

    斐波那契数列的整除性与质数生成性

    每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步的循环。

    自然界中“巧合”

    斐波那契数列在自然科学的其他分支,有许多应用。例如,树木的生长,由于新生的枝条,往往需要一段“休息”时间,供自身生长,而后才能萌发新枝。所以,一株树苗在一段间隔,例如一年,以后长出一条新枝;第二年新枝“休息”,老枝依旧萌发;此后,老枝与“休息”过一年的枝同时萌发,当年生的新枝则次年“休息”。这样,一株树木各个年份的枝桠数,便构成斐波那契数列。这个规律,就是生物学上著名的“鲁德维格定律”。

    另外,观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣,可以发现它们花瓣数目具有斐波那契数:3、5、8、13、21、……

    斐波那契数列 斐波那契数列

    其中百合花花瓣数目为3,梅花5瓣,飞燕草8瓣,万寿菊13瓣,向日葵21或34瓣,雏菊有34,55和89三个数目的花瓣。

    斐波那契螺旋:具有13条顺时针旋转和21条逆时针旋转的螺旋的蓟的头部

    这些植物懂得斐波那契数列吗?应该并非如此,它们只是按照自然的规律才进化成这样。这似乎是植物排列种子的“优化方式”,它能使所有种子具有差不多的大小却又疏密得当,不至于在圆心处挤了太多的种子而在圆周处却又稀稀拉拉。叶子的生长方式也是如此,对于许多植物来说,每片叶子从中轴附近生长出来,为了在生长的过程中一直都能最佳地利用空间(要考虑到叶子是一片一片逐渐地生长出来,而不是一下子同时出现的),每片叶子和前一片叶子之间的角度应该是222.5度,这个角度称为“黄金角度”,因为它和整个圆周360度之比是黄金分割数0.618033989……的倒数,而这种生长方式就决定了斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89,甚至144条。1992年,两位法国科学家通过对花瓣形成过程的计算机仿真实验,证实了在系统保持最低能量的状态下,花朵会以斐波那契数列长出花瓣。

    数字谜题

    三角形的三边关系定理和斐波那契数列的一个联系:

    现有长为144cm的铁丝,要截成n小段(n>2),每段的长度不小于1cm,如果其中任意三小段都不能拼成三角形,则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换成其他数,递推关系保留了,但这个数列消失了。这里,三角形的三边关系定理和斐波那契数列发生了一个联系。

    在这个问题中,144>143,这个143是斐波那契数列的前n项和,我们是把144超出143的部分加到最后的一个数上去,如果加到其他数上,就有3条线段可以构成三角形了。

    影视作品中的斐波那契数列

    斐波那契数列在欧美可谓是尽人皆知,于是在电影这种通俗艺术中也时常出现,比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现,在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名,多数人也就背过前几个数,并没有深入理解研究。在电视剧中也出现斐波那契数列,比如:日剧《考试之神》第五回,义嗣做全国模拟考试题中的最后一道数学题~在FOX热播美剧《Fringe》中更是无数次引用,甚至作为全剧宣传海报的设计元素之一。

    推广/斐波那契数列 编辑

    斐波那契—卢卡斯数列

    卢卡斯数列1、3、4、7、11、18…,也具有斐波那契数列同样的性质。(我们可称之为斐波那契—卢卡斯递推:从第三项开始,每一项都等于前两项之和f(n) = f(n-1)+ f(n-2)。

    卢卡斯数列的通项公式为 f(n)=[(1+√5)/2]^n+[(1-√5)/2]^n

    这两个数列还有一种特殊的联系(如下表所示),F(n)*L(n)=F(2n),及L(n)=F(n-1)+F(n+1)

    类似的数列还有无限多个,我们称之为斐波那契—卢卡斯数列。

    如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),

    ②任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得,如

    黄金特征与孪生斐波那契—卢卡斯数列

    斐波那契—卢卡斯数列的另一个共同性质:中间项的平方数与前后两项之积的差的绝对值是一个恒值,

    斐波那契数列:|1*1-1*2|=|2*2-1*3|=|3*3-2*5|=|5*5-3*8|=|8*8-5*13|=…=1

    卢卡斯数列:|3*3-1*4|=|4*4-3*7|=…=5

    F[1,4]数列:|4*4-1*5|=11

    F[2,5]数列:|5*5-2*7|=11

    F[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的递推规则:P1=1,P2=2,Pn=P(n-2)+2P(n-1).

    据此类推到所有根据前两项导出第三项的通用规则:f(n) = f(n-1) * p + f(n-2) * q,称为广义斐波那契数列。

    当p=1,q=1时,我们得到斐波那契—卢卡斯数列。

    当p=1,q=2时,我们得到佩尔—勾股弦数(跟边长为整数的直角三角形有关的数列集合)。

    当p=2,q=-1时,我们得到等差数列。其中f1=1,f2=2时,我们得到自然数列1,2,3,4…。自然数列的特征就是每个数的平方与前后两数之积的差为1(等差数列的这种差值称为自然特征)。

    具有类似黄金特征、勾股特征、自然特征的广义——斐波那契数列p=±1。

    当f1=1,f2=2,p=2,q=0 时,我们得到等比数列1,2,4,8,16……

    相关数学/斐波那契数列 编辑

    排列组合

    有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

    这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法……

    1,2,3,5,8,13……所以,登上十级,有89种走法。

    类似的,一枚均匀的硬币掷10次,问不连续出现正面的可能情形有多少种?

    答案是(1/√5)*{[(1+√5)/2]^(10+2) - [(1-√5)/2]^(10+2)}=144种。

    求递推数列a⑴=1,a(n+1)=1+1/a(n)的通项公式

    由数学归纳法可以得到:a(n)=F(n+1)/F(n),将斐波那契数列的通项式代入,化简就得结果。

    兔子繁殖问题

    斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

    一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,那么一年以后可以繁殖多少对兔子?

    我们不妨拿新出生的一对小兔子分析一下:

    第一个月小兔子没有繁殖能力,所以还是一对

    两个月后,生下一对小兔对数共有两对

    三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

    ------

    依次类推可以列出下表:

    幼仔对数=前月成兔对数

    成兔对数=前月成兔对数+前月幼仔对数

    总体对数=本月成兔对数+本月幼仔对数

    可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

    这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}(n=1,2,3,...)

    数列与矩阵

    对于斐波那契数列1、1、2、3、5、8、13、……。有如下定义

    F(n)=F(n-1)+F(n-2)

    F(1)=1

    F(2)=1

    对于以下矩阵乘法

    F(n+1) = (1,1 ) (F(n),F(n-1))

    F(n) =(1,0 ) (F(n),F(n-1))

    它的运算就是右边的矩阵 (1,1)乘以矩阵(F(n),F(n-1)),右边的矩阵(1,0 ) 乘以矩阵(F(n),F(n-1)),得到:

    F(n+1)=F(n)+F(n-1)

    F(n)=F(n)

    可见该矩阵的乘法完全符合斐波那契数列的定义

    设矩阵A=第一行(1,1)第二行(1,0) 迭代n次可以得到:F(n+1) =A^(n) *( F(2),F(1)) = A^(n)*(1,1)

    这就是斐波那契数列的矩阵乘法定义。

    另矩阵乘法的一个运算法则A^n(n为偶数) = A^(n/2)* A^(n/2),这样我们通过二分的思想,可以实现对数复杂度的矩阵相乘。

    因此可以用递归的方法求得答案。

    数列值的另一种求法

    F(n) = [ (( sqrt ( 5 ) + 1 ) / 2) ^ n ]

    其中[ x ]表示取距离 x 最近的整数。

    斐波那契弧线/斐波那契数列 编辑

    斐波那契数列 斐波那契数列

    斐波那契弧线,也称为斐波那契扇形线。第一,此趋势线以二个端点为准而画出,例如,最低点反向到最高点线上的两个点。然后通过第二点画出一条“无形的(看不见的)”垂直线。然后,从第一个点画出第三条趋势线:38.2%, 50%和61.8%的无形垂直线交叉。

    斐波纳契弧线,是潜在的支持点和阻力点水平价格。斐波纳契弧线和斐波纳契扇形线常常在图表里同时绘画出。支持点和阻力点就是由这些线的交汇点得出。

    要注意的是弧线的交叉点和价格曲线会根据图表数值范围而改变,因为弧线是圆周的一部分,它的形成总是一样的。

    C++代码实现/斐波那契数列 编辑

    基本循环算法  

    递归算法实现

    递归算法优化(记忆化搜索)

    高精度计算

    python3代码实现/斐波那契数列 编辑

    添加视频 | 添加图册相关影像

    扩展阅读
    1lava-lava.com
    2斐波那契数列的通项公式推导

    互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。未经许可,禁止商业网站等复制、抓取本站内容;合理使用者,请注明来源于www.baike.com。

    登录后使用互动百科的服务,将会得到个性化的提示和帮助,还有机会和专业认证智愿者沟通。

    互动百科用户登录注册
    此词条还可添加  信息模块

    WIKI热度

    1. 编辑次数:31次 历史版本
    2. 参与编辑人数:19
    3. 最近更新时间:2019-04-29 08:13:29

    互动百科

    扫码下载APP