2021-02-04：第一年農(nóng)場有1只成熟的母牛A颖御，往后的每年：①每一只成熟的母牛都會(huì)生一只母牛 ②每一只新出生的母牛都在出生的第三年成熟 ③每一只母牛永遠(yuǎn)不會(huì)死 。請問N年后牛的數(shù)量是多少 凝颇？
福哥答案2021-02-04：
舉例：
N=6，第1年1頭成熟母牛記為a疹鳄；
第2年a生了新的小母牛拧略，記為b，總牛數(shù)為2瘪弓；
第3年a生了新的小母牛垫蛆，記為c，總數(shù)為3腺怯；
第4年a生了新牛d袱饭，總數(shù)4；
第5年b成熟了呛占，ab分別生了一只虑乖，總數(shù)為6；
第6年c也成熟了晾虑，abc分別生了一只疹味，總數(shù)為9，故返回9.
遞推式是f(n)=f(n-1)+f(n-3)帜篇。
如果某個(gè)遞歸糙捺，除了初始項(xiàng)之外，具有如下的形式：
F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常數(shù))笙隙。
并且這個(gè)遞歸的表達(dá)式是嚴(yán)格的洪灯、不隨條件轉(zhuǎn)移的。那么都存在類似斐波那契數(shù)列的優(yōu)化竟痰，時(shí)間復(fù)雜度都能優(yōu)化成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
}
//兩個(gè)矩陣相乘
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
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
