首页 > 试题广场 >

奶牛家族

[编程题]奶牛家族
  • 热度指数：3384 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

在农场中，奶牛家族是一个非常庞大的家族，对于家族中的母牛，从它出生那年算起，第三年便能成熟，成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛，它从第二年开始生小母牛。请设计一个高效算法，返回第n年的母牛总数，已知n的范围为int范围内的正整数。

给定一个正整数n，请返回第n年的母牛总数，为了防止溢出，请将结果Mod 1000000007。

测试样例： 
6
返回：9
算法知识视频讲解
添加回答
Madstorm头像 Madstorm 
首先递推公式：F(n)=F(n-1)+F(n-3)
快速幂乘矩阵算法

class Cows:
    def countSum(self, n):
        res=base=[[0,0,1],[1,0,0],[0,1,1]]
        surplus=[[1,0,0],[0,1,0],[0,0,1]]
        while(n>1):
            if n&1:
                surplus=self.mutiply(surplus,res)
            res=self.mutiply(res,res)
            n=n>>1
        res=self.mutiply(res, surplus)
        return (res[0][1]+res[1][1]+res[2][1])%1000000007
    def mutiply(self,a,b):#矩阵乘法
        temp=[[0,0,0],[0,0,0],[0,0,0]]
        for i in range(len(a)):
            for j in range(len(b)):
                for k in range(len(temp)):
                    temp[i][j]+=a[i][k]*b[k][j]%1000000007
                     
        return temp

发表于 2015-08-26 21:17:45 回复(1)
牛客707439号头像 牛客707439号
按这题意还是F(n)=F(n-1)+F(n-2)，n-2年的母牛在同年就生小牛啊，经过n-2、n-1两年，到今年第n年刚好是第三年成为母牛啊！只是题中第一只母牛比较奇怪，非要拖到第二年才生而已啊。
发表于 2016-08-11 11:58:48 回复(1)
蓝魔4头像 蓝魔4 
class Cows {
public:
    void Multiply(long a[3][3],long b[3][3])
    {
        long res[3][3]={0};
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                for(int k=0;k<3;k++)
                {
                    res[i][j]+=a[i][k]*b[k][j]%1000000007;
                    res[i][j]%=1000000007;
                }
            }
        }
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
                a[i][j]=res[i][j];
        }
    }
    int countSum(int n) {
        if(n<4)
            return n;
        long res[3][3]={3,2,1,0,0,0,0,0,0};
        long base[3][3]={1,1,0,0,0,1,1,0,0};
        n-=3;
        while(n)
        {
            if(n%2)
            {
                Multiply(res,base);
            }
            Multiply(base,base);
            n/=2;
        }
        return (int)res[0][0]%1000000007;
    }
};

发表于 2017-07-19 12:01:36 回复(0)
老子是帮主头像 老子是帮主 
//这个题目O(N)时间复杂度的做法是过不了的，测试用例是大数，只有使用O(logN)时间复杂
//度的矩阵快速幂的思路才能通过。(Cn, Cn-1, Cn-2) = (Cn-1, Cn-2, Cn-3) × {{1,1,0},
//{0,0,1},{1,0,0}} = ......= (C3, C2, C1)×{{1,1,0},{0,0,1},{1,0,0}}的n-3次幂，
//注意这个矩阵{{1,1,0},{0,0,1},{1,0,0}}是可以通过解方程求出来的，9个未知数需要9个
//方程，所以多列出数列的前几项才能求出来。接下来问题就转变成了求解矩阵的n次幂问题
//了，如果n=8,我们只需要求出矩阵的4次幂就可以,要想求出4次幂，只需要求出2次幂就可以
//所以这个实际上就对应着n的二进制中等于1的进制位的数字依次相乘，结果就得到了矩阵
//的n次幂的O(logN)复杂度解法。还要提醒定义成int类型是过不了的，只有long long类型
//才能通过。涉及到大数运算，勿忘取模。
class Cows {
public:
    vector<vector<long long>> matrixPower(vector<vector<long long>> m, int p){
        int i = 0;
        int row = m.size();
        int col = m[0].size();
        //定义单位阵
        vector<vector<long long>> res(row, vector<long long>(col));
        for(i = 0;i < row;i++)
            res[i][i] = 1;
        
        vector<vector<long long>> temp = m;
        while(p){
            if(p & 1 == 1){
                res = multiMatrix(res, temp);
            }
            temp = multiMatrix(temp, temp);
            p = p >> 1;
        }
        return res;
    }
    
