斐波那契数列(Fibonacci sequence),也称之为黄金分割数列,由意大利数学家列昂纳多・斐波那契(Leonardo Fibonacci)提出。斐波那契数列指的是这样的一个数列:1、1、2、3、5、8、13、21、34、……,这个数列从第 3 项开始,每一项都等于前面两项之和。在数学上,斐波那契数列可以被递推的方法定义如下:
F(1)=1,F(2)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*)
斐波那契数列是数学上面一个经典的例子,并且在日常生活中有很多应用,他还与黄金分割有着密不可分的联系,而且当 n 趋向于无穷大时,前一项与后一项的比值越来越逼近黄金分割值 0.618。
1. 用递归方法求解斐指历波那契数列
在本篇文章中,我们就需要利用递归的思想去求解斐波那契数列,当给出一个斐波那契中第几项的数字,然后求解出对应的斐波那契数值。在之前,我们已经定义了递归算法的相关概念,并且明确了需要应用递归时候的三要素:
递归终止条件;
递归终止时候的处理方法;
递归中重复的逻辑提取,缩小问题规模。
接下来,我们将利用递归的知识来解决斐波那契数列问题,明确在斐波那契数列求解问题中的递归三要素分别是什么。
斐波那契数列的递归终止条件
显然易见,通过观察斐波那契数列的定义,我们很容易发现当 n=1 或者 n=2 时,是斐波那契数列的陆前递归终止条件,这个时候可以给出斐波那契数列的具体值。
斐波那契数列递归终止时候的处理方法
同样的,基于斐波那契数列的递推定义唯悉搜,当斐波那契数列达到终止条件 n=1 或者 n=2 时,我们也很容易发现对应 F(1)=1,F(2)=1,这就是斐波那契数列在递归终止时对应的取值。
斐波那契数列的递归重复逻辑提取
按照斐波那契数列的数学定义,F(n)=F(n - 1)+F(n - 2)(n ≥ 3,n ∈ N*),即当 n ≥ 3 时,斐波那契数列中这一项的值等于前面两项的值之和,这样便可以将求解一个比较大的斐波那契数列转化为求解较小数值的斐波那契数列值,这里面有重复逻辑可以递归复用。
例如,当我们求解斐波那契数列中的 F(5) 时,按照定义,我们有:
F(5) = F(4) + F(3) // 递归分解
= ( F(3) + F(2) ) + ( F(2)+F(1) ) // 递归求解
= [ ( F(2)+F(1) ) + 1 ] + ( 1+1 ) // 递归求解,遇到终止条件就求解
= [(1+1) +1 ]+(1+1) // 归并
= 3 + 2 // 归并
= 5 // 归并
是的,斐波那契数列是一个集合。集合是指具有某种特定性质的具体的或抽象的对象汇总成的集体,这些对象称为该集合的元素。
“斐波那契”读作:fēi bō nà qì
1、斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为陵仿例子而引入,故又称为“兔子数列”。
指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,哪链n∈N*)。
2、Prufer数列是无根树的一种数列。在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2。它可以通过简单的李汪孙迭代方法计算出来。它由Heinz Prufer于1918年在证明cayley定理时首次提出。
3、等差数列是常见数列的一种,如果一个数列从第二项起,每一项与它的前一项的差等于同一个常数,这个数列就叫做等差数列,而这个常数叫做等差数列的公差,公差常用字母d表示。
4、等比数列是指从第二项起,每一项与它的前一项的比值等于同一个常数的一种数列,常用G、P表示。这个常数叫做等比数列的公比,公比通常用字母q表示(q≠0),等比数列a1≠ 0。其中{an}中的每一项均不为0。注:q=1 时,an为常数列。
5、帕多瓦数列是由帕多瓦总结而出的。它的特点为从第四项开始,每一项都是前面2项与前面3项的和。帕多瓦数列是:1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,151……