java斐波拉契数列算法_Java与算法之(3) - 斐波那契数列_weixin_42128015的博客-程序员秘密

技术标签: java斐波拉契数列算法  

斐波那契数列问题:如果一对兔子每月能生1对小兔子,而每对小兔在它出生后的第三个月里,又能开始生1对小兔子,假定在不发生死亡的情况下,由一对初生的兔子开始,1年后能繁殖出多少对兔子?

首先手工计算来总结规律,如下表

c3db5afdfbb247713cef3ec1b10d0906.png

注意总数这一列

1+1=2

1+2=3

2+3=5

3+5=8

5+8=13

可以得出规律,第n个斐波那契数=第n-1个斐波那契数+第n-2个斐波那契数

为了计算n,必须计算n-1和n-2;为了计算n-1,必须计算n-2和n-3;直到n-x的值为1为止,这显示是递归大显身手的地方。来看代码

public class Fibonacci {

public static long calc(long n) {

if(n 

return 0;

}

if(n == 0 || n == 1) {

return n;

} else {

return calc(n - 1) + calc(n - 2);

}

}

}

这真是极短的,测试代码

public static void main(String[] args) {

long n = 50;

long begin = System.nanoTime();

long f = Fibonacci.calc(n);

long end = System.nanoTime();

System.out.println("第" + n + "个斐波那契数是" + f + ", 耗时" + TimeUnit.NANOSECONDS.toMillis(end - begin) + "毫秒");

}

运行输出

第50个斐波那契数是12586269025, 耗时66024毫秒

注意看消耗的时间,在我的电脑上耗时66秒,真是个相当耗时的操作。既然整个过程都是在不断重复相同的计算规则,那我们可以采用分而治之的思想来优化代码。

import java.util.concurrent.ForkJoinPool;

import java.util.concurrent.RecursiveTask;

import java.util.concurrent.TimeUnit;

public class Fibonacci extends RecursiveTask {

long n;

public Fibonacci(long n) {

this.n = n;

}

public Long compute() {

if(n <= 10) {  //小于10不再分解

return Fibonacci.calc(n);

}

Fibonacci f1 = new Fibonacci(n - 1);  //分解出计算n-1斐波那契数的子任务

f1.fork();  //由ForkJoinPool分配线程执行子任务

Fibonacci f2 = new Fibonacci(n - 2);  //分解出计算n-2斐波那契数的子任务

return f2.compute() + f1.join();

}

public static long calc(long n) {

if(n 

return 0;

}

if(n == 0 || n == 1) {

return n;

} else {

return calc(n - 1) + calc(n - 2);

}

}

public static void main(String[] args) {

long n = 50;

long begin = System.nanoTime();

Fibonacci fibonacci = new Fibonacci(n);

ForkJoinPool pool = new ForkJoinPool();

long f = pool.invoke(fibonacci);

long end = System.nanoTime();

System.out.println("第" + n + "个斐波那契数是" + f + ", 耗时" + TimeUnit.NANOSECONDS.toMillis(end - begin) + "毫秒");

}

}

运行输出

第50个斐波那契数是12586269025, 耗时20461毫秒

虽然时间缩短了2/3,但是仍然不理想。回头重新看计算方法,用递归方式虽然代码简短,但是存在很严重的重复计算,下面用非递归的方式改写,过程中每个数只计算一次。

