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

浅析,数列,代码,应用 · 浏览次数 : 71

小编点评

**最大公约数斐波那契数列** **4.3、最大公约数斐波那契数列** 斐波那契数列是一种递推关系的数列,可用于计算任意两个正整数的最大公约数。通过利用斐波那契数列,我们可以简化求最大公约数的步骤,并获得更高效的算法。 **4.4、合并排序算法在合并排序算法中** 斐波那契数列可用于确定合并的子数组大小。在合并排序的初始阶段,我们可以选择斐波那契数列的递推关系,以确定子数组大小。这样可以获得更平衡的排序过程,并以降低算法的复杂度。 **斐波那契数列的应用** 斐波那契数列可用于以下应用: * 计算任意两个正整数的最大公约数 * 确定合并的子数组大小 * 高效的合并排序算法 * 减少算法复杂度的排序算法

正文

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树的旋转操作中,涉及到更新节点的高度信息。通常,节点的高度可以通过其子节点的高度来计算。而斐波那契数列正好提供了方便的计算方式。

具体应用如下:

  1. 插入操作:当在AVL树中插入一个节点时,会导致从插入节点到根节点路径上的某些节点的平衡因子发生变化。通过向上回溯,我们可以更新路径上的节点的高度,并检查它们的平衡状态。如果某个节点的平衡因子超过了允许的范围,就需要进行旋转操作来恢复平衡。在这个过程中,斐波那契数列可以用于更新节点的高度信息。
  2. 删除操作:当从AVL树中删除一个节点时,也会导致树的平衡性被破坏。类似插入操作,我们需要从删除节点的父节点向上回溯并更新节点的高度信息。如果某个节点的平衡因子超过了允许的范围,就需要进行旋转操作来恢复平衡。斐波那契数列可以用于更新高度信息。
  3. 旋转操作:斐波那契数列在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、合并排序算法

在合并排序算法中,斐波那契数列可以用于确定合并的子数组大小。

合并排序是一种基于分治思想的排序算法,它将待排序的数组不断地拆分为较小的子数组,并对这些子数组进行排序,然后再将排好序的子数组合并为一个有序数组。斐波那契数列在确定子数组大小时可以发挥作用。

具体应用如下:

  1. 确定初始子数组大小:在合并排序的初始阶段,需要确定用于拆分数组的子数组大小。常规的合并排序算法中,通常选择固定的子数组大小(例如2)。而使用斐波那契数列则可以提供更灵活的选项。通过斐波那契数列,可以依次选择递增的子数组大小,使得拆分后的子数组大小趋近于黄金比例(1:1.618),以达到更好的平衡。
  2. 动态调整子数组大小:在合并排序的过程中,当两个子数组合并时,需要确定合并后的子数组大小。传统的合并排序中,通常是将两个子数组完全合并为一个新的子数组。而使用斐波那契数列,则可以根据斐波那契数列的顺序,选择部分元素进行合并,以减少合并操作的次数。这样可以降低算法的复杂度。

斐波那契数列在合并排序算法中的应用,主要是为了确定子数组的大小,以实现更灵活和高效的排序过程。利用斐波那契数列的特性,可以使合并排序算法更加平衡、快速和优化。

本文原创,才疏学浅,如有纰漏,欢迎指正。如果本文对您有所帮助,欢迎点赞,并期待您的反馈交流,共同成长。

原文地址: https://www.emanjusaka.top/archives/9

微信公众号:emanjusaka的编程栈

与浅析斐波那契数列在代码中的应用相似的内容:

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

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

浅析Vite本地构建原理

前言 随着Vue3的逐渐普及以及Vite的逐渐成熟,我们有必要来了解一下关于vite的本地构建原理。 对于webpack打包的核心流程是通过分析JS文件中引用关系,通过递归得到整个项目的依赖关系,并且对于非JS类型的资源,通过调用对应的loader将其打包编译生成JS 代码,最后再启动开发服务器。

浅析MySQL 8.0直方图原理

本文将对直方图概念进行介绍,借助举例描述直方图的使用方式,对创建/删除直方图的原理进行浅析,并通过例子说明其应用场景。

[转帖]浅析Nginx配置获取客户端真实IP的proxy_set_header、X-Real-IP、$remote_addr、X-Forwarded-For、$proxy_add_x_forwarded_for分别是什么意思

https://www.cnblogs.com/goloving/p/15588668.html 一、问题背景 在实际应用中,我们可能需要获取用户的ip地址,比如做异地登陆的判断,或者统计ip访问次数等,通常情况下我们使用 request.getRemoteAddr() 就可以获取到客户端ip,但是

[转帖]浅析IP地址及localhost、127.0.0.1和0.0.0.0的区别

https://www.cnblogs.com/goloving/p/7202151.html 127.0.0.1和0.0.0.0这两个IP地址再熟悉不过了,看起来好像就那么回事,但真正较起真来,这两个IP地址到底有什么作用以及到底有什么不同?貌似谁可以轻松回答,但张嘴却又不知从何说起(这要是面试,

[转帖]浅析nginx的server及server_name的意义详解

https://www.cnblogs.com/goloving/p/7010713.html 一、server_name 详解 当Nginx接到请求后,会匹配其配置中的server模块。匹配方法就是靠请求携带的host和port正好对应其配置中的server_name 和listen。如果做过ip

[转帖]浅析./configure、make、make install之间的关系

https://www.cnblogs.com/zcj-0928/articles/16261389.html 写在前面: 可能我们都知道linux中安装软件方式的一种是:将源码sourcecode.tar.gz进行解压,然后输入./configure,接着make,最后make install,一

【转帖】浅析经典JVM垃圾收集器-Serial/ParNew/Parallel Scavenge/Serial Old/Parallel Old/CMS/G1

https://zhuanlan.zhihu.com/p/481256418 在讲述垃圾收集器之前,我们得先知道JVM中常见的垃圾收集算法有什么,具体请参考我的这篇博文。如果说收集算法是内存回收的方法论, 那垃圾收集器就是内存回收的实践者。下面就来详细概述下Serial、ParNew、Paralle

[转帖]浅析TiDB二阶段提交

https://cloud.tencent.com/developer/article/1608073 关键内容说明: TiDB 对于每个事务,会涉及改动的所有key中,选择出一个作为当前事务的Primary Key,其他的则为Secondary keys。 当Primary Key提交成功,标识整

浅析 SplitChunksPlugin 及代码分割的意义

起因 有同事分享webpack的代码分割,其中提到了SplitChunksPlugin,对于文档上的描述大家有着不一样的理解,所以打算探究一下。 Q:什么是 SplitChunksPlugin?SplitChunksPlugin 是用来干嘛的? A: 最初,chunks(以及内部导入的模块)是通过内