by emanjusaka from  https://www.emanjusaka.top/archives/9 彼岸花開可奈何
本文歡迎分享與聚合，全文轉載請留下原文地址。

前言

斐波那契數列在程式碼中的應用是比較常見的，下面讓我們來了解下一個數學上的數列在程式碼中會有哪些應用。瞭解斐波那契，可以給我們提供解決某些問題的思路，優化解決問題的方法。

一、定義

F0 = 0，F1 = 1，Fn = F(n - 1) + F(n - 2)

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

從 F2 開始任意一位都是前兩位之和。
從 F2 開始任意一位與前一位相比的比值，都無限趨近於 (√5 - 1)/2 = 0.618 因此基於黃金分割的計算應用，也被稱為斐波那契應用。

二、三種計算方法

2.1、迴圈計算

public double fibonacci(int n) {
    int f1 = 1;
    int f0 = 0;
    if (n < 2) return n;
    int num = n - 1;
    while (num > 0) {
        f1 += f0;
        f0 = f1 - f0;
        num --;
    }
    return f1;
}

2.2、遞迴計算

public int fibonacciRecursion(int n) {
    if (n < 2){
        return n;
    } else {
        return (fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2));
    }
}

2.3、比奈公式

public double fibonacciClosedForm(long position) {
    int maxPosition = 75;
    if (position < 1 || position > maxPosition) {
        throw new RuntimeException("Can't handle position smaller than 1 or greater than 75");
    }
    double sqrt = Math.sqrt(5);
    double phi = (1 + sqrt) / 2;
    return Math.floor((Math.pow(phi, position)) / sqrt + 0.5);
}

三、雜湊函數

3.1、除法雜湊

在用來設計雜湊函數的除法雜湊法中，通過取 K 除以 M 的餘數，將關鍵字 K 對映到 M 個槽中的某一個位置上，即雜湊函數為：h(K) = K mod M 表格大小通常是 2 的冪。

另外除法雜湊的一個顯著缺點是除法在大多數現代架構（包括 x86）上都是微程式設計的，並且可能比乘法慢 10 倍。

3.2、乘法雜湊

乘法雜湊法整體包含兩步：

用關鍵字k乘上常數A(0<A<1)，並去除kA的小數部分
用m乘以這個值，再取結果的底floor 公式：h(K)=Math.floor[m(aK mod 1)]

步驟：

假設某計算機的字長為 ww 位，而 kk 正好可容於一個字中(k<2wk<2w)
現在選取範圍[0，2w]內的任意數值 ss，k×sk×s 即可用R1·2w+R0R1·2w+R0來表示
因此(k·A)mod1=k·s/2w(k·A)mod1=k·s/2w就是將k×sk×s整體向右平移 ww 位，此時R0R0即為小數部分
再乘以 2m2m 相當於左移 mm 位，雜湊值h(k)h(k) 為 R0R0 的前 m 位。

乘法雜湊只需要單個整數乘法和右移，使其成為計算速度最快的雜湊函數之一。但乘法雜湊可能會在變更計算因子後，較高值的輸入位不會影響較低值的輸出位，問題體現在元素分散不均，不滿足嚴格的雪崩標準。所以通常在會進行互斥或操作

乘法雜湊容易受到導致擴散不良的「常見錯誤」的影響——較高值的輸入位不會影響較低值的輸出位。在乘法步驟對此進行校正之前，輸入上的變換將保留的最高位的跨度向下移動，並將它們互斥或或加到鍵上。所以在輸入上的變換將保留的最高位的跨度向下移動，並將它們互斥或操作或者加到鍵上。例如 HashMap 的擾動函數。

3.3、斐波那契雜湊

其實斐波那契雜湊是一種特殊形式的乘法雜湊，只不過它的乘法因子選擇的是一個黃金分割比例值，所以叫做斐波那契雜湊。

斐波那契雜湊的特性在於將「大數對映到小數」的計算結果在表空間上是均勻分佈的，且計算滿足乘法雜湊效率高。

四、簡單應用

4.1、偽亂數生成

斐波那契數列可以用於生成偽亂數序列。雖然斐波那契數列本身不是真正的亂數序列，但通過適當的變換和擷取，可以得到具有一定隨機性的序列。

