0%

斐波那契数列

发表于

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

对斐波那契数列，我们有

an=an−1+an−2a_n = a_{n-1} + a_{n-2}

考虑矩阵乘法，我们有

[ab00]×[1110]=[a+ba00]\begin{bmatrix} a & b \\ 0 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} a + b & a \\ 0 & 0 \\ \end{bmatrix}

故

[an+1an00]=[anan−100]×[1110]=[1110]n\begin{bmatrix} a_{n+1} & a_n \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} a_n & a_{n-1} \\ 0 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^n

最后引入快速幂，即

[an+1an00]=[1110]n=([1110]⌊n2⌋)2×[1110]n%2\begin{bmatrix} a_{n+1} & a_n \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^n = ( \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{\lfloor \frac{n}{2} \rfloor}) ^2 \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{n \% 2} 

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
class Solution {
public:
    void times(int a[4], int b[4])
    {
        int r[4] = {
            a[0] * b[0] + a[1] * b[2],
            a[0] * b[1] + a[1] * b[3],
            a[2] * b[0] + a[3] * b[2],
            a[2] * b[1] + a[3] * b[3]};
        a[0] = r[0];
        a[1] = r[1];
        a[2] = r[2];
        a[3] = r[3];
    }
    int Fibonacci(int n) {
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }
        else
        {
            int base[] = {1, 1, 1, 0}, r[4] = {1, 1, 1, 0};
            n -= 2;
            while (n)
            {
                if (n & 1)
                {
                    times(r, base);
                }
                times(base, base);
                n >>= 1;
            }
            return r[0];
        }
    }
};