费氏数列：从兔子问题到黄金比例

费氏数列：从兔子问题到黄金比例

费氏数列（Fibonacci sequence）是数学中一个著名的数列，由意大利数学家斐波那契（Fibonacci）在1202年发表的《Liber abacci》中首次提出。这个数列不仅在数学领域有着广泛的应用，还在自然界中展现出惊人的规律性。本文将详细介绍费氏数列的定义、性质以及多种计算方法。

费氏数列的定义与性质

欧洲数学家Fibonacci在1202年发表的《Liber abacci》中曾经提过一个“免子算术”：“若有兔子每个 month 生一隻小兔子，一个 month 后小兔子也投入生产，那么一開始是一隻兔子，一個 month 後就有兩隻兔子，二個 month 後有三隻兔子，三個 month 後有五隻兔子……”如果将每个月的数量逐一写下，会是 1、1、2、3、5、8、13、21、34、55、89……

这个数列可以归纳为以下公式：

$$
F_0 = 0 \
F_1 = 1 \
F_n = F_{n-1} + F_{n-2}
$$

如果某个费氏数除以上一个费氏数，比例会接近 1.618，也就是黄金比例，越大的费氏数相除会越接近这个数字；相对地，如果某个费氏数除以下一个费氏数，比例会接近0.618，也就是黄金分割比，它是最难用有理数逼近的无理数。

解法思路

费氏数列的解法很多，基本上可以使用递归解：

Procedure FIB(N) 
    IF (N = 0 OR N = 1) 
        RETURN N
    ELSE 
        RETURN FIB(N - 1) + FIB(N - 2)

不过在求每个费氏数时，都会发生重复计算，效率不佳，单就执行次数上来说，有个使用递归的算法会比较少：

Procedure FIB(N) 
    IF (N <= 1)
        RETURN N; 
    IF (N = 2) 
        RETURN 1; 
    ELSE 
        i = N / 2; 
        f1 = FIB(i + 1)
        f2 = FIB(i)
        IF (N mod 2 = 0)
            RETURN f2 * (2 * f1 + f2)
        ELSE 
            RETURN f1² + f2²

如果使用循环解：

Procedure FIB(N) 
    IF (N = 0 OR N = 1) 
        RETURN N
    a = 0; 
    b = 1; 
    FOR i = 2 TO N 
        temp = b
        b = a + b
        a = temp
    RETURN b;  

若想一次列出 N 之前的费氏数，可以使用数组：

F[0] = 0
F[1] = 1
FOR i <- 2 TO N 
    F[i] = F[i - 1] + F[i - 2]

如果用矩阵来解费氏数列，可以使用以下：

那个矩阵称为费氏 Q-Matrix，问题就变成矩阵的 n 次方问题。

想解决矩阵的 n 次方问题，方式之一是参考整数次方演算的快速次方演算，依照相同的概念，也可以实现实现矩阵版本的快速次方演算，用以求得费氏数。

当然，如果你熟悉线性代数的话，可以先求得特征值（eigenvalues）与特征向量（eigenvectors），进一步求得矩阵的 n 次方，最后可以推导，得到以下的公式，不过这个公式中会用到 √5，如果你在电脑中只是用 sqrt(5) 之类的方式求 √5，结果与真正的 √5 还是有误差的，如果你的 N 很大，误差会被放大，也就不准确了，虽然也可以进一步使用更高的精度，不过得衡量是不是真的有效率，毕竟更高精度的运算并不是没有代价：

如果兔子不只生一隻小兔子的话怎麼辦？這稱為擴充費氏數列：

F₀ = 0
F₁ = 1
Fₙ = X * Fₙ₋₁ + Y * Fₙ₋₂

当 X、Y 等于1时，就是一般的费氏数列了，费氏数列与自然界有神奇的關係，有兴趣可以进一步参考《兔子、凤梨、向日葵、帕德能廟、正十边形、鹦鹉螺》。

来改变一下，现在不是兔子，而是树枝成长，若有树枝每个 month 分出一根树枝，一个 month 新树枝也投入生产，那么一開始是一根树枝，一个 month 後就有两根树枝，二个 month 後有三根树枝，三个 month 後有五根树枝……下图画出了过程：

