Java使用三种方式实现斐波那契数列求解

1.斐波那契数列的介绍

• 斐波那契数列（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 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果
• 斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89…
• 这个数列从第3项开始，每一项都等于前两项之和。

2.Java使用三种方式实现斐波那契数列求解

2.1 普通方法实现（递归）

package com.lagou.fibonacciMethod;/*** @author 云梦归遥* @date 2022/5/22 20:47* @description 斐波那契 - 普通方法实现（递归）*/
public class FibonacciMethod1 {public int fibonacci(int num){if (num <= 1) return num;// 大于 1 的情况return fibonacci(num - 1) + fibonacci(num - 2);}
}

2.2 动态规划实现

package com.lagou.fibonacciMethod;/*** @author 云梦归遥* @date 2022/5/22 20:52* @description 斐波那契 - 递归分治 + 备忘录*/
public class FibonacciMethod2 {private int[] array = null;public FibonacciMethod2(int num){this.array = new int[num + 1];}public int fibonacci(int num){if (num <= 1) return num;if (array[num] == 0){array[num] = fibonacci(num - 1) + fibonacci(num - 2);}return array[num];}
}

2.3 纯数组实现

package com.lagou.fibonacciMethod;/*** @author 云梦归遥* @date 2022/5/22 21:19* @description 斐波那契 - 数组实现*/
public class FibonacciMethod3 {public int fibonacci(int num){int[] array = new int[num + 1];if (num <= 1) return num;array[0] = 0; array[1] = 1;for (int i = 2; i <= num; i++){array[i] = array[i - 1] + array[i - 2];}return array[num];}
}

2.4 进行测试

package com.lagou.fibonacciMethod.test;import com.lagou.fibonacciMethod.FibonacciMethod1;
import com.lagou.fibonacciMethod.FibonacciMethod2;
import com.lagou.fibonacciMethod.FibonacciMethod3;/*** @author 云梦归遥* @date 2022/5/22 20:49* @description*/
public class FibonacciMethod1Test {public static void main(String[] args) {long l = System.currentTimeMillis();FibonacciMethod1 fibonacciMethod1 = new FibonacciMethod1();int fibonacci = fibonacciMethod1.fibonacci(10);Long l1 = System.currentTimeMillis();System.out.println("普通方法实现斐波那契（10）：" + fibonacci + ", 花费时间：" + (l1 - l));FibonacciMethod2 fibonacciMethod2 = new FibonacciMethod2(10);int fibonacci1 = fibonacciMethod2.fibonacci(10);Long l2 = System.currentTimeMillis();System.out.println("递归分治 + 备忘录 实现斐波那契（10）：" + fibonacci1 + ", 花费时间：" + (l2 - l1));FibonacciMethod3 fibonacciMethod3 = new FibonacciMethod3();int fibonacci2 = fibonacciMethod3.fibonacci(10);Long l3 = System.currentTimeMillis();System.out.println("数组 实现斐波那契（10）：" + fibonacci2 + ", 花费时间：" + (l3 - l2));}
}

package com.lagou.fibonacciMethod.test;import com.lagou.fibonacciMethod.FibonacciMethod1;
import com.lagou.fibonacciMethod.FibonacciMethod2;
import com.lagou.fibonacciMethod.FibonacciMethod3;/*** @author 云梦归遥* @date 2022/5/22 20:49* @description*/
public class FibonacciMethod1Test {public static void main(String[] args) {long l = System.currentTimeMillis();FibonacciMethod1 fibonacciMethod1 = new FibonacciMethod1();int fibonacci = fibonacciMethod1.fibonacci(40);Long l1 = System.currentTimeMillis();System.out.println("普通方法实现斐波那契（40）：" + fibonacci + ", 花费时间：" + (l1 - l));FibonacciMethod2 fibonacciMethod2 = new FibonacciMethod2(40);int fibonacci1 = fibonacciMethod2.fibonacci(40);Long l2 = System.currentTimeMillis();System.out.println("递归分治 + 备忘录 实现斐波那契（40）：" + fibonacci1 + ", 花费时间：" + (l2 - l1));FibonacciMethod3 fibonacciMethod3 = new FibonacciMethod3();int fibonacci2 = fibonacciMethod3.fibonacci(40);Long l3 = System.currentTimeMillis();System.out.println("数组 实现斐波那契（40）：" + fibonacci2 + ", 花费时间：" + (l3 - l2));}
}

3.总结

• 进行测试时发现，当所求得数比较小的时候，普通方式是最快的，因为没有数组和对象的创建；
• 当所求的数比较大时，后两种会非常快，因为递归的深度太深，有太多重复计算，如果用数组保存计算结果，将会远远比计算更快

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！