浅析斐波那契数列在代码中的应用
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、循环计算
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、乘法散列
乘法散列法整体包含两步：
<ul>用关键字k乘上常数A(0
页:
[1]