博客

详解斐波那契数列

什么是斐波那契数列？

斐波那契数列，又称黄金分割数列，指的是以下数列：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

其中，前两项是0和1，后面的每一项都是前面两项的和。即

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)  (n >= 2)

斐波那契数列的作用

斐波那契数列在数学、计算机科学等领域都有广泛的应用，下面列举几个常见的应用：

  1. 网格覆盖问题

如果有一个 $2 x n$ 的网格需要用 $1 x 2$ 的小矩形去覆盖，用几种不同的覆盖方法？

对于最左边一列，可以使用一个 $1 x 2$ 的矩形覆盖，或者两个 $1 x 1$ 的矩形分别覆盖。因此，针对最左边一列的覆盖情况可以分为两种：（1）用一个 $1 x 2$ 的矩形覆盖；（2）用两个 $1 x 1$ 的矩形覆盖。

针对第二列，也可以用一个 $1 x 2$ 的矩形覆盖，或者两个 $1 x 1$ 的矩形分别覆盖。但是，这里需要考虑第一列是用一个 $1 x 2$ 的矩形覆盖的情况，此时第二列只能用两个 $1 x 1$ 的矩形去覆盖；如果第一列是用两个 $1 x 1$ 的矩形分别覆盖的情况，则第二列既可以用一个 $1 x 2$ 的矩形覆盖，也可以用两个 $1 x 1$ 的矩形分别覆盖。因此，针对第二列的覆盖情况可以分为三种：（1）用一个 $1 x 2$ 的矩形覆盖；（2）用两个 $1 x 1$ 的矩形覆盖，且第一列也用两个 $1 x 1$ 的矩形覆盖；（3）用两个 $1 x 1$ 的矩形覆盖，且第一列用一个 $1 x 2$ 的矩形覆盖。

对于第 $n$ 列，可以用一个 $1 x 2$ 的矩形覆盖，或者两个 $1 x 1$ 的矩形分别覆盖。此时，对于最左边的 $n-1$ 列，已经求出了不同的覆盖情况，因此可以通过斐波那契数列来计算总的覆盖方法数。

  1. 加法运算

斐波那契数列也可以用来进行加法运算。具体做法如下：

  • 将两个加数转化为二进制形式
  • 对齐两个二进制数，补0使得两个数位数相同
  • 将两个二进制数从右往左一位一位地相加，得到每一位的和，如果是2则需要进一位

  • 将得到的数字再转化为十进制形式，即为加法的结果

  • 黄金分割

黄金分割点可以通过斐波那契数列来计算，具体做法如下：

  • 将相邻两项的比例作为近似黄金分割点，即 $\frac{f(n)}{f(n-1)}$

如何使用斐波那契数列

我们可以使用递归和循环两种方法来计算斐波那契数列：

递归算法

递归算法直观简单，但是当 $n$ 较大时，会进行大量重复计算，效率很低。

def fibonacci_recursion(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursion(n-1) + fibonacci_recursion(n-2)

循环算法

循环算法避免了重复计算，效率更高。

def fibonacci_loop(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a = 0
        b = 1
        for i in range(2, n+1):
            c = a + b
            a, b = b, c
        return c

示例

下面是如何使用斐波那契数列计算网格覆盖问题的例子：

def cover(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return cover(n-1) + cover(n-2)

n = 4
print(cover(n))    # 输出5

下面是如何使用斐波那契数列进行加法运算的例子：

def fibonacci_addition(a, b):
    f1 = 1
    f2 = 1
    while f2 < a:
        f1, f2 = f2, f1 + f2
    result = 0
    while b > 0:
        if b % 2 == 1:
            result += f2
        f1, f2 = f2 - f1, f1
        b //= 2
    return result

a = 5
b = 7
print(fibonacci_addition(a, b))    # 输出12
Tags: