package com.wyj.ch4; /** * @author: wyj * @describe: * @version:V01 * @date: 2021/7/28- 3:36 */ public class h4a1b { /* f(1)=1 f(2)=2 f(3)=3 f(4)=4 f(5)=6 f(n)=f(n-1)+f(n-3) f(n-1):前一年的牛 f(n-3)出生的牛 暴力 时间复杂度O(2*N) * */ public static int f1(int n){ if(n<1){ return 0; } if(n==1||n==2|| n==3){ return n; } return f1(n-1)+f1(n-3); } /*f2:从左到右依次求出每一项的值,通过顺序计算求到第N项 时间复杂度O(N) * */ public static int f2(int n){ if(n<1){ return 0; } if(n==1||n==2|| n==3){ return n; } int res=3; //f(i) f(i-1) int pre=2; //f(i-1) f(i-2) int prepre=1; int tmp=0; int temp1=0; for (int i = 4; i <=n ; i++) { tmp=res; temp1=pre; res=res+prepre;//f(i)=f(i-1)+f(i-3) pre=tmp;//f(i-1) prepre=temp1; } return res; } /*矩阵乘法 时间复杂度:O(logN) int mod=(int) (1e9+7); 为防止数越界,最后输出第n项对mod取模的值 * */ public static int f3(int n){ int mod=(int) (1e9+7); if(n<1){ return 0; } if(n==1||n==2){ return n; } int[][]base={{1,1,0},{0,0,1},{1,0,0}}; int[][]res=matrixPower(base,n-3); // return 3*res[0][0]+2*res[1][0]+res[2][0]; return (3*res[0][0]+2*res[1][0]+res[2][0])%mod; } //求矩阵m的p次方 public static int[][] matrixPower(int [][]m,int p){ int[][]res=new int[m.length][m[0].length]; //先把res设为单位矩阵,相当于整数中1 for (int i = 0; i < m.length; i++) { res[i][i]=1; } int[][]tmp=m; //求p对应的二进制 for(;p!=0;p>>=1){ if((p&1)!=0){ res=mulMatrix(res,tmp); } tmp=mulMatrix(tmp,tmp); } return res; } //矩阵m1 矩阵m2相乘 public static int[][] mulMatrix(int [][]m1,int [][]m2){ int mod=(int) (1e9+7); int[][] res=new int[m1.length][m2[0].length]; 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]+m1[i][k]*m2[k][j]; res[i][j]=(res[i][j] + (m1[i][k]*m2[k][j])%mod)%mod; } } } return res; } }