费氏数列：从起源到实现

费氏数列：从起源到实现

费氏数列（Fibonacci sequence）是欧洲数学家斐波那契（Fibonacci）在1202年发表的《Liber abacci》中提出的一个著名数列。这个数列源于一个“兔子繁殖”的问题：假设一对兔子每个月能生一对小兔子，而新生的小兔子在出生后第二个月就能开始繁殖。那么，从一对兔子开始，每个月的兔子总数会形成一个特定的数列：1、1、2、3、5、8、13、21、34、55、89……

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

F₀ = 0
F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂

费氏数列的一个有趣性质是：随着数列的延伸，相邻两项的比值会越来越接近黄金比例（约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;  

数组解法

如果需要生成整个数列，可以使用数组：

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

矩阵解法

费氏数列也可以通过矩阵运算来求解。具体来说，可以使用费氏Q-Matrix：

通过快速幂算法可以高效地计算矩阵的n次方。

扩展与应用

费氏数列可以扩展为更一般的数列：

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

当X和Y都等于1时，就是标准的费氏数列。费氏数列在自然界中有很多体现，如树枝生长、向日葵的花盘等。

程序实现

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

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];
        return function(n) {
            if(n >= fib.length) for(var i = fib.length; i <= n; i++) {
                fib[i] = fib[i - 1] + fib[i - 2];
            }
            return fib[n];
        };
}();
    
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.

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

Toy Language

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

费氏数列不仅在数学领域有重要地位，在计算机科学、自然科学研究等领域也有广泛应用。通过本文的介绍，读者可以全面了解费氏数列的定义、性质以及多种实现方法。