    vector<vector<long long>> multiMatrix(vector<vector<long long>> A, 
                                          vector<vector<long long>> B){
	vector<vector<long long>> result(A.size(), vector<long long>(B[0].size()));
        for (int i = 0; i < result.size(); i++){
            for (int j = 0; j < result[i].size(); j++){			
                for (int k = 0; k < A[0].size(); k++){
                    result[i][j] += (A[i][k] * B[k][j]) % 1000000007;
                    result[i][j] %= 1000000007;
                }
            }
        }
        return result;
	}
    
    int countSum(int n) {
        // write code here
        if(n < 1)
            return 0;
        else if(n == 1 || n == 2 || n == 3)
            return n;
        
        vector<vector<long long>> base = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}};
        vector<vector<long long>> res = matrixPower(base, n - 3);
        return (3 * res[0][0] + 2 * res[1][0] + res[2][0]) % 1000000007;
    }
};

编辑于 2017-07-23 17:50:54 回复(0)
总有刁民想害朕201808291700703头像 总有刁民想害朕201808291700703 
这道题最关键的是求取matrix矩阵，以及他的基数矩阵。我们可以通过Fn=Fn-1+Fn-3了解到，通过
F1，F2，F3可以表示出任何一个Fi,(4<=i<=n).该题中，F1,F2,F3=1,2,3. 然后matrix矩阵是
等于[1,1,0],[0,0,1],[1,0,0]的，然后再做矩阵的n-3次方幂就可以求出结果。
Mod=1000000007
class Cows:
    def countSum(self, n):
        if n<=4:
            return n
        else:
            matrix=[[1,1,0],[0,0,1],[1,0,0]]
            result_init=[[3,2,1],[0,0,0],[0,0,0]]
            result=self.matrixpower(matrix,n-3)
            res=self.multip(result_init,result)
            return res[0][0] % 1000000007
   
    def matrixpower(self,matrix,p): # matrix的p次方
        result=[[1,0,0],[0,1,0],[0,0,1]]
        base = matrix
        while p!=0:
            if p & 1:
                result = self.multip(result,base)
            base=self.multip(base,base)
            p>>=1
        return result

    def multip(self,A,B): #矩阵A，B相乘
        temp=[[0,0,0],[0,0,0],[0,0,0]]
        for i in range(len(A)):
            for j in range(len(B)):
                for k in range(len(temp)):
temp[i][j]+=(A[i][k]*B[k][j])%1000000007
        return temp

发表于 2019-04-10 10:56:58 回复(1)
Down头像 Down

矩阵快速幂
递推公式为D[n]=D[n-1]+D[n-3]

class Cows
{
public:
    int matN = 3;
    int const mod = 1e9 + 7;
    typedef long long ll;
    typedef vector v1;
    typedef vector<vector<int>> v2;
    void mul(vector>& a, vector>& b, vector>& ans)
    {
        for (int i = 0; i < matN; ++i)
        {
            for (int j = 0; j < matN; ++j)
            {
                ll t = 0;
                for (int k = 0; k < matN; ++k)
                {
                    t = (t + ll(a[i][k]) % mod * (b[k][j] % mod)) % mod;
                }
                ans[i][j] = t;
            }
        }
    }
    void fast_pow(vector>& mat, int n)
    {
        vector> ans(matN, vector(matN));
        for (int i = 0; i < matN; ++i)
            ans[i][i] = 1;
        auto t = mat, tmp = ans;
        while (n)
        {
            if (n & 1)
            {
                mul(ans, t, tmp);
                ans = tmp;
            }
            n >>= 1;
            mul(t, t, tmp);
            t = tmp;
        }
        mat = ans;
    }
    int countSum(int n)
    {
        if (n <= 3) return n;
        n -= 1;
        int f = n % matN;
        v2 mat = {{1, 1, 1}, {0, 1, 1}, {1, 1, 2}};
        int c = n / 3;
        fast_pow(mat, c);
        int ans = 0;
        ans = ((mat[0][f] % mod + 2ll * mat[1][f]) % mod + 3ll * mat[2][f]) % mod;
        return ans;
    }
};
编辑于 2018-05-14 19:39:46 回复(0)
沂飔头像 沂飔
答案有问题，，，class Cows {
    void mm(long a[9],long b[9]){
        long t[9],mod=1e9+7;
        t[0]=a[0]*b[0]+a[1]*b[3]+a[2]*b[6]%mod;
        t[1]=a[0]*b[1]+a[1]*b[4]+a[2]*b[7]%mod;
        t[2]=a[0]*b[2]+a[1]*b[5]+a[2]*b[8]%mod;
        t[3]=a[3]*b[0]+a[4]*b[3]+a[5]*b[6]%mod;
        t[4]=a[3]*b[1]+a[4]*b[4]+a[5]*b[7]%mod;
        t[5]=a[3]*b[2]+a[4]*b[5]+a[5]*b[8]%mod;
        t[6]=a[6]*b[0]+a[7]*b[3]+a[8]*b[6]%mod;
        t[7]=a[6]*b[1]+a[7]*b[4]+a[8]*b[7]%mod;
        t[8]=a[6]*b[2]+a[7]*b[5]+a[8]*b[8]%mod;
        memcpy(a,t,sizeof(long)*9);
    }
public:
    int countSum(int n){
        int s=n+1;
        long m[9]={1,1,0,0,0,1,1,0,0},e[9]={1,0,0,0,1,0,0,0,1};
        for(;s>1;s>>=1){
            int tt=s;
            if (s&1) mm(e,m);
            mm(m,m);
        }
        mm(m,e);
        return m[0];
    }
};
测试用例:
411910837

对应输出应该为:

694476150

你的输出为:

75100358
发表于 2017-06-15 20:47:08 回复(1)
Holiday_12138头像 Holiday_12138 
import java.util.*;
public class Cows {
    public int countSum(int n) {
        if(n<4)
            return n;
        long[][] res=new long[][]{{3,2,1}};
        long[][] base=new long[][]{{1,1,0},{0,0,1},{1,0,0}};
        n-=3;
        while(n>0){
            if((n&1)>0){
                res=multiply(res,base);
            }
            base=multiply(base,base);
            n=n>>1;
        }
        return (int) res[0][0]%1000000007;
    }
    public long[][] multiply(long[][] a,long[][] b){
        int L1=a.length;
        int L2=a[0].length;
        int L3=b[0].length; 
        long[][]  res=new long[L1][L3];
        for(int i=0;i<L1;i++)
            for(int j=0;j<L3;j++)
                for(int k=0;k<L2;k++){
                    res[i][j]+=a[i][k]*b[k][j]%1000000007;
                    res[i][j]%=1000000007;
                }         
        return res;
    }
}

发表于 2017-03-07 15:12:40 回复(0)
HelloWorldn头像 HelloWorldn 
final static int mod = 1000000007;
    public int countSum(int n) {
        int f1 = 1;
        int f2 = 2;
        int f3 = 3;
        if(n <= 4)return n;
        n -= 3;
        int[][] base = {{1,2,3}};
        int[][] matrix ={
                {0, 0, 1},
                {1, 0, 0},
                {0, 1, 1}
        };
        int[][] tmp ={
                {1, 0, 0},
                {0, 1, 0},
                {0, 0, 1}
        };
        int[][] tmp1 = matrixMlu(matrix, n);
        return mltHelp(base, tmp1)[0][2];
    }

    private int[][] matrixMlu(int[][] matrix, int n) {
        if(n == 1){
            return matrix;
        }
        if(n % 2==1){
            return mltHelp(matrix, matrixMlu(matrix, n-1));
        } else {
            int[][] tmp = matrixMlu(matrix, n / 2);
            return mltHelp(tmp, tmp);
        }
    }

    private int[][] mltHelp(int[][] a, int[][] b) {
        int[][] res = new int[3][3];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[i].length; k++) {
                    res[i][j] += (int)(((long)a[i][k] * (long)b[k][j]) % mod);
                    res[i][j] %= mod;
                }
            }
        }
        return res;
    }
