2021-02-04：第一年农场有1只成熟的母牛A，往后的每年：①每一只成熟的母牛都会生一只母牛 ②每一只新出生的母牛都在出生的第三年成熟 ③每一只母牛永远不会死 。请问N年后牛的数量是多少 ？

2021-02-04：第一年农场有1只成熟的母牛A，往后的每年：①每一只成熟的母牛都会生一只母牛 ②每一只新出生的母牛都在出生的第三年成熟 ③每一只母牛永远不会死 。请问N年后牛的数量是多少 ？
福哥答案2021-02-04：

举例：
N=6，第1年1头成熟母牛记为a；
第2年a生了新的小母牛，记为b，总牛数为2；
第3年a生了新的小母牛，记为c，总数为3；
第4年a生了新牛d，总数4；
第5年b成熟了，ab分别生了一只，总数为6；
第6年c也成熟了，abc分别生了一只，总数为9，故返回9.

递推式是f(n)=f(n-1)+f(n-3)。

如果某个递归，除了初始项之外，具有如下的形式：
F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)。
并且这个递归的表达式是严格的、不随条件转移的。那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)。

代码用golang编写，代码如下：

package main

import "fmt"

func main() {
    fmt.Println(c3(6))
}
func c3(n int) int {
    if n < 1 {
        return 0
    }
    if n == 1 || n == 2 || n == 3 {
        return n
    }
    base := [][]int{
        {1, 1, 0},
        {0, 0, 1},
        {1, 0, 0}}
    res := matrixPower(base, n-3)
    return 3*res[0][0] + 2*res[1][0] + res[2][0]
}

//矩阵的p次方
func matrixPower(m [][]int, p int) [][]int {
    mLen := len(m)
    m0Len := len(m[0])
    res := make([][]int, mLen)
    for i := 0; i < mLen; i++ {
        res[i] = make([]int, m0Len)
    }

    for i := 0; i < mLen; i++ {
        res[i][i] = 1
    }

    tmp := m
    for ; p != 0; p >>= 1 {
        if p&1 != 0 {
            res = muliMatrix(res, tmp)
        }
        tmp = muliMatrix(tmp, tmp)
    }
    return res
}

//两个矩阵相乘
func muliMatrix(m1 [][]int, m2 [][]int) [][]int {
    m1Len := len(m1)
    m20Len := len(m2[0])
    m2Len := len(m2)
    res := make([][]int, m1Len)
    for i := 0; i < m1Len; i++ {
        res[i] = make([]int, m20Len)
    }

    for i := 0; i < m1Len; i++ {
        for j := 0; j < m20Len; j++ {
            for k := 0; k < m2Len; k++ {
                res[i][j] += m1[i][k] * m2[k][j]
            }
        }
    }

    return res
}

执行结果如下：

在这里插入图片描述

答案参考左神的java代码
评论

有疑问加站长微信联系（非本文作者）