技术标签: 算法 # 算法技能树 leetcode 数据结构 大数据 数据与未来 b树
斐波那契数列
(Fibonacci sequence
),又称“
黄金分割数列“
,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“
兔子数列”
,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
黄金分割
是指将整体一分为二,较大部分与整体部分的比值等于较小部分与较大部分的比值,其比值约为0.618。这个比例被公认为是最能引起美感的比例,因此被称为黄金分割。
把一条线段分割为两部分,使较大部分与全长的比值等于较小部分与较大的比值,则这个比值即为黄金分割。其比值是,近似值为0.618,通常用希腊字母Ф表示这个值。
附:黄金分割数前面的32位为:0.6180339887 4989484820 458683436564
设一条线段AB的长度为a,C点在靠近B点的黄金分割点上,且AC为b,则b与a的比叫作黄金比
有趣的是,这样一个完全是自然数的数列,通项公式却是用无理数来表达的。而且当趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割0.618(或者说后一项与前一项的比值小数部分越来越逼近 0.618)。
斐波那契数列又因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。
经典问题:
一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死:
我们不妨拿新出生的一对小兔子分析一下:
第一个月小兔子没有繁殖能力,所以还是一对
两个月后,生下一对小兔对数共有两对
三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对
------
依次类推可以列出下表:
幼仔对数=前月成兔对数
成兔对数=前月成兔对数+前月幼仔对数
总体对数=本月成兔对数+本月幼仔对数
可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前
面相邻两项之和,构成了后一项。
这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有
a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]n-[(1-√5)/2]n(n=1,2,3,…)
/**
* 兔子问题
* 斐波那契数列求值
* @author tonylp
*题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,
*小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?
*1.程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21....
*/
public class rabbit {
public static final int MONTH = 15;
public static void main(String[] args) {
long f1 = 1L, f2 = 1L;
long f;
for(int i=3;i<MONTH;i++){
f=f1+f2;
f1=f2;
f2=f;
System.out.println("第"+i+"个月的兔子对数:"+f2);
}
}
//递归方法实现
public static int fib(int month){
if(month == 1 || month == 2){
return 1;
}else{
return fib(month-1)+fib(month-2);
}
}
}
斐波那契数列算法的应用
相关数学题:排列组合、兔子繁殖问题、杨辉三角 …
/**
* 平推方法实现
*/
public static long fibLoop(int num){
if(num<1||num>92) return 0;
long a =1, b = 1, temp;
for(int i =2;i<num;i++){
temp =a;
a=b;
b+=temp;
}
return b;
}
/**
* 递归方法实现
* f(n) = f(n-1)+f(n-2)
* 最高支持 n=92 ,否则超出 Long.MAX_VALUE
*
*/
public static long fibRec(int num){
if(num<1) return 0;
if (num<3)return 1;
return fibRec(num-1)+ fibRec(num-2);
}
/**
* 带有缓存的方法, 比fibRec方法性能好很多
*/
static long[] l=new long[93];
static {
l[1]=1;}
public static long fibBuffec(int num){
if(num<1||num >92) return 0;
if (l[num]==0)
l[num]=fibBuffec(num-1)+fibBuffec(num-2);
return l[num];
}
/**
* 1,2,3,4,5,6,7,8
* 1,1,2,3,5,8,13,21
* 支持num 超过92的超大型数字,使用了ArrayList进行缓存以提高性能
*/
static List<BigDecimal> list =new ArrayList<>(93);
static {
list.add(BigDecimal.ZERO);
list.add(BigDecimal.ONE);
}
public static BigDecimal fibBig(int num){
if (num<0) return list.get(0);
if (list.size()<=num)
list.add(fibBig(num-1).add(fibBig(num-2)));
return list.get(num);
}
使用迭代算法和递归算法都可以实现斐波那契数列,输出数列中的第N项,但是由于递归算法在计算时存在着大量的重复计算,所以在N值很大时,可能会造成内存的溢出,以及计算时间较长的情况出现,在使用迭代算法的情况下同样可以实现计算斐波那契数列第N项的功能,
代码示例如下
迭代算法:
public static int FibonacciD(int num) {
if(num <= 0) {
return 0;
}
if(num == 1 || num == 2) {
return 1;
}
int first = 1,second =1,third = 0;
for(int i = 3; i<= num ;i++) {
third = first + second;
first = second;
second = third;
}
return third;
}
思路就是当 n <=0 时 return 0,当1 <= n <= 2时 return 1 ,当 n >= 3时,第n项 f(n) = f(n-2) + f(n-1),所以在计算数列中第n项的时候可用一个for循环,初始化前两项的值,计算完成第N项之后,然后交换(n-2)项 (n-1)项的值,循环完成之后计算出的Third值即为数列中第N项的值
递归算法:
public static int Fibonacci(int i) {
if(i <= 0) {
return 0;
}
if(i == 1 || i == 2) {
return 1;
}
return Fibonacci(i -2) + Fibonacci(i-1);
}
在N值比较小的时候两种方式计算耗时的差异不大,但是当N值比较大的时候两者之间计算时间的差异就比较大了,
当N = 10 ,运行时间差异不大,基本上一致
当N = 40 时,此时运行耗时差异已经比较大了
N = 45 时,耗时差异进一步加大
所以当N 值趋近于一个较大的值时,再使用递归计算第N项值,耗费的时间将是一个很恐怖的值,因此当N值较大时优先使用迭代算法
这里有一些相关的文章,可以参考一下
1、斐波那契数列的迭代算法和递归算法
2、埃氏筛法(埃氏算法)
3、BF算法(暴⼒算法)-- 模式匹配算法
4、数据结构:八大数据结构分类
5、JAVA中 常用七大排序算法
6、Linked 链表反转 - 迭代 与 递归
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象