一些废话

定义斐波那契数列为:
\begin{equation}
\begin{cases}
Fib(1)=1 \\
Fib(2)=1 \\
Fib(i)=Fib(i-1)+Fib(i-2)
\end{cases}
\end{equation}

log2N复杂度内求Fib(N)可以用矩阵乘法做
但是我就是不喜欢咋啦?╭(╯^╰)╮
我问Pyh神犇他的递归求的方法,他很耐心地跟我讲解了,在此感谢~
这个方法使用的是递归求,不需要矩阵乘法快速幂啥的。。。编程复杂度比较低吧。。。

公式的证明

这里证明一个公式:
$$Fib(n)=Fib(m)\times Fib(n-m+1)+Fib(m-1)\times Fib(n-m)$$
证明:
$Fib(n)$
$=Fib(n-1)+Fib(n-2)$
$=2\times Fib(n-2)+Fib(n-3)$
$=3\times Fib(n-3)+2\times Fib(n-4)$
$=Fib(4)\times Fib(n-3)+Fib(3)\times Fib(n-4)$
以此类推
可以得到:
$$Fib(n)=Fib(m)\times Fib(n-m+1)+Fib(m-1)\times Fib(n-m)$$

方法解释

根据上面得到的公式,我们可以得到:
$$Fib(2n)=Fib(n)\times Fib(n+1)+Fib(n-1)\times Fib(n)$$
怎么得到的呢?就是设公式中的m为n,即2n的1/2
然后再拆开移项:
$Fib(2n)$
$=Fib(n)\times [Fib(n)+Fib(n-1)]+Fib(n-1)\times Fib(n)$
$=Fib^2(n)+2Fib(n)Fib(n-1)$

然后依然是m为n,我们求Fib(2n-1)
$Fib(2n-1)$
$=Fib^2(n)+Fib^2(n-1)$(可以直接带入原公式得到)

那么正片来了:
我们搞个递归函数dfs(a)
当a等于1时,Fib(a)=1,Fib(a-1)=0
当a等于2时,Fib(a)=Fib(a-1)=1
当a为偶数,我们可以dfs(a/2),求出Fib(a/2),Fib(a/2-1),然后Fib(a)就等于$Fib^2(a/2)+2Fib(a/2)Fib(a/2-1)$,Fib(a-1)就等于$Fib^2(a/2)+Fib^2(a/2-1)$
当a为奇数时,我们可以dfs(a-1),求出Fib(a-1),Fib(a-2),然后加起来得到Fib(a)
这样一直递归下去就能最后求得Fib(n)了
复杂度$O(log_2n)$

代码: