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

Java

jahentao

归纳递推数组 $图片说明$ ,

代入初始值，求解状态矩阵 $图片说明$ 。

所以， $图片说明$ 。

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

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)

科大15届软工代言人

思路: 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<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)

pein531

和斐波那契数列问题一样，使用矩阵的快速幂将O(N)的时间复杂度压缩到O(logN)。对于第n年，牛的总数=上一年牛的总数+新生牛，而新生牛由三年前的全部牛所生（近两年的新生牛还不具备生育能力），因此得到状态转移方程

$f_{n}=f_{n-1} + f_{n - 3}$

根据依赖关系，写成矩阵相乘的通式

$[f_{n},f_{n-1},f_{n-2}]=[f_{n-1},f_{n-2},f_{n-3}]*\left[ \begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{matrix} \right]=[f_{3},f_{2},f_{1}]*\left[ \begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{matrix} \right]^{n-3}$

然后计算矩阵的快速幂得到答案

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static final 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());
        if(n <= 3){
            System.out.println(n);
        }else{
            long[][] base = new long[][]{{1, 1, 0}, {0, 0, 1}, {1, 0, 0}};
            long[][] res = new long[][]{{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
            long p = n - 3;
            while(p != 0){
                if((p & 1) != 0) res = multiMat2D(res, base);
                base = multiMat2D(base, base);
                p >>= 1;
            }
            System.out.println((3 * res[0][0] + 2 * res[1][0] + res[2][0]) % MOD);
        }
    }
    
    private static long[][] multiMat2D(long[][] A, long[][] B) {
        long[][] res = new long[A.length][B[0].length];
        for(int i = 0; i < res.length; i++){
            for(int j = 0; j < res[0].length; j++){
                long elem = 0;
                for(int k = 0; k < A[0].length; k++) elem = (elem + (A[i][k] * B[k][j] % MOD)) % MOD;
                res[i][j] = elem;
            }
        }
        return res;
    }
}

发表于 2021-11-25 13:12:07 回复(0)

C++

栗子吃栗子201804121313378

#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)

Emars

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)

SteveX

动态规划，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)

1sanguine

#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)

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

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题