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

这篇具有很好参考价值的文章主要介绍了【算法】斐波那契数列通项公式。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

特征方程和通项公式

如果数列 a n a_n an的递推公式: a n = c 1 a n − 1 + c 2 a n − 2 a_n=c_1a_{n-1}+c_2a_{n-2} an=c1an1+c2an2------(1)

根据待定系数法,假设 a n − x a n − 1 = y ( a n − 1 − x a n − 2 ) a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2}) anxan1=y(an1xan2)-----(2)
(1)和(2)比较得

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

根据韦达定理, x , y x,y x,y是方程 t 2 − c 1 t − c 2 = 0 t^2-c_1t-c_2=0 t2c1tc2=0的两个根,我们也将这个方程称为数列 a n a_n an特征方程

根据方程(2)可以推出 a n − x a n − 1 = y n − 1 ( a 1 − x a 0 ) a_n-xa_{n-1}=y^{n-1}(a_1-xa_0) anxan1=yn1(a1xa0)(等比数列)-----(3)

下面我们将两个根 t 1 , t 2 t_1,t_2 t1,t2分别带入方程(3)得
【算法】斐波那契数列通项公式

( 5 ) ∗ t 1 − ( 4 ) ∗ t 2 (5)*t_1-(4)*t_2 (5)t1(4)t2

( t 1 − t 2 ) a n = ( a 1 − t 2 a 0 ) t 1 n − ( a 1 − t 1 a 0 ) t 2 n (t_1-t_2)a_n=(a_1-t_2a_0)t_1^n-(a_1-t_1a_0)t_2^n (t1t2)an=(a1t2a0)t1n(a1t1a0)t2n

再整理得

a n = a 1 − t 2 a 0 t 1 − t 2 t 1 n − a 1 − t 1 a 0 t 1 − t 2 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 an=t1t2a1t2a0t1nt1t2a1t1a0t2n

a 0 , a 1 , t 1 , t 2 a_0,a_1,t_1,t_2 a0,a1,t1,t2均已知,可当作常项,于是 a n a_n an通项公式

a n = A t 1 n + B t 2 n a_n=At_1^n+Bt_2^n an=At1n+Bt2n
t 1 , t 2 t_1,t_2 t1,t2是特征方程的两个根
A , B A,B A,B为常项,一般通过待定系数法求出

斐波那契通项公式

斐波那契数列的递推公式: a n = a n − 1 + a n − 2 a_n=a_{n-1}+a_{n-2} an=an1+an2

于是特征方程为: x 2 − x − 1 = 0 x^2-x-1=0 x2x1=0的两个根: x 1 = 1 + 5 2 x_1=\frac{1+\sqrt5}{2} x1=21+5 x 2 = 1 − 5 2 x_2=\frac{1-\sqrt5}{2} x2=215

a n = A x 1 n + B x 2 n a_n=Ax_1^n+Bx_2^n an=Ax1n+Bx2n,将 a 1 = 1 , a 2 = 1 a_1=1,a_2=1 a1=1,a2=1带入可求得 A = 1 5 , B = − 1 5 A=\frac{1}{\sqrt5},B=-\frac{1}{\sqrt5} A=5 1,B=5 1

即通项公式: a n = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] a_n=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n] an=5 1[(21+5 )n(215 )n]文章来源地址https://www.toymoban.com/news/detail-423867.html

到了这里,关于【算法】斐波那契数列通项公式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++算法 —— 动态规划(1)斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月10日
    浏览(44)
  • C语言实现求解斐波那契数列的四种方法及优化处理(递归,迭代,特殊性质公式,矩阵快速幂)

            众所周知, 斐波那契数列 是非常经典的一个数列,它的数学公式如下         为了便于观察,我们列出它的几项:0  1  1  2  3  5  8  13  21......         下面我们将介绍四种方法来用C语言计算机代码实现对斐波那契数列的求解,分别是:递归法,迭代法

    2023年04月09日
    浏览(35)
  • 一分钟学算法-递归-斐波那契数列递归解法及优化

    一分钟学一个算法题目。 今天我们要学习的是用递归算法求解斐波那契数列。 视频教程链接:https://www.bilibili.com/video/BV1Wu4y1i7JJ/ 首先我们要知道什么是斐波那契数列。 斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都

    2024年02月11日
    浏览(48)
  • 递归以及斐波那契数列递归算法和迭代算法的实现与分析

    程序调用自身的编程技巧称为递归( recursion) 递归有两个过程,简单地说一个是 递的过程 ,一个是 归的过程 。 递归的两个必要条件 1. 存在限制条件 ,当满足这个限制条件的时候,递归便不再继续。 2.每次递归调用之后越来越 接近这个限制条件 . 递归本质就是函数调用

    2024年02月12日
    浏览(37)
  • Java数据结构与算法:动态规划之斐波那契数列

    大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里,让我们一同探讨Java中的动态规划,重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法,通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)
  • 线性代数 --- 计算斐波那契数列第n项的快速算法(矩阵的n次幂)

    The n-th term of Fibonacci Numbers:         斐波那契数列的是一个古老而又经典的数学数列,距今已经有800多年了。关于斐波那契数列的计算方法不难,只是当我们希望快速求出其数列中的第100,乃至第1000项时,有没有又准又快的方法,一直是一个值得探讨和研究的问题。笔者

    2024年04月27日
    浏览(44)
  • JAVA-斐波那契数列

    输入一个整数 n ,求斐波那契数列的第 n 项。 假定从 0 开始,第 0 项为 0 。 数据范围 0≤n≤39 样例

    2024年02月10日
    浏览(50)
  • Python斐波那契数列

    斐波那契数列是一个经典的数学问题,在 Python 中可以使用多种方法来实现,下面是几个常见的实现方式: 1. 使用递归 ```python def fibonacci_recursive(n):     if n = 1:         return n     else:         return fibonacci_recursive(n-1) + fibonacci_recursive(n-2) ``` 2. 使用循环 ```python def fibonacci_i

    2024年02月02日
    浏览(44)
  • 斐波那契数列应用2

    目录 斐波那契数列应用2 程序设计 程序分析  系列文章 【问题描述】定义如下序列:f(1)=1,f(2)=1;f(n)=(A*f(n-1)+B*f(n-2))mod7     给定A和B,请你计算f(n)的值。 【输

    2023年04月10日
    浏览(52)
  • c 斐波那契数列输出

    在C语言中,我们可以通过递归或循环的方法来实现斐波那契数列的输出。首先,我们需要明白斐波那契数列的定义:任一项数字是前两项的和(最开始两项均定义为1)。下面是具体的实现方式。 使用递归方法: #include stdio.h int main() {     int m = 0, n = 1, sum;     printf(\\\"请输入

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包