首页 > 试题广场 >

斐波那契数列问题的递归和动态规划

[编程题]斐波那契数列问题的递归和动态规划
  • 热度指数：6576 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出一个整数 n，请输出斐波那契数列的第 n 项对 1e9 + 7 取模的值。

输入描述:
第一行一个整数 n。


输出描述:
输出第 n 项对于 1e9 + 7 取模的值。
示例1

输入

1

输出

1

备注:
算法知识视频讲解
添加回答
ZONE画派201805111104727头像 ZONE画派201805111104727
fn =  
f(n)   = f(n-1) + f(n-2)
f(n-1) = f(n-1)
    
矩阵：

[ f(n)   ] = [ 1*f(n-1) + 1*f(n-2) ] = [ 1 1 ] * [ f(n-1) ]
[ f(n-1) ]   [ 1*f(n-1) + 0*f(n-2) ]   [ 1 0 ]   [ f(n-2) ]

显然：
    [ f(2) ] = [ 1 ]
    [ f(1) ]   [ 1 ]
    
假设：
    mul = [ 1 1 ]
          [ 1 0 ]
    
那么：
    [ f(n)   ] = mul * [ f(n-1) ] = mul * mul * [ f(n-2) ] = ... = mul^(n-2) * [ f(2) ]
    [ f(n-1) ]         [ f(n-2) ]               [ f(n-3) ]                     [ f(1) ]
    
转变为快速幂问题：
    快速求 mul^(n-2) 的值即可

发表于 2019-08-14 19:19:50 回复(5)
天命剑主头像 天命剑主 
#include <cstring>

using std::memcpy;
using std::memset;

#include <iostream>

using std::ostream;
using std::endl;

template<typename T>
/**
 * 矩阵类
 * @tparam T 类型参数
 */
class matrix {
public:
    int row;//行
    int column;//列
    T **data;//数据

public:
    matrix(int r, int c) : row(r), column(c) {
        data = new T *[r];
        for (int i = 0; i < r; ++i) {
            data[i] = new T[c];
            memset(data[i], 0, column * sizeof(*data[i]));
        }
    }

    matrix(const matrix &m) : row(m.row), column(m.column) {
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m.data[i], column * sizeof(*data[i]));
        }
    }

    matrix(int r, int c, T **m) : row(r), column(c) {
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m[i], column * sizeof(*data[i]));
        }
    }

    matrix &operator=(const matrix &m) {
        if (&m == this) {
            return *this;
        }
        for (int i = 0; i < row; ++i) {
            delete[] data[i];
        }
        delete[] data;
        row = m.row;
        column = m.column;
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m.data[i], column * sizeof(*data[i]));
        }
        return *this;
    }

    bool operator==(const matrix &m) const {
        if (row != m.row || column != m.column) {
            return false;
        }
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < column; ++c) {
                if (m[r][c] != data[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }

    inline bool operator!=(const matrix &m) const {
        return !operator==(m);
    }

    inline matrix operator*(const matrix &m) {
        return multiply(m);
    }

    inline matrix &operator*=(const matrix &m) {
        *this = multiply(m);
        return *this;
    }

    /**
     * 矩阵乘法
     * @param m 被乘数
     * @return 结果
     */
    matrix multiply(const matrix &m) {
        matrix<T> c(row, m.column);
        for (int i = 0; i < row; ++i) {
            for (int k = 0; k < m.row; ++k) {
                for (int j = 0; j < m.column; ++j) {
                    c[i][j] = (c[i][j] + data[i][k] * m[k][j]);
                }
            }
        }
        return c;
    }

    /**
     * 矩阵乘法
     * @param m 被乘数
     * @param mod 结果太大的时候求mod
     * @return 结果
     */
    matrix multiply(const matrix &m, T mod) {
        matrix<T> c(row, m.column);
        for (int i = 0; i < row; ++i) {
            for (int k = 0; k < m.row; ++k) {
                for (int j = 0; j < m.column; ++j) {
                    c[i][j] = (c[i][j] + data[i][k] * m[k][j]) % mod;
                }
            }
        }
        return c;
    }

    /**
     * 求矩阵m的n次幂
     * 注意m.row == m.column
     * @param n n次幂
     * @return 结果
     */
    matrix pow(unsigned long long n) {
        matrix<T> m = *this;
        matrix<T> res(m.row, m.row);
        for (int i = 0; i < m.row; ++i) {
            res[i][i] = 1;
        }
        while (n > 0) {
            if (n & (unsigned)1) {
                res = res.multiply(m);
            }
            m = m.multiply(m);
            n >>= 1;
        }
        return res;
    }

    /**
     * 求矩阵m的n次幂
     * 注意m.row == m.column
     * @param n n次幂
     * @param mod 结果太大的时候求mod
     * @return 结果
     */
    matrix pow(unsigned long long n, T mod) {
        matrix<T> m = *this;
        matrix<T> res(m.row, m.row);
        for (int i = 0; i < m.row; ++i) {
            res[i][i] = 1;
        }
        while (n > 0) {
            if (n & (unsigned)1) {
                res = res.multiply(m, mod);
            }
            m = m.multiply(m, mod);
            n >>= 1;
        }
        return res;
    }

    ~matrix() {
        for (int i = 0; i < row; ++i) {
            delete[] data[i];
        }
        delete[] data;
    }

    T *&operator[](int r) const {
        return data[r];
    }

    friend ostream &operator<<(ostream &os, const matrix &m) {
        os << "matrix : ";
        for (int i = 0; i < m.row; ++i) {
            if (i != 0) {
                os << "         ";
            }
            for (int j = 0; j < m.column; ++j) {
                os << m[i][j] << " ";
            }
            os << endl;
        }
        return os;
    }
};

template<typename T>
T fast_fibonacci(unsigned long long n, T mod) {
    matrix<T> m(2, 2);
    m[0][0] = 1;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 0;
    m = m.pow(n, mod);
    return m[1][0];
}

#include <iostream>
using std::cout;
using std::cin;

unsigned long long m = 1e9 + 7;

int main(){
    unsigned long long n = 0;
    cin >> n;
    cout << fast_fibonacci(n,m) << endl;
}

发表于 2019-08-29 10:00:12 回复(2)
Java
pein531头像 pein531
矩阵的快速幂求解，让直接线性动态规划的O(N)时间复杂度降低为O(logN)。能这么做的条件是：除了初始的几项，dp序列中某一项的计算必须严格依赖前面的某几项，无论递归深度达到多少都满足，不存在终止递归的递归头，程序什么时候停止完全依赖于你设置让它算到哪一轮。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long[][] base = {{1, 1}, {1, 0}};
        long[][] res = {{1, 0}, {0, 1}};     // 单位矩阵
        if(n <= 2){
            System.out.println(1);     // 小于等于2直接输出
        }else{
            long p = n - 2;
            for(; p != 0; p >>= 1){
                if((p & 1) != 0) res = multiMat2D(res, base);
                base = multiMat2D(base, base);
            }
            System.out.println((res[0][0] + res[1][0]) % MOD);
        }
    }
    
    private static long[][] multiMat2D(long[][] A, long[][] B) {
        return new long[][]{{(A[0][0] * B[0][0] % MOD) + (A[0][1] * B[1][0] % MOD), (A[0][0] * B[0][1] % MOD) + (A[0][1] * B[1][1] % MOD)}, 
                            {(A[1][0] * B[0][0] % MOD) + (A[1][1] * B[1][0] % MOD), (A[1][0] * B[0][1] % MOD) + (A[1][1] * B[1][1] % MOD)}};
    }
}

