测试

2022-11-11 约 904 字预计阅读 2 分钟

有一种兔子,出生后一个月就可以长大,然后再过一个月一对长大的兔子就可以生育一对小兔子且以后每个月都能生育一对.现在,我们有一对刚出生的这种兔子,那么,n 个月过后,我们会有多少对兔子呢？假设所有的兔子都不会死亡.

这是一个经典的兔子问题,其实也就是斐波那契数列,转换为数学公式就是:

$$ F_n = \begin{cases} 0,&n=0\ 1,&n=1\ F_{n-1}+F_{n-2},&n \geq 2 \end{cases} $$

后续的解法都采用 Java 语言.

普通解法

按照公式,采用从后往前递归的方法很容易写出一个解法.

1
2
3
4
5
6
7
8
9


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

代码比较简介,但是会有大量重复的计算,时间复杂度应该是 O(2^n).

迭代解法

为了避免大量重复计算,可以从前往后计算,并且每次保留前两个结果,效率更高.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


    public static int fibonacciIter(int n) {
        int a = 0, b = 1;
        if (n <= 0) return a;
        for (int i = 0; i < n - 1; i++) {
            int tmp = b;
            b = a + tmp;
            a = tmp;
        }
        return b;
    }

时间复杂度是 O(1).

公式解法

斐波那契数列实际是有通项公式的:

$$ F_n=\frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] $$

所以可以代码实现:

1
2
3
4
5


    public static int fibonacciFormula(int n) {
        double fiveSqrt = Math.sqrt(5d);
        double result = (Math.pow((1 + fiveSqrt) / 2, n) - Math.pow((1 - fiveSqrt) / 2, n)) / fiveSqrt;
        return (int) result;
    }

因为有大量的浮点数计算,而且精度有限,所以结果可能不正确而且速度也快.

矩阵解法

首先根据公式有:

$$ \left[\begin{matrix} F_{n} \ F_{n-1} \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \ 1 & 0 \end{matrix}\right] \left[\begin{matrix} F_{n-1} \ F_{n-2} \end{matrix}\right] $$

所以有:

$$ \left[\begin{matrix} F_{n} \ F_{n-1} \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \ 1 & 0 \end{matrix}\right] ^ {n-1} \left[\begin{matrix} F_1 \ F_0 \end{matrix}\right] $$

同理可得:

$$ \left[\begin{matrix} F_{n-1} \ F_{n-2} \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \ 1 & 0 \end{matrix}\right] ^ {n-1} \left[\begin{matrix} F_0 \ F_{-1} \end{matrix}\right] $$

所以:

$$ \left[\begin{matrix} F_{n} & F_{n-1} \ F_{n-1} & F_{n-2} \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \ 1 & 0 \end{matrix}\right] ^ {n-1} \left[\begin{matrix} F_1 & F_0 \ F_0 & F_{-1} \end{matrix}\right] $$

同时有:

$$ \left[\begin{matrix} F_1 & F_0 \ F_0 & F_{-1} \end{matrix}\right] = \left[\begin{matrix} 1 & 0 \ 0 & 1 \end{matrix}\right] $$

所以可以得到:

$$ \left[\begin{matrix} F_n & F_{n-1} \ F_{n-1} & F_{n-2} \end{matrix}\right] = \left[\begin{matrix} 1 & 1 \ 1 & 0 \end{matrix}\right] ^{n-1} $$

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


/**
* 2 * 2 矩阵乘法
* <p>
* a[0][0]  a[0][1]
* a[1][0]  a[1][1]
*/
    public static long[][] matrixMultiply(long[][] a, long[][] b) {
        long[][] result = new long[2][2];
        result[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        result[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        result[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        result[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
        return result;
    }

/**
* 2 * 2 矩阵 N 次幂
*/
    public static long[][] matrixPower(long[][] x, int n) {
        if (n < 0) throw new IllegalArgumentException();
        long[][] result = new long[2][2];
        result[0] = new long[]{1, 0};
        result[1] = new long[]{0, 1};

        long[][] v = x;

        while (n != 0) {
            if (n % 2 == 1) {
                result = matrixMultiply(result, v);
                n -= 1;
            }
            v = matrixMultiply(v, v);
            n /= 2;
        }

        return result;
    }

    public static long fibonacciMatrix(int n) {
        if (n <= 0) {
            return 0;
        } else {
            long[][] y = new long[2][2];
            y[0] = new long[]{1, 1};
            y[1] = new long[]{1, 0};
            long[][] r = matrixPower(y, n - 1);
            return r[0][0];
        }
    }

时间复杂度是 $O(log(n))$

目录

测试

普通解法

迭代解法

公式解法

矩阵解法