斐波那契数列

递归
尾递归
迭代-数组
迭代-临时变量
通项公式
矩阵快速幂
卢卡斯数列
齐肯多夫定理
斐波那契编码

在数学中，斐波那契数列是其中每个元素都是其前面的两个元素之和的序列。斐波那契数列中的数字称为斐波那契数，通常表示为 Fₙ。许多作者从 0 和 1 开始序列，也有些作者从 1 和 1 开始，还有些作者从 1 和 2 开始。这里我们也从 0 和 1 开始。

递归

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

递归的代码简洁明了，但是存在大量重复计算，复杂度指数级别，运行效率极其低下。

尾递归

fun fib(n: Int, a: Int = 0, b: Int = 1): Int = if (n == 0) a else fib(n - 1, b, a + b)

尾递归一般比较难想到，主要是平时能见到的应用不多，更多的是为后续转化为循环迭代做准备，比如 kotlin 里使用 tailrec 标记尾递归可以被编译器自动优化成循环。

迭代-数组

fun fib(n: Int): Int {
    val dp = IntArray(n + 1) { it }
    for (i in 2..n) dp[i] = dp[i - 1] + dp[i - 2]
    return dp.last()
}

这大概是大多数人能想到的优化版本。

迭代-临时变量

fun fib(n: Int): Int {
    var a = 0
    var b = 1
    repeat(n) { b += a.apply { a = b } }
    return a
}

使用临时变量替代数组，降低空间复杂度。

通项公式

\[F_n = \tfrac{1}{\sqrt{5}}\Big [(\tfrac{1 + \sqrt{5}}{2})^n - (\tfrac{1 - \sqrt{5}}{2})^n\Big ]\]

数学理论上通项公式最快，复杂度 O(1)。
但在实际计算机工程应用中，浮点数计算的复杂度为 O(logn)，且浮点数存在运算精度问题。

矩阵快速幂

import kotlin.system.measureTimeMillis

class Matrix(private val arr: Array<out IntArray>) {
    val rows = arr.size
    val cols = if (arr.isNotEmpty()) arr[0].size else 0

    constructor(row: Int, init: (Int) -> IntArray) : this(Array(row, init))

    constructor(row: Int, col: Int, init: (Int, Int) -> Int = { _, _ -> 0 }) : this(
        Array(row) { r -> IntArray(col) { c -> init(r, c) } }
    )

    fun set(row: Int, col: Int, value: Int) {
        require(row in 0..<rows && col in 0..<cols) { "Index out of bounds: ($row, $col)" }
        arr[row][col] = value
    }

    fun get(row: Int, col: Int): Int {
        require(row in 0..<rows && col in 0..<cols) { "Index out of bounds: ($row, $col)" }
        return arr[row][col]
    }

    operator fun times(m: Matrix): Matrix {
        require(cols == m.rows) { "Matrix dimensions do not match for multiplication" }
        val product = Matrix(rows) { IntArray(m.cols) }
        repeat(rows) { r ->
            repeat(m.cols) { c ->
                product.set(r, c, (0..<cols).fold(0) { acc, i -> acc + this.get(r, i) * m.get(i, c) })
            }
        }
        return product
    }
}

// fun matrixOf(vararg elements: IntArray) = Matrix(elements.map { it.copyOf() }.toTypedArray()) // deep copy
fun matrixOf(vararg elements: IntArray) = Matrix(elements)

// n 阶单位矩阵
fun identityMatrix(n: Int): Matrix = Matrix(n, n) { r, c -> if (r == c) 1 else 0 }

fun fastExponentiationRec(matrix: Matrix, exp: Int): Matrix {
    if (exp == 1) return matrix
    val half = fastExponentiationRec(matrix, exp / 2)
    return if (exp % 2 == 0) half * half else half * half * matrix
}

fun fastExponentiation(matrix: Matrix, exp: Int): Matrix {
    var ret = identityMatrix(matrix.cols)
    var mul = matrix
    var n = exp
    while (n > 0) {
        if (n % 2 != 0) ret *= mul
        mul *= mul
        n /= 2
    }
    return ret
}

fun fib(n: Int): Int {
    if (n < 2) return n
    val init = matrixOf(intArrayOf(1), intArrayOf(0))
    val eigen = matrixOf(intArrayOf(1, 1), intArrayOf(1, 0))
    // return ((2..<n).fold(eigen) { matrix, _ -> matrix * eigen } * init).get(0, 0) // no fast exponentiation
    return (fastExponentiation(eigen, n - 1) * init).get(0, 0)
}

fun main() {
    testCorrection(20)
    testTime(1_000_000)
}

fun testCorrection(n: Int) {
    // 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
    println((1..n).map(::fib).joinToString())
}

fun testTime(n: Int) {
    var fn: Int
    val time = measureTimeMillis { fn = fib(n) }
    println("Fibonacci($n) = $fn, time: $time ms")
}

欢迎来到线性代数的世界，显然：

\[\left\{ \begin{array}{l} F_2 = F_1 + F_0 \\ F_1 = F_1 \end{array} \right.\]

使用矩阵表示上述等式关系：

\[\bigg [ \begin{matrix} F_2 \\ F_1 \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ] \times \bigg [ \begin{matrix} F_1 \\ F_0 \end{matrix} \bigg ]\]

那么：

\[\bigg [ \begin{matrix} F_3 \\ F_2 \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ] \times \bigg [ \begin{matrix} F_2 \\ F_1 \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ]^2 \times \bigg [ \begin{matrix} F_1 \\ F_0 \end{matrix} \bigg ]\]

一般地：

\[\bigg [ \begin{matrix} F_n \\ F_{n-1} \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ] \times \bigg [ \begin{matrix} F_{n-1} \\ F_{n-2} \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ]^{n-1} \times \bigg [ \begin{matrix} F_1 \\ F_0 \end{matrix} \bigg ] = \bigg [ \begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \bigg ]^{n-1} \times \bigg [ \begin{matrix} 1 \\ 0 \end{matrix} \bigg ]\]

斐波那契数列增长很快，上面的 Int 版本很容易整数溢出，即便是 Long 类型也在 n=562 时就溢出了，有需要的可以使用 BigInteger 来实现。

卢卡斯数列

占坑

齐肯多夫定理

坑 2

斐波那契编码

坑 3

目录

递归