斐波那契数列

· · 个人记录

斐波那契数列 递推公式

he，上数学课上疯了。

思路与推导

看到这题，我不禁想到了刚刚学完的特征根法求通项公式。

所以，我们就可以将该题转换为：

已知数列 {a_n} 满足：a_{n+2}=a_{n+1}+a_{n}。又 a_1=1，a_2=1。

我们使用待定系数法构造：

对比系数，不难发现： $\begin{cases} p+q=1\\pq=-1 \end{cases}

根据韦达定理，构造一元二次方程：

设：$a_n=A \times (\frac{\sqrt{5}+1}{2})^n+B \times (\frac{-\sqrt{5}+1}{2})^n$。 补充 $a_0=a_2-a_1=0$。 则 $\begin{cases} A+B=0 \\ A \times \frac{\sqrt{5}+1}{2}+B \times \frac{-\sqrt{5}+1}{2} =1 \end{cases}

解得:\begin{cases} A=\frac{\sqrt{5}}{5} \\ B=-\frac{\sqrt{5}}{5 }\end{cases}

所以:a_n=\frac{\sqrt{5}}{5} \times (\frac{\sqrt{5}+1}{2})^n-\frac{\sqrt{5}}{5} \times (\frac{-\sqrt{5}+1}{2})^n。

代码

现在我们已经得到了斐波那契数列的通项公式，我们只需照着公式模拟代码即可。

#include <stdio.h>
#include <math.h>
int main(){ 
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%.0f\n",(pow(((1+sqrt(5))/2),n)-pow(((1-sqrt(5))/2),n))/sqrt(5)); 
    }
    return 0;
}