public static long calcWithoutRecursion(long n) {

if(n 

return 0;

if(n == 0 || n == 1) {

return n;

}

long fib = 0;

long fibOne = 1;

long fibTwo = 1;

for(long i = 2; i 

fib = fibOne + fibTwo;

fibTwo = fibOne;

fibOne = fib;

}

return fib;

}

测试

第50个斐波那契数是12586269025, 耗时0毫秒

斐波那契数的另一个经典题目是青蛙跳台阶问题:

一只青蛙一次可以条一级或两级台阶,求该青蛙跳上n级的台阶共有多少种跳法。

假设计算第n级台阶跳法的函数是f(n),当n>2时,第一步选择跳一级有X种跳法,第一步选择跳两级有Y种跳法,f(n)=X+Y。如何计算X呢,站在青蛙的位置考虑,面对的是一个全新的n-1级台阶,有f(n-1)种跳法,那么Y就是n-2级台阶的跳法,那么f(n)=f(n-1)+f(n-2),即斐波那契数列公式。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_42128015/article/details/114543550

智能推荐

docker安装gitlab、迁移和升级_docker gitlab升级_风唤雀翎的博客-程序员秘密

公司之前gitlab长时间之后经常宕机假死,版本较旧,决定迁移并升级到新版本。新版本为gitlab-ee:13.1.0-ee.0,采用docker安装,之前版本为10.1.01. gitlab数据备份gitlab-rake gitlab:backup:create使用以上命令会自动备份到 /var/opt/gitlab/backups目录下面,然后拷贝到新的gitlab服务器上,这里因为备份文件比较大,将新的server上面的/data目录通过nfs挂载到旧的/var/opt/gitlab/backu

华为HCIP-Datacom821(441-470)_打螺丝不眨眼的网工的博客-程序员秘密

441.执行()saved-configuration命令,清空设备下次启动使用的配置文件的内容,并取消指定系统下次启动时使用的配置文件,从而使设备配置恢复到缺省值。(请填写完整命令,不能缩写且全部使用英文字母小写)答案:reset442.华为防火墙默认创建的安全区域为untrust、dmz、local和()。(全小写)答案:trust443.如图所示R1与R2组成一个VRRP备份组1,通过在R1执行vrrp vrid 1 virtual-ip()命令,可以使其成为IP地址拥有者,让R1为Master,R

hcip-datacom-core-00-认识网络设备_浅寂的博客-程序员秘密

框式设备以S12700E-8为例:主控板(MPU,Main Processing Unit):负责整个系统的控制平面和管理平面交换网板(SFU,Switch Fabric Unit):负责整个系统的数据平面。数据平面提供高速无阻塞数据通道,实现各个业务模块之间的业务交换功能接口板(LPU,Line Processing Unit):线路处理单元是物理设备上用于提供数据转发功能的模块,提供不同速率的光口、电口交换网板、接口板上都有自己的管理芯片,与主控板共同组成整个设备的控制管理平面盒式设备

华为HCIP-DATACOM391-420(821)_as-external-lsa不属于任何区域_打螺丝不眨眼的网工的博客-程序员秘密

在配置组播路由协议是,首先需要执行()routing-enable命令,然后在进行PIM协议的相关配置。 使用堆叠、集群技术构建园区网的优势包括以下哪些?关于Route policy描述正确的是 下面关于OSPF协议,哪些描述是正确的?A:第二类外部路由的开销值只是AS外部开销值,忽略AS内部开销值B:AS-External-LSA不属于任何区域C:AS-External-LSA描述到AS外部路由的路径,泛洪的范围是AS外部D:AS-External-LSA描述的是路由器到ASBR的路径

tushare获取中机2014 到2018年末五复权收盘数据_lambda x:x.find('12',4,6)>=0_山坡羊某某浩的博客-程序员秘密

import tushare as tspro = ts.pro_api('token')ds = pro.monthly(ts_code='603988.SH', start_date='20140101', end_date='20181231', fields='trade_date,close')ds = ds[ds.trade_date.map(lambda x:x.find('12',4,6)&gt;=0)]print(ds)

在ROS中传递图像消息(一)_ros no image_退休码农飞伯德的博客-程序员秘密

最近在学习如何在ROS中传递图像,在这里将自己的拙见与大家分享,希望大家多多指教。如果有错误的地方,希望各位大神不吝赐教。

随便推点

【PyG】pytorch和torch_geometric离线安装教程-程序员秘密

1、首先要安装pytorch,有两类cpu版本和cuda版本,我通过pip下载的是cpu版本。进入python交互环境,通过以下代码获得torch版本import torchprint(torch.__version__) #注意是双下划线比如我的就是1.8.1+cpu2、下载四个轮子https://pytorch-geometric.com/whl/进入该网址,根据torch版本和python版本和windows等版本下载对应的四个轮子torch_clustertorch

Javascript DOM变成艺术学习笔记_石山下的博客-程序员秘密

1.对象对象是自包含的是对象集合,包含在对象里的数据可以通过两种形式进行访问----属性(property)和方法(method)。属性:隶属于某个特定对象的变量–object.property方法:只有某个特定对象才能调用的方法–object.method()...

Hibernate实现分页 笔记_小白白友的博客-程序员秘密

最近在学习SSH编程,整理了一个Hibernate Query分页的笔记。因为在做一个邮箱项目,所以就用一个Mail表来作为例子了自己菜鸟程序员一只,方便自己查阅的同时方便大家参考

矩阵乘法基本概念及模板题目_矩阵乘法模板_北岭山脚鼠鼠的博客-程序员秘密

由上式可以逐渐推出F[n]的表达式,F[n]=F[1]*A^(n-1),其中F[1,1]=[1,1],后半部分的A就是上图中的01行列式,快用快速幂求它的次方。矩阵乘法具有结合律如A*B*C==A*(B*C),当遇到A*(X*X*X*...*X)时就可以算法后面的X^n用快速幂来解决先。对于题目中的S[n],可以将F[n]变成一个带有S[n]的向量,F[n]= [ f[n] , f[n+1],S[n] ]思路:回顾斐波那契数列可以知道f[n]=f[n-1]+f[n-2]常用场景:矩阵快速幂。

用命令提示符创建图书管理系统表(Mysql)_mysql建立图书表_Pan_Yuan123的博客-程序员秘密

建立图书类别表依次输入create table bookcategory(category_id int primary key, (主键约束)category varchar(20) nut null unique, ...

Java基础-IO流对象之File类_weixin_33858249的博客-程序员秘密

                  Java基础-IO流对象之File类                                      作者:尹正杰版权声明:原创作品,谢绝转载!否则将追究法律责任。   一.IO技术概述  回想之前写过的程序,数据都是在内存中,一旦程序运行结束,这些数据都没有了,等下次再想使用这些数据,可是已经没有了。那怎么办呢?能不能把运算完的数据都保...

推荐文章

热门文章

相关标签