首页 > 试题广场 > 斐波那契数列问题的递归和动态规划3
[编程题]斐波那契数列问题的递归和动态规划3
  • 热度指数:4508 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
假设农场中成熟的母牛每年只会生 1 头小母牛,并且永远不会死。第一年农场中有一只成熟的母牛,从第二年开始,母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 n,求出 n 年后牛的数量。

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


输出描述:
输出 n 年后牛的数量对 1e9 + 7 取模的值。
示例1

输入

6

输出

9

备注:
#include<iostream>
using namespace std;
long long int mod = 1e9+7; 
//参考程序员代码面试指南
struct node
{
    long long int matrix[3][3];
};
typedef struct node node;
node mutMatrix(node a,node b)
{
    node c;
    for(int i = 0;i < 3;i++)
    {
        for(int j = 0;j < 3;j++)
        {
            c.matrix[i][j] = 0;
            for(int k = 0;k < 3;k++)
            {
                c.matrix[i][j] =(c.matrix[i][j]+a.matrix[i][k]*(b.matrix[k][j]%mod))%mod;
            }
            
        }
    }
    return c;
}
node matrixPower(const node m,const long long int p)
{
    node res;
    long long int q = p;
    //建立一个单位矩阵(100,010,001)
    for(int i = 0;i < 3;i++)
    {
        for(int j = 0;j < 3;j++)
        {
            if(j == i)
            {
                res.matrix[i][j] = 1;
            }
            else
            {
                res.matrix[i][j] = 0;
            }
            
        }
    }
    node temp = m;
    for(;q != 0;q >>= 1)
    {
        if( (q & 1) != 0)
        {
            res = mutMatrix(res,temp);
        }
        temp = mutMatrix(temp,temp);
    }
    
    return res;
}

int main()
{
    long long int n;
    cin >> n;
    if(n < 1)
    {
        cout << 0;
        return 0;
    }
    if(n == 1)
    {
        cout << 1;
        return 0;
    }
    if(n == 2)
    {
        cout << 2;
        return 0;
    }
    if(n == 3)
    {
        cout << 3;
        return 0;
    }
    node mat;
    mat.matrix[0][0] = 1;mat.matrix[0][1] = 1;mat.matrix[0][2] = 0;
    mat.matrix[1][0] = 0;mat.matrix[1][1] = 0;mat.matrix[1][2] = 1;
    mat.matrix[2][0] = 1;mat.matrix[2][1] = 0;mat.matrix[2][2] = 0;
    node last = matrixPower(mat,n-3);
    //最后记得再取模一次,因为三个数之和可能还是太大
    cout << (3*last.matrix[0][0] + 2*last.matrix[1][0]+1*last.matrix[2][0])%mod;
    return 0;
}
发表于 2019-08-20 20:45:21 回复(0)

归纳递推数组图片说明 ,

代入初始值,求解状态矩阵图片说明

所以,图片说明

用快速幂将时间复杂度降到图片说明

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 || N == 2 || N == 3) {
            System.out.println(N);
            return;
        }
        long[][] matrix = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}};
        long[][] res = powerN(N - 3, matrix);
        System.out.println((3 * res[0][0] + 2 * res[1][0] + res[2][0]) % mod);
    }
}
发表于 2020-05-18 17:05:55 回复(1)
思路: x,y,z分别表示一岁,两岁,三岁及以上的母牛数量,sum(n)表示n年后母牛的总数量,即sum = x+y+z; n为0时,sum=0+0+1; n为1时,sum=1+0+1; n为2时,sum=1+1+1; while(n-2>0){ tmp=z; z=tmp+y; y=x; x=tmp; n--; } sum=x+y+z;
发表于 2020-03-15 12:51:54 回复(0)
#include <bits/stdc++.h>
using namespace std;

long long int mod = 1e9+7;
#define ll long long

vector<vector<ll>> matrix_mul(vector<vector<ll>>& A, vector<vector<ll>>& B) {
    int n = A.size();
    vector<vector<ll>> C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
            }
        }
    }
    
    return C;
}

