【算法】斐波那契通项公式

作者: 如雨随行2020 | 来源:发表于2022-12-13 01:30 被阅读0次

计算题目
斐波那契数列
斐波那契数列通项公式
偶遇斐波那契数列通项公式
面试题10：斐波那契数列
斐波那契数列
斐波那契数列脚本设计
斐波那契数列青蛙跳台阶
面试题10- I. 斐波那契数列
斐波那契数列 - 递归与递推Python实现

特征方程和通项公式

如果数列 $a_n$ 的递推公式： $a_n=c_1a_{n-1}+c_2a_{n-2}$ -----(1)

根据待定系数法，假设 $a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2})$ -----（2）

（1）和（2）比较得
$\begin{equation} \left\{ \begin{array}{lr} x+y=c_1\\ xy=-c_2\\ \end{array} \right. \end{equation}$
根据韦达定理， $x,y$ 是方程 $t^2-c_1t-c_2=0$ 的两个根，我们也将这个方程称为数列 $a_n$ 的特征方程

根据方程（2）可以推出 $a_n-xa_{n-1}=y^{n-1}(a_1-xa_0)$ （等比数列）-----（3）

下面我们将两个根 $t_1,t_2$ 分别带入方程（3）得
$\begin{equation} \left\{ \begin{array}{lr} a_n-t_1a_{n-1}=t_2^{n-1}(a_1-t_1a_0)......(4)\\ a_n-t_2a_{n-1}=t_1^{n-1}(a_1-t_2a_0)......(5)\\ \end{array} \right. \end{equation}$
将 $(5)*t_1-(4)*t_2$ 得

$(t_1-t_2)a_n=(a_1-t_2a_0)t_1^n-(a_1-t_1a_0)t_2^n$

再整理得

$a_n=\frac{a_1-t_2a_0}{t_1-t_2}t_1^n-\frac{a_1-t_1a_0}{t_1-t_2}t_2^n$

而 $a_0,a_1,t_1,t_2$ 均已知，可当作常项，于是 $a_n$ 的通项公式：

$a_n=At_1^n+Bt_2^n$

$t_1,t_2$ 是特征方程的两个根

$A,B$ 是常项，一般通过待定系数法求出

斐波那契通项公式

斐波那契数列的递推公式： $a_n=a_{n-1}+a_{n-2}$

于是特征方程为： $x^2-x-1=0$ 的两个根： $x_1=\frac{1+\sqrt5}{2}$ 和 $x_2=\frac{1-\sqrt5}{2}$

则 $a_n=Ax_1^n+Bx_2^n$ ，将 $a_1=1,a_2=1$ 带入可求得 $A=\frac{1}{\sqrt5},B=-\frac{1}{\sqrt5}$

即通项公式： $a_n=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]$

计算题目
9. 斐波那契数列描述输出斐波那契数列的第n项（从0开始，第0项为0）。公式:f(n) = n, n <= ...
斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39斐波那契数列的公式（和跳台...
斐波那契数列通项公式
偶遇斐波那契数列通项公式
斐波那契数列 1,1,2,3,5,8,13,21........ 通项公式如下，默认证明如下： 1.高中待定系数...
面试题10：斐波那契数列
题目: 求斐波那契数列的第项。写一个函数，输入，求斐波那契（Fibonacci）数列的第项。斐波那契数列定义：扩展...
斐波那契数列
1 什么是斐波那契数列? 斐波那契数列 2 数学公式 3 代码实现题目描述大家都知道斐波那契数列，现在要求输入...
斐波那契数列脚本设计
标题：斐波那契数列与黄金分割引入：趣味引入，斐波那契数列与黄金分割故事:兔子数列的故事特征：发现规律通项：...
斐波那契数列青蛙跳台阶
题目一：求斐波那契数列的第n项。写一个函数，输入n，求斐波那契（Fibonacci）数列的第n 项。斐波那契数列的...
面试题10- I. 斐波那契数列
斐波那契数列题目描述写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定...
斐波那契数列 - 递归与递推Python实现
介绍斐波那契数列是一种经典的递归数列，根据斐波那契数列的数学定义，其第n项F(n)定义如下: 算法实现我们可以...