一些废话

定义斐波那契数列为:

$$
\begin{equation}
\begin{cases}
Fib(1)=1 \\
Fib(2)=1 \\
Fib(i)=Fib(i-1)+Fib(i-2)
\end{cases}
\end{equation}
$$

$\log _ 2 N$复杂度内求 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(\frac a 2),Fib(\frac a 2-1)$

然后 $Fib(a)$就等于 $Fib^2(\frac a 2)+2Fib(\frac a 2)Fib(\frac 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)$

代码:

LL cur, pre;

void dfs(LL a)
{
    if (a == 1){ pre = 0, cur = 1; return; }
    if (a == 2){ pre = cur = 1; return; }
    if (a & 1) { dfs(a - 1), swap(pre, cur), cur = (pre + cur) % m; return; }
    dfs(a >> 1);
    LL tem = cur;
    cur = (cur * cur % m + ((cur * pre % m) << 1) % m) % m;
    pre = (tem * tem % m + pre * pre % m) % m;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

konnyakuxzy · 2018年3月8日 3:20 下午

啊,最近听说了这个方法叫做 “折半搜索法”
QvQ

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注