发表于 2021-11-25 10:42:32 回复(0)
Java
jahentao头像 jahentao

求出二阶递推数列二阶递推数列 的状态矩阵状态矩阵。

推导

用矩阵快速幂求解矩阵幂。

注意到N的范围图片说明 ，用8个字节整数表示。

import java.util.*;
public class Main {
    public static final int mod = 1_000_000_007;
    public static long[][] multiply(long[][] matrix1, long[][] matrix2) {
        long[][] res = new long[matrix1.length][matrix1.length];
        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                long sum = 0;
                for (int k = 0; k < matrix1.length; k++)
                    sum = (sum + (matrix1[i][k] * matrix2[k][j]) % mod) % mod;
                res[i][j] = sum;
            }
        }
        return res;
    }
    public static long[][] powerN(long N, long[][] matrix) {
        long[][] res = new long[matrix.length][matrix.length];
        for (int i = 0; i < res.length; i++) 
            res[i][i] = 1;
        while (N != 0) {
            if ((N & 1) == 1) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            N = N >>> 1;
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        sc.close();
        if (N < 1) {
            System.out.println(0);
            return;
        }
        if (N == 1) {
            System.out.println(1);
            return;
        }
        long[][] matrix = {{1, 1}, {1, 0}};
        long[][] res = powerN(N - 1, matrix);
        System.out.println((res[1][0] + res[1][1]) % mod);
    }
}
发表于 2020-05-18 16:32:50 回复(0)
Durobert头像 Durobert
左神书上的代码转换成python的，过不了
发表于 2020-10-07 16:01:37 回复(0)
Java
码海泛舟头像 码海泛舟

本题的输入非常大，需要将左神的代码转为大数类型

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    static long n;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextLong();
        BigInteger res = f(n);
        System.out.println(res);
    }

    private static BigInteger f(long n) {
        if (n <= 2) return BigInteger.ONE;
        BigInteger[][] base = {{BigInteger.ONE, BigInteger.ONE}, {BigInteger.ONE, BigInteger.ZERO}};
        BigInteger[][] res = matrixPower(base, n - 2);
        return (res[0][0].add(res[1][0])).mod(new BigInteger(String.valueOf(mod)));
    }

    private static BigInteger[][] matrixPower(BigInteger[][] m, long p) {
        BigInteger[][] res = new BigInteger[m.length][m[0].length];
        //初始化res
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                if (i == j) {
                    res[i][j] = BigInteger.ONE;
                } else {
                    res[i][j] = BigInteger.ZERO;
                }
            }
        }
        BigInteger[][] tmp = m;
        while (p > 0) {
            if ((p & 1) == 1) res = muliMatrix(res, tmp);
            tmp = muliMatrix(tmp, tmp);
            p >>= 1;
        }
        return res;
    }

    private static BigInteger[][] muliMatrix(BigInteger[][] m1, BigInteger[][] m2) {
        BigInteger[][] res = new BigInteger[m1.length][m2[0].length];
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                res[i][j] = BigInteger.ZERO;
            }
        }
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] = (res[i][j].add(m1[i][k].multiply(m2[k][j]))).mod(new BigInteger(String.valueOf(mod)));
                }
            }
        }
        return res;
    }
}
发表于 2020-07-04 16:37:19 回复(0)
Python
cnzero头像 cnzero
一般的循环方法，提示超内存。
发表于 2020-04-01 15:35:33 回复(0)
Java
牛客640912481号头像 牛客640912481号
java 程序通不过
发表于 2020-02-28 19:06:19 回复(0)
提交观点

问题信息

数学 高级算法
上传者：小小
难度：
8条回答 6444浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号