Python: Ciąg Fibonacciego

Definicja

Ciąg Fibonacciego jest to ciąg liczb naturalnych, w którym każdy wyraz jest sumą dwóch poprzednich (przy założeniu, że pierwszy wyraz jest równy 0, a drugi jest równy 1).

Pierwsze 10 liczb ciągu Fibonacciego

\( F_0 = 0 \\ F_1 = 1 \\ F_2 = 1 \\ F_3 = 2 \\ F_4 = 3 \\ F_5 = 5 \\ F_6 = 8 \\ F_7 = 13 \\ F_8 = 21 \\ F_9 = 34 \)

Zero jako pierwszy wyraz ciągu jest dyskusyjny, jednak ja pozostanę przy tej opcji.

Algorytm rekurencyjny

def fib(n):
    if n == 0: return 0
    elif n == 1: return 1
    return fib(n-1) + fib(n-2)

Algorytm iteracyjny

p - poprzedni wyraz (na początku równy zerowemu wyrazowi)
w - obecny wyraz (na początku równy pierwszemu wyrazowi)
Pętla for i in range(n-1) wykona się n-1 razy, czyli np. dla n=2 wykona się 1 raz.

def fib_i(n):
    if n == 0: return 0
    elif n == 1: return 1
    p, w = 0, 1
    for i in range(n-1):
        p, w = w, p+w
    return w