很简单的一道题，可以参考 wise 的笔记，三种方法，递归、迭代、矩阵快速幂，下面直接上C++代码。

// 递归
    int fib(int N) {
        if(N == 0)
            return 0;
        else if(N == 1)
            return 1;
        else{
            int result = 0;
            result = fib(N - 1) + fib(N - 2);
            return result;
        }
    }

image.png

然后是迭代，wise 说是简单的动规

// 迭代
    int fib(int N) {
        int a = 0;
        int b = 1;
        int c = 1;
        int temp = 0;
        for(int i = N; i > 0; i--){
            temp = b + c;
            a = b;
            b = c;
            c = temp;
        }
        return a;
    }

image.png

可以说非常牛逼了

最后是复杂度 logn 的矩阵快速幂

// 矩阵
    int fib(int N) {
        int pow = N;
        int base[2][2] = {{1,1},{1,0}};
        int mulbase[2][2] = {{1,1},{1,0}};
        int temp[2][2] = {{1,0},{0,1}};
        int result[2][2] = {{1,0},{0,1}};
        for(pow = N; pow != 0; pow >>= 1){
            if(pow & 1){
                result[0][0] = temp[0][0] * base[0][0] + temp[0][1] * base[1][0];
                result[0][1] = temp[0][0] * base[0][1] + temp[0][1] * base[1][1];
                result[1][0] = temp[1][0] * base[0][0] + temp[1][1] * base[1][0];
                result[1][1] = temp[1][0] * base[0][1] + temp[1][1] * base[1][1];
            }
            mulbase[0][0] = base[0][0] * base[0][0] + base[0][1] * base[1][0];
            mulbase[0][1] = base[0][0] * base[0][1] + base[0][1] * base[1][1];
            mulbase[1][0] = base[1][0] * base[0][0] + base[1][1] * base[1][0];
            mulbase[1][1] = base[1][0] * base[0][1] + base[1][1] * base[1][1];
            for(int i = 0; i < 2; i++){
                for(int j = 0; j < 2; j++){
                    temp[i][j] = result[i][j];
                    base[i][j] = mulbase[i][j];
                }
            }
        }
        return result[1][0];
    }

代码比较多，但是复杂度低了，在运算比较大的数据时候有优势。

image.png