vector<vector<ll>> qpow(vector<vector<ll>>& A, ll p) {
    int n = A.size();
    vector<vector<ll>> ans(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) ans[i][i] = 1;
    while (p) {
        if (p & 0x01) {
            ans = matrix_mul(ans, A);
        }
        A = matrix_mul(A, A);
        p >>= 1;
    }
    return ans;
}


int main() {
    ll n;
    cin >> n;
    
    if (n <= 3) {
        cout << n << endl;
    } else {
        vector<vector<ll>> A = {
            {1, 0, 1},
            {1, 0, 0},
            {0, 1, 0}
        };
        vector<vector<ll>> ans = qpow(A, n-3);
        cout << ((ans[0][0] * 3) % mod + (ans[0][1] * 2) % mod + ans[0][2]  % mod)  % mod << endl;
    }
    
    return 0;
}

发表于 2021-09-12 13:39:26 回复(0)
#include<bits/stdc++.h>
using namespace std;

int beat(long long k){
    if(k==1){
        return 1;
    }
    if(k==2){
        return 2;
    }
    if(k==3){
        return 3;
    }
    if(k==4){
        return 4;
    }
    else{
        long long a,b=1,c=2,d=3,e=4;
        for(long long i=4;i<k;i++){
            a=c+e;
            b=e;
            e=a;
            c=d;
            d=b;
        }
        int f=a%1000000007;
       return f;
    }
   
}
int main(){
    long long k;
    cin>>k;
    cout<<beat(k);
}


不通过

发表于 2020-07-09 18:52:33 回复(0)
import java.util.Scanner;

public class FibonacciDemo {
    /**
     * 矩阵乘法
     * @param A
     * @param B
     * @return
     */
    static long MAX = (long) (1e9 + 7);
    static long[][] dot(long[][] A, long[][] B) {
        assert (A[0].length == B.length);
        long tmp;
        long[][] R = new long[A.length][B[0].length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B[0].length; j++) {
                for (int k = 0; k < A[0].length; k++) {
                    R[i][j]+= A[i][k]* B[k][j];
                }
                R[i][j] = (long) (R[i][j]%MAX);
            }

        }
        return R;
    }

    /**
     * 矩阵快速幂模
     * @param a
     * @param b
     * @return
     */
    public static long[][] quickMod(long[][] a, long b) {
        long[][] ans = new long[3][3];
        b=b-3;
        //初始化为单位矩阵
        for(int i=0;i<3 ;++i) {
            ans[i][i] = 1;
        }
        //计算矩阵乘法
        while (b != 0) {
            if ((1 & b) == 1) {
                ans = dot(ans, a);
            }
            b >>= 1;
            a = dot(a , a) ;
        }
        return ans;
    }


    /**
     * 斐波那契通用公式:
     * {F(n),F(n-1),F(n-2)} = {{1, 0,1}, {1,0, 0},{0,1,0}}^(n-3) *  {F(3),F(2),F(1)}
     * @param args
     */
    public static void main(String[] args) {
        long[][] A = new long[][]{{1, 0,1}, {1, 0,0},{0, 1,0}};
        long[][] B = new long[3][3];
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        if (n > 3) {
            B= quickMod(A,n);
            long rs = (long) (3*B[0][0]+2*B[0][1]+B[0][2])%MAX;
            System.out.println(rs);
        } else {
            System.out.println(n);
        }

    }
}

发表于 2019-10-08 16:48:39 回复(0)
#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(3, 3);
    m[0][0] = 1;
    m[0][1] = 0;
    m[0][2] = 1;
    m[1][0] = 1;
    m[1][1] = 0;
    m[1][2] = 0;
    m[2][0] = 0;
    m[2][1] = 1;
    m[2][2] = 0;
    m = m.pow(n, mod);
    return m[0][0] % mod;
}

#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+1,m) << endl;
}

