[java练习]斐波那契数列的三种实现方式
【[java练习]斐波那契数列的三种实现方式】我以为我以前写过,想复习一下才发现我没写过。。。
直接把我代码贴出来了,注释都写的很清楚了
/***
* 说斐波那契数列三种实现
* 0,1,1,2,3,5,8,13
* 可以得出来结论
* F(0)=0
* F(1)=1
*
* F(2)=F(0)+F(1)=1
* F(3)=F(1)+F(2)=F(1)+( F(0)+F(1) ) = 2
* ......
* F(n)=F(n-2)+F(n-1)
* 这个如果细化分解的话,最终会回归到只有F(0)和F(1)的问题里面去,也就是等号右边全是F(0)和F(1)
*
*
*/
public class Fib {/**
* 递归实现
* @param n 第n项
* @return
*/
public static int fib1(int n){
if (n<0){
return -1;
}
if (n==0){
return 0;
}
if (n == 1) {
return 1;
}
return fib1(n-2) + fib1(n-1);
}/**
* 基于变量实现
* 卸磨杀驴型 = = 用完就给你覆盖上
* @param n
* @return
*/
public static int fib2(int n){
if (n<0){
return -1;
}
if (n==0){
return 0;
}
if (n == 1 || n==2) {
return 1;
}
int a = 1;
int b = 1;
int result = 0;
for (int i=3;
i<=n;
i++){
result = a+b;
a=b;
b=result;
}
return result;
}/**
* 基于数组实现
* 这个有个好处。
* 如果需要的话,可以直接把整条斐波那契数列全带出来。直接返回数组就可以了
* @param n
* @return
*/
public static int fib3(int n){
if (n<0){
return -1;
}
if (n==0){
return 0;
}
if (n == 1 || n==2) {
return 1;
}
int[] array = new int[n+1];
array[0]=0;
array[1]=1;
array[2]=1;
for (int i=3;
i<=n;
i++){
array[i]=array[i-2]+array[i-1];
}
return array[n];
}public static void main(String[] args) {
System.out.println(fib1(6));
System.out.println(fib2(6));
System.out.println(fib3(6));
}
}
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- Python基础|Python基础 - 练习1
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 呼吸练习心得
- Java|Java基础——数组