浅析斐波那契数列在代码中的应用

by emanjusaka from ​ https://www.emanjusaka.top/archives/9 彼岸花开可奈何
本文欢迎分享与聚合，全文转载请留下原文地址。

前言

斐波那契数列在代码中的应用是比较常见的，下面让我们来了解下一个数学上的数列在代码中会有哪些应用。了解斐波那契，可以给我们提供解决某些问题的思路，优化解决问题的方法。
一、定义

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

• 从 F2 开始任意一位都是前两位之和。
  
• 从 F2 开始任意一位与前一位相比的比值，都无限趋近于 (√5 - 1)/2 = 0.618 因此基于黄金分割的计算应用，也被称为斐波那契应用。
  

二、三种计算方法

2.1、循环计算

1. public double fibonacci(int n) {
2.     int f1 = 1;
3.     int f0 = 0;
4.     if (n < 2) return n;
5.     int num = n - 1;
6.     while (num > 0) {
7.         f1 += f0;
8.         f0 = f1 - f0;
9.         num --;
10.     }
11.     return f1;
12. }

复制代码

2.2、递归计算

1. public int fibonacciRecursion(int n) {
2.     if (n < 2){
3.         return n;
4.     } else {
5.         return (fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2));
6.     }
7. }

复制代码

2.3、比奈公式

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

复制代码

三、散列函数

3.1、除法散列

在用来设计散列函数的除法散列法中，通过取 K 除以 M 的余数，将关键字 K 映射到 M 个槽中的某一个位置上，即散列函数为：h(K) = K mod M 表格大小通常是 2 的幂。
另外除法散列的一个显着缺点是除法在大多数现代架构（包括 x86）上都是微编程的，并且可能比乘法慢 10 倍。
3.2、乘法散列

乘法散列法整体包含两步：
<ul>用关键字k乘上常数A(0