解斐波那契数列的三种方法

什么是斐波那契数列？

斐波那契数列又称黄金分割数列、兔子数列。
斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89…

观察数列我们很快就能发现F[n]=F[n-1]+F[n-2]规律，就是前两个数相加等于当前位置的数值

取第n个斐波那契数列数有三个思路

第一种:
可先准备第一个数和第二个数
这里我们把a1作为第一个数，a2作为第二个数
while循环 根据n的值开始相加 相加过程中 a2 = a1+a2 a1=a2
当n==0时即可输出答案

第二种:
根据n的值，初始化数组list1
将list1[0],list1[1]都赋值为1，作为斐波那契数列的第一个数和第二个数
再循环i=2到n-1
list1[i]=list1[i-1]+list[i-2]

第三种:
通过递归的方式
我们知道F[n]=F[n-1]+F[n-2]则易写出递归方式
(不是很推荐，因为时间复杂度高)