Fibonacci sequence - 学习笔记

S1gMa · 2021-10-31 02:10:34 · 个人记录

1.斐波那契数列定义：

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”在数学上，斐波那契数列以如下被以递推的方法定义：

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

这个数列的前几项为：

0、1、1、2、3、5、8、13、21、34......

2.公式推导

我们假设有一个等比数列 \left\{ x^n \right\} ，公比是 x，x 不为 0，首项为 1，可以满足斐波那契数列的递推公式，于是就有：

x^{n+2} = x^{n+1} + x^{n}

将等比数列 \left\{ x^n \right\} 代入递推式中得到，提取 x^n ，移项，即有：

(x^2 - x - 1)x^n = 0

由于 x^n \ne 0 可得：

x^2 - x - 1= 0

也就是说等比数列: \left\{ x_1^n \right\} , \left\{ x_2^n \right\} , 是满足斐波那契数列递推公式的两个解，但是实际上这两个等比数列都不是斐波那契数列的通项公式，既然单独的解不是，那么它们的组合呢？容易验证它们的线性组合，即：

c_1x_1^n+c_2x_2^n

为了确定这两个常数，我们需要数列的前两项作为初始因子。细想一下，一个数列怎么能没有首项呢？例如等差数列由首项和公差确定，等比数列由首项公比确定，公差和公比至少需要数列的前两项确定，将 $F_1$, $F_2$, 代入线性组合的式子里，可得： > $ \left\{\begin{aligned} & c_1 \cdot (\frac{1+\sqrt{5} }{2}) + c_2\cdot \frac{1-\sqrt{5} }{2} = 1 & \\ & c_1 \cdot (\frac{1+\sqrt{5} }{2})^2 + c_2\cdot (\frac{1-\sqrt{5} }{2})^2 = 1 & \\ \end{aligned}\right.

于是斐波那契数列的通项公式为：

F_{n} = \frac{1}{\sqrt{5} }[(\frac{1+\sqrt{5} }{2})^n - (\frac{1-\sqrt{5} }{2})^n]

3. 实际应用：

当我们学会了Fibonacci数列之后我们可以用到什么实际地方呢？

1、黄金分割

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

2、矩形面积

斐波那契数列与矩形面积的生成相关，由此可以导出一个斐波那契数列的一个性质。斐波那契数列前几项的平方和可以看做不同大小的正方形，由于斐波那契的递推公式，它们可以拼成一个大的矩形。这样所有小正方形的面积之和等于大矩形的面积

3、身份证校验码生成

斐波那契数列数列可以作为身份证校验码生成，一般会依据个人的手机号来求出具体求法即为：用个人手机号的后10位作为 tag ,求得 Fibonacci的前tag项的和，再取其后4位即为所求（编的。

4、尾数循环

斐波那契数列的个位数：一个60步的循环


11235,83145,94370,77415,61785.38190,

99875,27965,16730,33695,49325,72910…

进一步，斐波那契数列的最后两位数是一个 300 步的循环，最后三位数是一个 1500 步的循环，最后四位数是一个 15000 步的循环，最后五位数是一个 150000 步的循环。

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

斐波那契数列在欧美可谓是尽人皆知，于是在电影这种通俗艺术中也时常出现，比如在风靡一时的《达芬奇密码》里它就作为一个重要的符号和情节线索出现，在《魔法玩具城》里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。

在电视剧中也出现斐波那契数列，比如：日剧《考试之神》第五回，义嗣做全国模拟考试题中的最后一道数学题~在FOX热播美剧《Fringe》中更是无数次引用，甚至作为全剧宣传海报的设计元素之一。

6、杨辉三角

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

7、斐波那契数列数列求前 n 项的代码

int Fib(int n) 
{
    if(n == 0) 
        return 0;
    else if(n == 1)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}
//C++

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
//java

def fib(n):
    a, b = 1, 1
    for i in range(n-1):
        a, b = b, a+b
    return a
//python

以上便是所有斐波那契数列的学习笔记啦~~~，感谢学习！