斐波那契數列在代碼中的應用是比較常見的，下麵讓我們來瞭解下一個數學上的數列在代碼中會有哪些應用。瞭解斐波那契，可以給我們提供解決某些問題的思路，優化解決問題的方法。 ...
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、合併排序演算法
在合併排序演算法中，斐波那契數列可以用於確定合併的子數組大小。
合併排序是一種基於分治思想的排序演算法，它將待排序的數組不斷地拆分為較小的子數組，並對這些子數組進行排序，然後再將排好序的子數組合併為一個有序數組。斐波那契數列在確定子數組大小時可以發揮作用。
具體應用如下：
- 確定初始子數組大小：在合併排序的初始階段，需要確定用於拆分數組的子數組大小。常規的合併排序演算法中，通常選擇固定的子數組大小（例如2）。而使用斐波那契數列則可以提供更靈活的選項。通過斐波那契數列，可以依次選擇遞增的子數組大小，使得拆分後的子數組大小趨近於黃金比例（1:1.618），以達到更好的平衡。
- 動態調整子數組大小：在合併排序的過程中，當兩個子數組合併時，需要確定合併後的子數組大小。傳統的合併排序中，通常是將兩個子數組完全合併為一個新的子數組。而使用斐波那契數列，則可以根據斐波那契數列的順序，選擇部分元素進行合併，以減少合併操作的次數。這樣可以降低演算法的複雜度。
斐波那契數列在合併排序演算法中的應用，主要是為了確定子數組的大小，以實現更靈活和高效的排序過程。利用斐波那契數列的特性，可以使合併排序演算法更加平衡、快速和優化。
本文原創，才疏學淺，如有紕漏，歡迎指正。如果本文對您有所幫助，歡迎點贊，並期待您的反饋交流，共同成長。
原文地址： https://www.emanjusaka.top/archives/9
微信公眾號：emanjusaka的編程棧
