用Java语言编写菲波那契数列程序

文章目录

• ​​一、了解菲波那契数列​​
• ​​二、递归算法​​
• ​​三、动态规划算法​​

一、了解菲波那契数列

• 斐波那契数列，又称黄金分割数列或兔子数列，该数列为0、1、1、2、3、5、8、13、21、34、…，可以看到它的性质是前两项之和等于后一项。
• 用数学公式表示，即：F(N) = F(N - 1) + F(N - 2), (其中 N > 1且F(0) = 0, F(1) = 1)。
• 菲波那契数列随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887……，黄金分割数又在自然界中无处不在，世界著名建筑如巴黎圣母院、埃菲尔铁塔、埃及金字塔等均能从它们身上找到0.618的影子。

二、递归算法

• 从顶至下进行递归运算，并通过记忆化搜索进行优化

/**
 * 递归法计算菲波那契数列
 */
public class Fibonacci {

    // 定义一个储存数值对应的HashMap: 比如HashMap<0,0>,HashMap<10,55>...
    static HashMap<Integer, Long> map = new HashMap<>();

    public static Long fib(int n) {

        if (n == 0 || n == 1) {
            return Integer.toUnsignedLong(n);
        }

        // 判断该数值是否已进行计算：未计算进行递归计算，已计算直接返回储存的值
        if (!map.containsKey(n)) {
            map.put(n, fib(n - 1) + fib(n - 2));
        }
        return map.get(n);
    }

    public static void main(String[] args) {
        for(int j=0;j<44;j++) {
            System.out.print(fib(j)+",");
        }
    }
}      

• 输出：

三、动态规划算法

• 动态规划能解决子问题重复的问题，该算法与递归算法的从顶至下正好相反，通过自底向上进行迭加运算

/**
 * 动态规划法计算菲波那契数
 */
public class Dymaic {

    public static Long fib(int n) {
        Long f0 = 0L, f1 = 1L;
        Long result = n == 0 ? f0 : f1;
        for (int i = 2; i <= n; i++) {
            // 从下向上依次叠加计算，每次由位于它之前的两个斐波那契数相加
            result = f0 + f1;
            f0 = f1;
            f1 = result;
        }
        return result;
    }

    public static void main(String[] args) {
        for (int j = 0; j < 44; j++) {
            System.out.print(fib(j) + ",");
        }

    }

}      

• 输出：