- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
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 |
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;
}
public int fibonacciRecursion(int n) {
if (n < 2){
return n;
} else {
return (fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2));
}
}
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);
}
在用来设计散列函数的除法散列法中,通过取 K 除以 M 的余数,将关键字 K 映射到 M 个槽中的某一个位置上,即散列函数为:h(K) = K mod M 表格大小通常是 2 的幂.
另外除法散列的一个显着缺点是除法在大多数现代架构(包括 x86)上都是微编程的,并且可能比乘法慢 10 倍.
乘法散列法整体包含两步:
A(0<A<1)
,并去除kA的小数部分 floor
公式: h(K)=Math.floor[m(aK mod 1)]
步骤 :
(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即为小数部分 h(k)h(k)
为 R0R0 的前 m 位。 乘法散列只需要单个整数乘法和右移,使其成为计算速度最快的哈希函数之一。但乘法散列可能会在变更计算因子后,较高值的输入位不会影响较低值的输出位,问题体现在元素分散不均,不满足严格的雪崩标准。所以通常在会进行异或操作 。
乘法散列容易受到导致扩散不良的“常见错误”的影响——较高值的输入位不会影响较低值的输出位。在乘法步骤对此进行校正之前,输入上的变换将保留的最高位的跨度向下移动,并将它们异或或加到键上。所以在输入上的变换将保留的最高位的跨度向下移动,并将它们异或操作或者加到键上。例如 HashMap 的扰动函数.
其实斐波那契散列是一种特殊形式的乘法散列,只不过它的乘法因子选择的是一个黄金分割比例值,所以叫做斐波那契散列.
斐波那契散列的特性在于将“大数映射到小数”的计算结果在表空间上是均匀分布的,且计算满足乘法散列效率高.
斐波那契数列可以用于生成伪随机数序列。虽然斐波那契数列本身不是真正的随机数序列,但通过适当的变换和截取,可以得到具有一定随机性的序列.
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;
}
}
在AVL树中,斐波那契数列可以用于平衡因子的调整和旋转操作.
AVL树是一种自平衡二叉搜索树,它要求左右子树的高度差不超过1,以保持树的平衡性。当对AVL树进行插入或删除操作时,可能会破坏树的平衡,这时需要对树进行旋转操作来恢复平衡.
在AVL树的旋转操作中,涉及到更新节点的高度信息。通常,节点的高度可以通过其子节点的高度来计算。而斐波那契数列正好提供了方便的计算方式.
具体应用如下:
斐波那契数列在最大公约数计算中有一个有趣的应用,称为"连续整除性质".
假设我们有两个正整数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的大小顺序.
在合并排序算法中,斐波那契数列可以用于确定合并的子数组大小.
合并排序是一种基于分治思想的排序算法,它将待排序的数组不断地拆分为较小的子数组,并对这些子数组进行排序,然后再将排好序的子数组合并为一个有序数组。斐波那契数列在确定子数组大小时可以发挥作用.
具体应用如下:
斐波那契数列在合并排序算法中的应用,主要是为了确定子数组的大小,以实现更灵活和高效的排序过程。利用斐波那契数列的特性,可以使合并排序算法更加平衡、快速和优化.
本文原创,才疏学浅,如有纰漏,欢迎指正。如果本文对您有所帮助,欢迎点赞,并期待您的反馈交流,共同成长.
原文地址: https://www.emanjusaka.top/archives/9 。
微信公众号:emanjusaka的编程栈 。
最后此篇关于浅析斐波那契数列在代码中的应用的文章就讲到这里了,如果你想了解更多关于浅析斐波那契数列在代码中的应用的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
很多朋友或许都有这个疑问,一个网站域名和网站的排名有关系吗?今天本文就从三个方面分析网站的域名与网站的排名有没有关系,希望对大家有一定的帮助。 1、全拼双拼域名 首先,我们要知道在这一点百
什么是进程 当一个程序进入内存中运行起来它就变为一个进程。因此,进程就是一个处于运行状态的程序。同时进程具有独立功能,进程是操作系统进行资源分配和调度的独立单位。 什么是线程 线程是进
最近几年,互联网络竞争异常激烈,各个企业为了增加业绩,都在网络销售中下足了功夫。要确定网站发展的方向,必须给自己的网站制定好一个发展目标,有了目标才能更好的发展。不管
一.基础知识准备: 1.层的原则: (1)每一层以接口方式供上层调用。 (2)上层只能调用下层。 (3)依赖分为松散交互和严格交互两种。 2.业务逻辑分类: (1)应
编程时一门技术,更是一门艺术 简单工厂模式利用面向对象方式通过继承、封装、多态把程序的耦合度降低,设计模式使得程序更加灵活,容易修改,易于复用。 下面是服务器计算器代码:
对于策略模式的理解:当一个业务有多种需求时候,在某个时候需要使用不同的方式来计算结果。这时候不同的方式可以理解为不同的策略来解决同样的问题。 例如:商场收银系统计算价格,1:正常计算 2:商品打折计
随着 Kubernetes 在企业中应用的越来越广泛和普及,越来越多的公司在生产环境中运维多个集群。本文主要讲述一些关于多集群 Kubernetes 的思考,包括为什么选择多集群,多集群的好处以
Kubelet 出于对节点的保护,允许在节点资源不足的情况下,开启对节点上 Pod 进行驱逐的功能。最近对 Kubelet 的驱逐机制有所研究,发现其中有很多值得学习的地方,总结下来
以下分析不针对任何快递公司,纯属实说。 申通快递在快递行业中速度与费用都属于中等的水平,在国内也分布有很多投递点,一般地区都可以投递到;顺丰在国内是速度最快的快递公司之一,一般来说隔天就能够到,其
概述 流(streams)是PHP4.3版本引入的一个特性,主要是为了统一文件、sockets以及其他类似资源的工作方法。PHP4.3距今已经有很长时间了,但是很多程序员似乎都不能正确使用PHP中
Pre 很早在看 Jesse 的 Asp.net Core快速入门 的课程的时候就了解到了在Asp .net core中,如果添加的Json配置被更改了,是支持自动重载配置的,作为一名有着严重&q
之前对closure一知半解,在网上也找不到一篇文章能把它说清楚,今天好像第一次对它有点清晰的了解 了,写个BLOG记念一下 lua的函数是一种 First-Class Value 的东西, 到底
1、什么是默认方法,为什么要有默认方法 简单说,就是接口可以有实现方法,而且不需要实现类去实现其方法。只需在方法名前面加个default关键字即可。 为什么要有这个特性?首先,之前的接口是个双
信息数据传输的安全一直都是个很重要的话题,从刚开始当程序员时错以为MD5、SHA1这些哈希算法就是加密算法,到后来慢慢接触对称加密、非对称加密这些概念,再到对接各种大开发平台接口的时候看到他们通
前言 2021年,vanilla-extract 作为黑马登顶了 css-in-js 满意度榜首(虽然使用率仅为1%),号称是一个类型安全、高度兼容 TS 场景的库,国内相关讨论还很少,稍微看
(一)响应式数据 1. 简单例子 从最简单的数据绑定开始,在 Vue 2.0 中,我们这样将一个数据绑定到模板的指定位置: 在组件创建参数的 data 构造函数中返回一个用来绑定的数据对象,其
我是一名优秀的程序员,十分优秀!