Java 斐波那契数列 及 优化
2020-03-19 本文已影响0人
邮差在行动
import java.util.HashMap;
public class Recursion {
HashMap<Integer, Long> bucket = new HashMap<>();
/**
* 优化的方法
* @param n
* @return
*/
public long f(int n){
System.out.println("n="+n);
if(n <= 2){
return n;
}
if (!bucket.containsKey(n)) {
bucket.put(n, f(n-1) + f(n-2));
}
return bucket.get(n);
}
/**
* 原始的方法
* @param n
* @return
*/
public long flazy(int n) {
System.out.println("n="+n);
if (n <= 2) {
return n;
}
System.out.println("f("+(n-1)+")+f("+(n-2)+")");
return flazy(n-1) + flazy(n-2);
}
public static void main(String[] args) {
Recursion r = new Recursion();
long f = r.flazy(5);
System.out.println(f);
}
}
斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(*n ≥ 3,n ∈ N)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志,用于专门刊载这方面的研究成果。
如果只是按上面的定义,我们就能写出代码。
可是我们还需要再思考一下代码的效率,有些值是重复计算过的,所以又出了优化的方法。
当然,我开始没有想到,是什么样的人想到的呢?真棒!