这模拟了树枝成长的过程，其中蓝色部分是成熟的树枝，每个 month 会分出新枝，白色的是新分支，一个 month 才会分支，当然，早成熟的树枝也会越长越粗壮，如果绘图时也考虑树枝要长粗，就可能一棵树的样态了。

《巴斯卡三角形》里隐藏着费氏数列；你可以使用费氏数列来进行《费氏搜索》。

以下的黄金矩形图片，由数个正方形组成，而正方形的边长关系，就符合 Fibonacci 数列：

黄金螺线可以将黄金矩形中每个正方形的两个对角，使用圆弧连接起来：

费氏晶格（Fibonacci lattice）演算演算中用到了黄金分割计算黄金角，因而以费氏为名，可以用來模仿向日葵的花蕊图样：

下图是三維版本的费氏晶格演算：

程序实现

以下是使用不同编程语言实现费氏数列的代码示例：

C语言

#include <stdio.h> 
#include <stdlib.h> 
#define LEN 20 
void fill_fibonacci_numbers(int*, int);
void print(int*, int len);
    
int main() {
    int fib[LEN];
    fill_fibonacci_numbers(fib, LEN);
    print(fib, LEN);
    return 0; 
} 
void fill_fibonacci_numbers(int* fib, int len) {
    int i;
    for(i = 2; i < len; i++) {
        fib[i] = fib[i-1] + fib[i-2]; 
    }
}
void print(int* arr, int len) {
    int i;
    for(i = 0; i < len; i++) { printf("%d ", arr[i]); } 
}

Java

import java.util.*;
public class Fibonacci {
    private List<Integer> fib = new ArrayList<>();
    {
        fib.add(0);
        fib.add(1);
    }
    
    public int get(int n) {
        if(n >= fib.size()) for(int i = fib.size(); i <= n; i++) {
            fib.add(fib.get(i - 1) + fib.get(i - 2));
        }
        return fib.get(n);
    }
    
    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        for(int i = 0; i < 20; i++) {
            System.out.print(fibonacci.get(i) + " ");
        }
    }
}

Python

def fibonacci(n, fib = [0, 1]):
    if n >= len(fib):
        for i in range(len(fib), n + 1):
            fib.append(fib[i - 1] + fib[i - 2])
    return fib[n]

for i in range(20):
    print(fibonacci(i), end=' ')

Scala

def fib(n: Int): Int = n match {
    case 0 => 0
    case 1 => 1
    case _ => fib(n - 1) + fib(n - 2)
}
(for(i <- 0 until readInt) yield fib(i)).foreach(i => print(i + " "))

Ruby

# encoding: UTF-8
fibonacci = -> {
    -> n { 
            fib.size.upto(n) do |i|
                fib << fib[i - 1] + fib[i - 2]
            end
        end
        fib[n]
    }
}.call
print "輸入個數："
0.upto(length - 1) do |i|
    print fibonacci.call(i).to_s + ' '
end

JavaScript

var fibonacci = function() {
    var fib = [0, 1];
        if(n >= fib.length) for(var i = fib.length; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    };
}();
    
for(var i = 0; i < 20; i++) { print(fibonacci(i)); }

Haskell

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = addPrevsRecusivelyUntilCounterIsN (fib 1) (fib 0) 2 n
addPrevsRecusivelyUntilCounterIsN prev1 prev2 counter n
    | otherwise = addPrevsRecusivelyUntilCounterIsN result prev1 (counter + 1) n
    where result = prev1 + prev2
main = sequence [print (fibonacci i) | i <- [0..19]]

Prolog

fibonacci(N, Result) :- NP1 is N - 1, NP2 is N - 2, 
                        fibonacci(NP1, FP1), fibonacci(NP2, FP2), 
                        Result is FP1 + FP2.
fibonacci(0, 0).
fibonacci(1, 1).

main([Arg0|_]) :-
        atom_number(Arg0, N),
        fibonacci(N, Result),
        writef("The nth %n is %d\n", [Arg0, Result]).

Toy Lang

# 我写的玩具语言 https://github.com/JustinSDK/toy_lang
def fib(n) {
    if n == 0 or n == 1 {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}
iterate(0, 10).forEach(i -> println(fib(i)))