发表于 2017-01-13 23:05:30 回复(1)
Java
阿华头像 阿华 
 
// 递推 f(n) = f(n-1)+f(n-3);
 class Mad{
 
 long[][] ad = new long[3][3];
 
}
public class Cows {
 
 int mod =1000000007;
 
 
 
 
 public Mad muti(Mad a,Mad b){
  
  long temp=0;
  
  Mad res = new Mad();
  
  for(int i=0;i<3;i++){
   for(int j=0;j<3;j++){
    for(int k=0;k<3;k++){
     
    // if(a.ad[i][k]>mod){a.ad[i][k]=a.ad[i][k]%mod;}
    // if(b.ad[k][j]>mod){b.ad[k][j]=b.ad[k][j]%mod;}
     
     temp += (a.ad[i][k]*b.ad[k][j])%mod;
     
     if(temp>mod){temp=temp%mod;}
  
    }
    
    res.ad[i][j] = temp;
    temp =0;
   }
  }
  
  return res;
  
 }
 
 public int countSum(int n){
  
  if(n==1){return 1;}
  if(n==2){return 2;}
  if(n==3){return 3;}
  
  int b = n-3;
  
  Mad res = new Mad();
  
  res.ad[0][0]=1;
  res.ad[1][1]=1;
  res.ad[2][2]=1;
  
  Mad a = new Mad();
  
  a.ad[0][0]=1;
  a.ad[0][2]=1;
  a.ad[1][0]=1;
  a.ad[2][1]=1;
  
  
  while(b>0){
   
   if((b&1)==1){
    
    res = muti(a,res); 
   }
   b>>=1;
   
   a = muti(a,a);
   
  }
  
  return (int)((3*res.ad[0][0]+2*res.ad[0][1]+res.ad[0][2])%mod);
  
  
  
 }
}

发表于 2016-07-26 16:40:48 回复(0)
高高的围墙头像 高高的围墙
class Cows {
public:
    const long Mod = 1000000007;

vector<vector<long long> > matrixMult(vector<vector<long long> > arr1, vector<vector<long long> > arr2){
    vector<vector<long long> > ret(3);
    ret[0].resize(3);
    ret[1].resize(3);
    ret[2].resize(3);
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j){
            for(int k = 0; k < 3; ++k){
                ret[i][j] += ((arr1[i][k] % Mod)*(arr2[k][j] % Mod)) % Mod;
            }
        }
    return ret;
}

vector<vector<long long> > GetmatrixPower(vector<vector<long long> > matrix, int n)
{
    vector<vector<long long> > ret(3);
    ret[0].resize(3);
    ret[1].resize(3);
    ret[2].resize(3);
    for (int i = 0; i < 3; ++i){
        ret[i][i] = 1;
    }
    vector<vector<long long> > tmp = matrix;
    for(; n != 0; n >>= 1){
        if((n & 1) == 1){
            ret = matrixMult(ret, tmp);
        }
        tmp = matrixMult(tmp, tmp);
    }
    return ret;
}

    int countSum(int n) {
        // write code here
        if(n <= 4) return n; 
         vector< vector<long long> > matrix(3);
        for(int i = 0; i < 3; ++i)
            matrix[i].resize(3);
        matrix[0][0] = matrix[0][1] = matrix[1][2] = matrix[2][0] = 1;
        matrix[0][2] = matrix[1][0] = matrix[1][1] = matrix[2][1] = matrix[2][2] = 0;
        vector<vector<long long> > res = GetmatrixPower(matrix, n-3);
        return ((3 * res[0][0])% Mod + (2 * res[1][0])% Mod + (res[2][0]% Mod))% Mod;
    }
};

