零基础学Python(23)

 

斐波那契数列:迭代 VS 递归

斐波那契数列

\[F(n) = \left\lbrace \begin{matrix} 1, 当n=1\\ 1, 当n=2\\ F(n-1)+F(n-2), 当n>2 \end{matrix} \right\rbrace\]

1.斐波那契数列:迭代

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

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

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


    return n3
        
number = int(input('输入一个整数:'))
result = fb(number)
print("%d 的斐波那契数列是 %d" % (number,result))

2.斐波那契数列:递归

def fb(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fb(n-1) + fb(n-2)

number = int(input('输入一个整数:'))
result = fb(number)
print("%d 的斐波那契数列是 %d" % (number,result))