一些废话

定义斐波那契数列为:
\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)$

代码:

#define MOD (1000000007)//这是取模的数字,无关紧要
long long cur,pre;
void dfs(LL a)
{
    if(a==1){pre=0,cur=1;return;}//当a为1
    if(a==2){pre=cur=1;return;}//当a为2
    if(a&1){dfs(a-1),swap(pre,cur),cur=(pre+cur)%MOD;return;}//当a为奇数
    //下面是当a为偶数
    dfs(a>>1);//dfs(a/2),这样就得到了Fib(a/2)和Fib(a/2-1)
    LL tem=cur;//下面是
    cur=(cur*cur%MOD+((cur*pre%MOD)<<1)%MOD)%MOD;//计算Fib(a)
    pre=(tem*tem%MOD+pre*pre%MOD)%MOD;//计算Fib(a-1)
}
分类: 文章

XZYQvQ

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

1 条评论

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

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

发表评论

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

你是机器人吗? =。= *