Fibonacci Array

Fibonacci array (斐波那契数列)的编程实现

golden section/ratio 黄金分割/比 : 0.618

$A_n = A_{n-1} + A_{n-2} $

$\lim\limits_{n\to \infty} \frac{A_{n-1}}{A_n}=\frac{\sqrt{5}-1}{2} $

$ \begin{eqnarray}F(n)= \begin{cases} 1, &n=1 \cr 1, &n=2 \cr F(n-1)+F(n-2), &n>2 \end{cases}\end{eqnarray} $
利用迭代和递归两种算法来求出n = 20 时，F(n)=?

Iteration :

def Fibonacci(n):
    n1 = 1
    n2 = 1
    n3 = 1

    if n < 1:
        print('输入有误!')
        return -1

    while n >  2:
        n3 = n2 + n1
        n1 = n2
        n2 = n3
        n -= 1

    return n3

number = int(input('Please input an interger:'))
result = Fibonacci(number) 
print("n=%d时斐波那契数列值为：%d" % (number, result))

Recursion(divide and conquer algorithm) :

def Fibonacci(n):
    if n < 1:
        print('输入有误!')
        return -1 
    elif n == 1 or n==2:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)

number = int(input('Please input an interger:'))
result = Fibonacci(number) 
print("n=%d时斐波那契数列值为：%d" % (number, result))