编辑于 2019-08-29 10:29:21 回复(0)
动态规划,f(n)代表第n年的牛数,所以f(n-1)代表了第n-1年的牛数。
f(n)比f(n-1)多出来的牛来自成熟牛的崽子。我们怎么知道n-1年有多少成熟牛和不成熟牛呢?
由题目可知,3岁大的牛就开始下崽子了,所以第n-3年所有的牛,成年的以及未成年的,在第n年都会下崽子了。
所以f(n) = f(n-1) + f(n-3);

具体方法与上面一题类似,用矩阵来代替快速幂。
只不过改为了三维矩阵:
f(n)=f(n-1)+0*f(n-2)+f(n-3)
f(n-1)=f(n-1)+0*f(n-2)+0*f(n-3)
f(n-2)=0*f(n-1)+f(n-2)+0*f(n-3)
所以状态矩阵为 
[1,0,1]
[1,0,0]
[0,0,1]
其他同上题,不再赘述。

关于下面老铁的超时问题,题目给出的N是long级别的整数,o(N)算法肯定超时了,用快速幂把时间复杂度降到了o(logN)。
发表于 2019-08-26 20:13:45 回复(0)
所有的牛都不会死,故第n - 1年的牛会活到第n年
成熟牛的数量:三年成熟,故n-3年的所有牛到n年肯定都成熟了
故 类似斐波那契数列,但 f(n)=f(n-1)+f(n-3)
发表于 2019-08-25 16:30:06 回复(0)
#include <iostream>
using namespace std;

#define VAL 1000000007

typedef long long LL;
int main()
{
	LL oldcow[4] = { 0 };
	LL newcow[4] = { 1 };
	LL N;
	cin >> N;
	for (LL i = 0; i < N; i++) {
		if (i < 3) {
			newcow[i + 1] = 1;
		}
		else {
			for (LL j = 0; j < 4; j++) {
				oldcow[j] = newcow[j];
			}
			newcow[0] = (oldcow[0] + oldcow[3])%VAL;
			newcow[1] = newcow[0];
			newcow[2] = oldcow[1];
			newcow[3] = oldcow[2];
		}
	}

	cout << (newcow[0] + newcow[2] + newcow[3])%VAL<< endl;
}
为什么说我超时。。。我的时间复杂度也不大啊
发表于 2019-08-17 15:18:28 回复(1)
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n;
int f=3;
ll mod = 1e9+7;
struct node{
    ll materix[5][5];
};

node mul(node a,node b)
{
    node res;
    memset(res.materix,0,sizeof(res.materix));
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=f;j++)
        {
            for(int k=1;k<=f;k++)
            {
                res.materix[i][j]=(res.materix[i][j]+a.materix[i][k]*b.materix[k][j]%mod)%mod;
            }
        }
    }
    return res;
}

node ksm(node a,ll b)
{
    node ans;
    memset(ans.materix,0,sizeof(ans.materix));
    for(int i=1;i<=f;i++)
        ans.materix[i][i]=1;
    while(b)
    {
        if(b&1)
            ans=mul(ans,a);
        b>>=1;
        a=mul(a,a);        
    }    
    return ans;
}
int main()
{
    while(cin>>n)
    {
        if(n==1||n==2)
        cout<<n<<endl;
        else
        {
            node a,b,ans;
            memset(a.materix,0,sizeof(a.materix));
            a.materix[1][1]=3;
            a.materix[2][1]=2;
            a.materix[3][1]=1;
            
            b.materix[1][1]=1,b.materix[1][2]=0,b.materix[1][3]=1;
            b.materix[2][1]=1,b.materix[2][2]=0,b.materix[2][3]=0;
            b.materix[3][1]=0,b.materix[3][2]=1,b.materix[3][3]=0;
            ans=ksm(b,n-3);
            ans = mul(ans,a);
            ll init = ans.materix[1][1];
            cout<<init<<endl;
        }
    }
    return 0;
}

发表于 2019-08-02 14:05:57 回复(0)