趣学算法 —— 兔子数列

14天阅读挑战赛
努力是为了不平庸~
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~

兔子问题

兔子数列即斐波那契数列，它的发明者是意大利数学家莱奥纳尔多斐波那契（Leonardo Fibonacci，1170—1250）。1202年，莱奥纳尔多撰写了《算盘全书》（Liber Abaci），该书是一部较全面的初等数学著作。

假设第1个月有1对初生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生的兔子开始，12个月后会有多少对兔子呢？

a 1 = 1 a 2 = 1 a 3 = a 2 + a 1 … a n = a n − 1 + a n − 2

a1​a2​a3​an​​=1=1=a2​+a1​…=an−1​+an−2​​

转化成矩阵形式
[ a 3 a 2 ] = [ a 1 + a 2 a 2 ] = [ 1 1 1 0 ] [ a 2 a 1 ]

= = [a3​a2​​]=[a1​+a2​a2​​]=[11​10​][a2​a1​​]
[ a 4 a 3 ] = [ 1 1 1 0 ] [ a 3 a 2 ] = [ 1 1 1 0 ] 2 [ a 2 a 1 ]

[a4a3]" role="presentation">[a4a3]$$\left[\begin{array}{c}{a}_4\\ a_3\end{array}\right]$$

=

[1110]" role="presentation">[1110]$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

[a3a2]" role="presentation">[a3a2]$$\left[\begin{array}{c}{a}_3\\ a_2\end{array}\right]$$

=

[1110]" role="presentation">[1110]$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

^2

[a2a1]" role="presentation">[a2a1]$$\left[\begin{array}{c}{a}_2\\ a_1\end{array}\right]$$

[a4​a3​​]=[11​10​][a3​a2​​]=[11​10​]2[a2​a1​​]

由此可知

[ a n a n − 1 ] = [ 1 1 1 0 ] n − 2 [ a 2 a 1 ] = [ 1 1 1 0 ] n − 2 [ 1 1 ]

=^{n-2} = ^{n-2} [an​an−1​​]=[11​10​]n−2[a2​a1​​]=[11​10​]n−2[11​]

因此问题转化成矩阵幂的求解：
A n = [ 1 1 1 0 ] n A^n =

^{n} An=[11​10​]n