主要方法(与斐波那契数列的最优算法类似)： 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)] * matrix
........
[f(n), f(n-1), f(n-2)] = [f(3), f(2), f(1)] * matrix^(n-3)
matrix = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}}
f(1) = 1, f(2) = 2, f(3) = 3
编辑于 2016-06-22 18:06:53 回复(0)
一枚水货头像 一枚水货 
public int countSum(int n) {       
        if(n<0)
		return 0;
	if(n<=3)
		return n;
        int[] arr=new int[n+1];
        arr[0]=0;
        arr[1]=1;
        arr[2]=2;
        arr[3]=3;
        for(int i=4;i<=n;i++){
        	arr[i]=(arr[i-1]+arr[i-3])%1000000007;
        }
        return arr[n];
}
内存超限:您的程序使用了超过限制的内存  。。。。
发表于 2016-06-19 11:30:59 回复(3)
祈祷祈祷祈祷祈祷头像 祈祷祈祷祈祷祈祷
如果用递归的话感觉挺简单，就是太慢了
    int countSum(int n) {
if(n<5)
return n;
return countSum(n-1)+countSum(n-3);
    }
发表于 2016-05-08 17:13:05 回复(0)
大漠刀客头像 大漠刀客
为什么这样不对？
第一年 3（3岁大的）
第二年 3  1（1岁大的）
第三年 3 ， 2 ， 1(3个)
第四年3,3,2,1(3+1)
第五年3,3,3,2,1,1,(3+1+2)
第六年3,3,3,3,2,2,1,1,1,（3+1+2+3 = 9个）
规律 3+1+2+。。。。。+n-3( n>=3 )
f[ n ] = (n-3)*(n-2)/2+3 ( n>=3 )； 
class Cows {
public:
    int countSum(int n) {
        // write code here
        
        long  int f[n] ;
        
        
        if( n>=3 )
        f[ n ] = (n-3)*(n-2)/2+3 ;
        else if( n==1 ) return 1 ;
        else if( n==2 ) return 2 ;
        
        if( n>=1000000007 )
        f[n]=f[n]%1000000007 ;
        
        return f[n];
        
        
    }
};
答案错误:您提交的程序没有通过所有的测试用例

case通过率为20.00%
测试用例:
411910837

对应输出应该为:

694476150

你的输出为:

16827198
发表于 2016-05-02 15:07:26 回复(2)
牛客251340号头像 牛客251340号 
class Cows {
public:
    int countSum(int n) {
        if(n<=3) return n;
        long long matrix[3][3] = {{1,1,0},{0,0,1},{1,0,0}}, matrix2[3][3] = {{1,0,0},{0,0,1},{1,0,0}}, matrix3[3][3] = {{1,0,0},{0,1,0},{0,0,1}};
        n = n-3;
        while(n!=0){
            if(n&1){
                for(int i = 0; i < 3; ++i){
                    for(int j = 0; j < 3; ++j){
                        matrix2[i][j] = (matrix3[i][0]*matrix[0][j]+matrix3[i][1]*matrix[1][j]+matrix3[i][2]*matrix[2][j])%1000000007;
                    }
                }
                for(int i = 0; i < 3; ++i){
                    for(int j = 0; j < 3; ++j){
                        matrix3[i][j] = matrix2[i][j];
                    }
                }
            }
            for(int i = 0; i < 3; ++i){
                for(int j = 0; j < 3; ++j){
                    matrix2[i][j] = (matrix[i][0]*matrix[0][j]+matrix[i][1]*matrix[1][j]+matrix[i][2]*matrix[2][j])%1000000007;
                }
            }
            for(int i = 0; i < 3; ++i){
                for(int j = 0; j < 3; ++j){
                    matrix[i][j] = matrix2[i][j];
                }
            }
            n = n>>1;
        }
        return (3*matrix3[0][0]+2*matrix3[1][0]+matrix3[2][0])%1000000007;
    }
};
编辑于 2015-10-14 16:25:47 回复(2)
筱沫头像 筱沫
1~7年分别为1只、2只、3只、4只、8只、13只、20只。所以上面的公式应该不对把，上面的公式是从第一只是小牛开始的,所以个人认为，公式应该为：f(n)=f(n-1)+f(n-3)+f(n-4)(n>5)
发表于 2015-08-13 10:46:48 回复(0)
攻城狮凌风头像 攻城狮凌风
f(n)=f(n-1)+f(n-3);
发表于 2015-08-05 15:45:01 回复(0)
Baymax头像 Baymax
很明显是这个题错了吧，第六年应该是13啊
发表于 2015-07-30 23:05:04 回复(2)
提交观点

问题信息

递归
来自：面试常考算法题(八)-...
难度：
18条回答 11347浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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