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

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

前言

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

一、定义

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

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

二、三种计算方法

2.1、循环计算

public double fibonacci(int n) {
    int f1 = 1;
    int f0 = 0;
    if (n  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  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