斐波那契数列

cultureSun

发布于 2023-09-02 18:45:00

1950

发布于 2023-09-02 18:45:00

文章被收录于专栏：cultureSun学安全cultureSun学安全

0x01

刷抖音突然刷到了斐波那契数列，突发奇想就用java写一个斐波那契数列。虽然很早之前学习算法，这应该是最基本的，但是对于一个干着普普通通工作的我已经是需要深思熟虑一番。

0x02

斐波那契数列是指从第3个数开始，每个数都是前两个数的和。数列的前几个数字如下所示：0、1、1、2、3、5、8、13、21、34、55、89……以此类推。斐波那契数列在数学和计算机领域具有广泛的应用。它们可以描述自然界中许多现象，如植物的分枝、螺旋线形状等。在编程中，斐波那契数列常用于解决一些递归问题，也被用于算法优化和动态规划等方面。

0x03

直接看代码，从第一个数为 1 开始。

public class Feibonaqi {
    public static void main(String[] args) {
        int n = 3; // 要计算的斐波那契数列长度
        System.out.println("斐波那契数列第 " + n + " 个数为：");

        System.out.print(fibonacci(n) + " ");
        System.out.print(fibonacci2(n, new int[3]) + " ");
        System.out.print(fibonacci3(n) + " ");

    }

    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            int[] fib = new int[n + 1];
            fib[0] = 0;
            fib[1] = 1;
            fib[2] = 1;
            for (int i = 3; i <= n; i++) {
                fib[i] = fib[i - 1] + fib[i - 2];
            }
            return fib[n];
        }
    }

    public static int fibonacci2(int n, int[] fib) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            if (fib[0] == n) {
                return fib[2];
            }
            if (fib[0] == 0) {
                fib[0] = 2;
                fib[1] = 1;
                fib[2] = 1;
            }
            fib[0]++;
            int temp = fib[2];
            fib[2] = fib[1] + fib[2];
            fib[1] = temp;
            return fibonacci2(n, fib);
        }
    }

    public static int fibonacci3(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

}

一共有三个方法。第一个方法是 gpt 写的，很简单，一个循环来计算第 n 个数的值。第二个方法是我写的，采用了递归的方式写的。何谓递归，往下读： 递归是一种在程序执行过程中调用自身的技术。在递归过程中，问题会被不断地分解成规模更小的子问题，并通过递归调用解决子问题，最终得到问题的解。递归通常有两个重要的部分：