Fibonacci数列那些事！

对于Fibonacci 数，相信我们都不陌生，在初学编程时，算Fibonacci数往往是一个不错的编程习题，那么接下来一起深入了解一下Fibonacci数吧

先假设一个初始条件F(0)=0，F(1)=1，设一个递推关系为F(n)=F(n-1)+F(n-2)，（n>=2),在这之下可以得到一个数列，这个数列就叫做Fibonacci数列。

例如：数列：

1，1，2，3，5，8，13，21，34，55....，

这就是一个Fibonacci数列。一个特点就是这个数列从第3项开始，每一项都等于前两项之和。

下面将编程实现求Fibonacci数列的中的任意一项

solution1（循环):

def getNum(n):    a=0    b=1    for i in range(n):        a,b=b,a+b    return aprint(getNum(4))
结果：3

solution2（递归）:​​​​​​​

def GetNum(n):    if n==0:        return 0    elif n==1 or n==2:        return 1    else:        return GetNum(n-1)+GetNum(n-2)
print(GetNum(4))结果：3

solution3(公式）：

import math
def GetNUM(n):    d=math.sqrt(5)    return round(1/d*(((1+d)/2)**n-((1-d)/2)**n))
print(GetNUM(4))结果：3

好吧，到这里，我们至少学到了三种求解Fibonacci 数的方法，快打开电脑试一试吧！

当然，Fibonacci 数非常有意思，会有一些问题与Fibonacci 数相关，比如下面这个问题：

有一段楼梯有10级台阶，规定每一步只能跨一级或两级，要登上第 10 级台阶有几种不同的走法?

当然，也许初此见到会感觉非常难就像这样

但是，看了过程之后，你就会突然明白原来这如此简单

哈哈，过程是这样的：

首先，我们设F(n)表示上n级台阶的楼梯的不同方法数，显然易得F(1)=1,F(2)=2，

上完n级台阶可分为两种大状况，已经走完了n-1级，最后走一级，这种情况下方法数为F(n-1)，或者已经走完了n-2级，最后再走两级，这种方法数为F(n-2)。

那么递推关系为：F(n)=F(n-1)+F(n-2) (n>=3)

那么很显然，这就是Fibonacci数列，准确来说应该是一部分。我们要求10级台阶的方法数，对应Fibonacci数列则是第11项：

调用程序：​​​​​​​

def getNum(n):    a=0    b=1for i in range(n):        a,b=b,a+b    return aprint(getNum(11))
----------------结果：89

再次复习一下：

数列：

1，1，2，3，5，8，13，21，34，55，89....

从第3项开始，每一项都等于前两项之和，这样的数列就叫做Fibonacci 数列，第一项不是0，但在数学上，Fibonacci 数列是以递推的方法定义的，也就是这样

F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）