斐波那契数列 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 斐波那契数列.

斐波那契数列

维基百科,自由的百科全书

此条目需要补充更多来源。 (2014年3月25日)请协助添加多方面可靠来源以改善这篇条目,无法查证的内容可能会因为异议提出而移除。
以斐波那契数为边的正方形拼成的近似的黄金矩形(1:1.618)
以斐波那契数为边的正方形拼成的近似的黄金矩形(1:1.618)

斐波那契数列意大利语:Successione di Fibonacci),又译为菲波拿契数列菲波那西数列斐氏数列黄金分割数列

数学上,斐波那契数列是以递归的方法来定义:

  • (n≧2)

用文字来说,就是斐波那契数列由0和1开始,之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的数列A000045

特别指出0不是第一项,而是第零项。

源起

根据高德纳(Donald Ervin Knuth)的《计算机程序设计艺术》(The Art of Computer Programming),1150年印度数学家Gopala和金月在研究箱子包装对象长宽刚好为1和2的可行方法数目时,首先描述这个数列。在西方,最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契Leonardo Fibonacci),他描述兔子生长的数目时用上了这数列:

兔子对的数量就是斐波那契数列
兔子对的数量就是斐波那契数列
  • 第一个月初有一对刚诞生的兔子
  • 第二个月之后(第三个月初)它们可以生育
  • 每月每对可生育的兔子会诞生下一对新兔子
  • 兔子永不死去

假设在n月有兔子总共a对,n+1月总共有b对。在n+2月必定总共有a+b对:因为在n+2月的时候,前一月(n+1月)的b对兔子可以存留至第n+2月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在n月就已存在的a对

斐波纳契数是帕斯卡三角形的每一条红色对角线上数字的和。
斐波纳契数是帕斯卡三角形的每一条红色对角线上数字的和。

斐波纳契数也是帕斯卡三角形的每一条红色对角线上数字的和。

表达式

为求得斐波那契数列的一般表达式,可以借助线性代数的方法。高中的初等数学知识也能求出。

初等代数解法

已知

首先构建等比数列


化简得

比较系数可得:

不妨设
解得:


又因为有, 即为等比数列。

求出数列{}

由以上可得:

变形得: 。 令

求数列{}进而得到{}


,解得。 故数列为等比数列
。而, 故有
又有
可得

得出表达式

线性代数解法

构建一个矩阵方程

设Jn为第n个月有生育能力的兔子数量,An为这一月份的兔子数量。

上式表达了两个月之间,兔子数目之间的关系。而要求的是,An+1的表达式。

求矩阵的特征值

行列式:

当行列式的值为0,解得==

特征向量

将两个特征值代入


求特征向量

=

=

分解首向量

第一个月的情况是兔子一对,新生0对。

将它分解为用特征向量表示。

(4)

数学归纳法证明

=

可得到

(5)

化简矩阵方程

将(4) 代入 (5)

根据3

求A的表达式

现在在6的基础上,可以很快求出An+1的表达式,将两个特征值代入6中

(7)

(7)即为An+1的表达式

数论解法

实际上,如果将斐波那契数列的通项公式写成,即可利用解二阶线性齐次递推关系式的方法,写出其特征多项式(该式和表达斐波那契数列的矩阵的特征多项式一致),然后解出==,即有,其中为常数。我们知道,因此,解得

组合数解法

[1]

近似值

用计算机求解

可通过编程观察斐波那契数列。分为两类问题,一种已知数列中的某一项,求序数。第二种是已知序数,求该项的值。

可通过递归递推的算法解决此两个问题。 事实上当n相当巨大的时候,O(n)的递推/递归非常慢……这时候要用到矩阵快速幂这一技巧,可以使递归加速到O(logn)。

和黄金分割的关系

开普勒发现数列前、后两项之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也组成了一个数列,会趋近黄金分割

斐波那契数亦可以用连分数来表示:

而黄金分割数亦可以用无限连分数表示:

而黄金分割数也可以用无限多重根号表示:

与平方数的关系

斐波那契数列中,只有3个平方数01144[2]

和自然的关系

许多的生物构成都和斐波那契数列有正相关。例如人体从脚底至头顶之距离和从肚脐至脚底之距趋近 ,向日葵种子螺旋排列有99%是[来源请求]

恒等式

资料来源:[3]

证明以下的恒等式有很多方法。以下会用组合论述来证明。

  • 可以表示用多个1和多个2相加令其和等于的方法的数目。

不失一般性,我们假设是计算了将1和2加到n的方法的数目。若第一个被加数是1,有种方法来完成对的计算;若第一个被加数是2,有来完成对的计算。因此,共有种方法来计算n的值。

计算用多个1和多个2相加令其和等于的方法的数目,同时至少一个加数是2的情况。

如前所述,当,有种这样的方法。因为当中只有一种方法不用使用2,就即 (项),于是我们从减去1。

  1. 若第1个被加数是2,有种方法来计算加至的方法的数目;
  2. 若第2个被加数是2、第1个被加数是1,有种方法来计算加至的方法的数目。
  3. 重复以上动作。
  4. 若第个被加数为2,它之前的被加数均为1,就有种方法来计算加至0的数目。

若该数式包含2为被加数,2的首次出现位置必然在第1和的被加数之间。2在不同位置的情况都考虑到后,得出为要求的数目。

定理

资料来源:[3]

特别地,当m = n时,

  • 整除,当且仅当n整除m,其中n≧3。
  • 任意连续三个菲波那契数两两互素,亦即,对于每一个n
gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = gcd(Fn+1, Fn+2) = 1

相关的数列

费波那西数列是费波那西n步数列步数为2的特殊情况,也和卢卡斯数列有关。

和卢卡斯数列的关系

反费波那西数列

反费波那西数列的递归公式如下:

如果它以1,-1,之后的数是:1,-1,2,-3,5,-8, ...

即是

反费波那西数列两项之间的比会趋近

巴都万数列

费波那西数列可以用一个接一个的正方形来表现,巴都万数列则是用一个接一个的等边三角形来表现,它有的关系。

佩尔数列

佩尔数列的递归公式为,前几项为0,1,2,5,12,29,70,169,408,...

应用

1970年,尤里·马季亚谢维奇指出了偶角标的斐波那契函数

正是满足Julia Robison假设的丢番图函数,因而证明了希尔伯特第十问题是不可解的。

相关猜想

斐波那契数列中是否存在无穷多个素数?

在斐波那契数列中,有素数: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917…… 目前已知最大素数是第81839个斐波那契数,一共有17103位数。

程序参考

JavaScript迭代

function fib(n) {
    var fib_n = function(curr, next, n) {
        if (n == 0) {
            return curr;
        }
        else {
            return fib_n(next, curr+next, n-1);
        }
    }
    return fib_n(0, 1, n);
}
alert(fib(40));

C语言通项公式版

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double constant_a = (1 + sqrt(5)) / 2;
    double constant_b = (1 - sqrt(5)) / 2;
    double constant_c = sqrt(5) / 5;
    double value_1 = 0;
    int value_2 = 0;
    scanf("%d", &n);
    if(n > 0)
    {
        for (int i = 0; i < n; i++)
        {
             value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
             value_2 = (int)value_1;
             printf("%d\n", value_2);
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

c++通项公式版

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    unsigned long long n;
    double ca = (1 + sqrt(5)) / 2;
    double cb = (1 - sqrt(5)) / 2;
    double cc = sqrt(5) / 5;
    double v1 = 0;
    double v2 = 0;
    cout <<" ";
    cin>>n;
    if(n > 0)
    {
        for (unsigned long long i = 0; i < n; i++)
    {
            v1 = cc * (pow(ca, i) - pow(cb, i));
        v2 = (int)v1;
        cout <<v2<<endl;
    }
    return 0;
    }
    else
    {
        return -1;
    }
        cout <<'/b';
}

Python语言通项公式版

# Fibonacci numbers module

def fib(n):    # write Fibonacci series up to n
    a, b = 0, 1
    while b < n:
        print(b, end=' ')
        a, b = b, a+b
    print()

def fib2(n):   # return Fibonacci series up to n
    result = []
    a, b = 0, 1
    while b < n:
        result.append(b)
        a, b = b, a+b
    return result
fibs = [0, 1]
numZS = int(input('How many Fibonacci numbers do you want? '))
for i in range(numZS-2):
    fibs.append(fibs[-2] + fibs[-1])
print fibs

Common Lisp

(defun fibs (x)
  (cond ((equal x 0) 1)
        ((equal x 1) 1)
        (t (+ (fibs (- x 1))
              (fibs (- x 2))))))

(defun fibs (x)
  (do ((n 0 (+ n 1))
       (i 1 j)
       (j 1 (+ i j)))
      ((equal n x) i)))

Go

递归版,时间复杂度为 O(2^n):

func fibonacci(n int) int {
	if n < 2 {
		return n
	}

	return fibonacci(n-2) + fibonacci(n-1)
}

通用版,时间复杂度为 O(n):

func fibonacci(n int) int {
	a, b := n%2, 1

	for i := 0; i < n/2; i++ {
		a += b
		b += a
	}

	return a
}

Java语言通项公式版:

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      return fibonacci(n-1)+fibonacci(n-2);
    }
}

Java语言快捷版:

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      int[] ans = new int[n];
          ans[0] = 1;
          ans[1] = 2;
          for(int i=2;i<n;i++) {
              ans[i]=ans[i-1]+ans[i-2];
          }
          return ans[n-1];
    }
}

C语言阵列版:

#include <stdio.h>
#include <stdlib.h> 
int main()
{   
     int n,s,L;
     printf("輸入長度");
     scanf("%d",&L);
     while(L<0)
     {
     	printf("錯誤"); 
     	return 0;
	 }
     int a[L]; 
     int x=1,y=2;
     a[0]=x;
     a[1]=x;
     a[2]=y;
	 for(n=3;n<L;n++)
	 {  
		 a[n]=a[n-1]+a[n-2];  	
	 }
       for(n=0;n<L;n++)
     {
         printf("%d ",a[n]);
     }
     system("pause");
     return 0;
}

Python Lambda 递归版:

fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)

参考文献

  • KNUTH, D. E. 1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.
  • Arakelian, Hrant (2014). Mathematics and History of the Golden Section. Logos, 404 p. ISBN 978-5-98704-663-0, (rus.)
  • 克里福德A皮科夫.数学之恋.湖南科技出版社.
  1. ^ 斐波那契数列与组合数的一个关系及推广. 
  2. ^ JOHN H. E. COHN. Square Fibonacci Numbers, Etc.. Bedford College, University of London, London, N.W.1. (原始内容存档于2012-06-30). Theorem 3. If Fn = x2, then n = 0, ±1, 2 or 12. 
  3. ^ 3.0 3.1 李晨滔、冯劲敏. 费氏数列的性质整理 (PDF). 桃园县立大园国际高中. 

参见

外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
斐波那契数列
Listen to this article