package top.emanjusaka;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        System.out.println(fibonacciRandom(5, 8));
    }

    public static List<Integer> fibonacciRandom(int seed, int length) {
        List<Integer> fibSequence = new ArrayList<>(Arrays.asList(0, 1));
        while (fibSequence.size() < seed + length) {
            int nextNumber = fibSequence.get(fibSequence.size() - 1) + fibSequence.get(fibSequence.size() - 2);
            fibSequence.add(nextNumber);
        }
        List<Integer> randomSequence = new ArrayList<>();
        for (int i = seed; i < seed + length; i++) {
            randomSequence.add(fibSequence.get(i));
        }
        return randomSequence;
    }
}

4.2、AVL 二元樹

在AVL樹中，斐波那契數列可以用於平衡因子的調整和旋轉操作。

AVL樹是一種自平衡二元搜尋樹，它要求左右子樹的高度差不超過1，以保持樹的平衡性。當對AVL樹進行插入或刪除操作時，可能會破壞樹的平衡，這時需要對樹進行旋轉操作來恢復平衡。

在AVL樹的旋轉操作中，涉及到更新節點的高度資訊。通常，節點的高度可以通過其子節點的高度來計算。而斐波那契數列正好提供了方便的計算方式。

具體應用如下：

插入操作：當在AVL樹中插入一個節點時，會導致從插入節點到根節點路徑上的某些節點的平衡因子發生變化。通過向上回溯，我們可以更新路徑上的節點的高度，並檢查它們的平衡狀態。如果某個節點的平衡因子超過了允許的範圍，就需要進行旋轉操作來恢復平衡。在這個過程中，斐波那契數列可以用於更新節點的高度資訊。
刪除操作：當從AVL樹中刪除一個節點時，也會導致樹的平衡性被破壞。類似插入操作，我們需要從刪除節點的父節點向上回溯並更新節點的高度資訊。如果某個節點的平衡因子超過了允許的範圍，就需要進行旋轉操作來恢復平衡。斐波那契數列可以用於更新高度資訊。
旋轉操作：斐波那契數列在AVL樹的旋轉操作中扮演了重要的角色。旋轉操作包括左旋和右旋，它們通過改變樹的結構來保持平衡。在旋轉操作中，涉及到節點的高度資訊的更新，而斐波那契數列可以方便地計算節點的高度。

4.3、最大公約數

斐波那契數列在最大公約數計算中有一個有趣的應用，稱為"連續整除性質"。

假設我們有兩個正整數a和b，並且a > b。如果a可以被b整除，那麼a與斐波那契數列中位於第a個位置（從1開始計數）的數具有相同的最大公約數。換句話說，gcd(a, b) = gcd(b, F(a))，其中F(n)表示斐波那契數列中第n個數。

這個性質的證明基於斐波那契數列的遞推關係和歐幾里得演演算法的原理。簡單來說，當a能夠被b整除時，可以將a表達為b的倍數加上剩餘部分，即a = qb + r，其中q是商，r是餘數。然後我們可以使用斐波那契數列的遞推關係，即F(n) = F(n-1) + F(n-2)，將a和b替換為它們的等價表示式：

gcd(a, b) = gcd(qb + r, b) = gcd(b, r)

這就意味著最初的問題可以轉化為更小的問題，即求b和r的最大公約數。通過重複應用這個性質，我們最終可以將問題簡化為求最小的b和斐波那契數列中的一個數之間的最大公約數。

這個連續整除性質可以用於計算任意兩個正整數的最大公約數，而不需要直接使用輾轉相除法。通過與斐波那契數列相關聯，它提供了一種更高效的方法來計算最大公約數。

需要注意的是，連續整除性質只適用於a > b的情況，因此在應用時需要確保a和b的大小順序。

4.4、合併排序演演算法

在合併排序演演算法中，斐波那契數列可以用於確定合併的子陣列大小。

合併排序是一種基於分治思想的排序演演算法，它將待排序的陣列不斷地拆分為較小的子陣列，並對這些子陣列進行排序，然後再將排好序的子陣列合併為一個有序陣列。斐波那契數列在確定子陣列大小時可以發揮作用。