Числа Фибоначчи (вычисление с помощью цикла while и рекурсии)

Числа Фибоначчи – это ряд чисел, в котором каждое последующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13 и т.д.
Формула:
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2
Пример вычисления:
F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
F6 = F5 + F4 = 5 + 3 = 8
и т.д.

Вычисление n-го числа ряда Фибоначчи с помощью цикла

Алгоритм

  1. Ввести два начальных значения ряда (fib1 и fib2).
  2. Ввести номер определяемого элемента.
  3. Выполнять нижеследующие действия количество раз, равное по величине номеру определяемого элемента, уменьшенному на две единицы (т.к. первое и второе значение ряда уже известны).
    1. Сложить fib1 и fib2, присвоив результат третьей переменной (fib_sum).
    2. Поменять начальные значения: fib1 = fib2, а fib2 = fib_sum

Код на Python

fib1 = 1
fib2 = 1
 
n = input("Значение какого элемента ряда \
Фибоначчи вы хотите узнать? ")
n = int(n) # преобразование в целое число
 
i = 2 
while i < n:
    fib_sum = fib2 + fib1
    fib1 = fib2
    fib2 = fib_sum
    i += 1
 
print (fib_sum)

Рекурсивное вычисление n-го числа ряда Фибоначчи

Алгоритм

  1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу (т.к. первый и второй элементы ряда Фибоначчи равны единице).
  2. Во всех остальных случаях вызвать эту же функцию с аргументами n-1 и n-2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.

Код на Python

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

while i <= n:/*!!!!!!!*/

while i <= n:/*!!!!!!!*/
    fib_sum = fib2 + fib1
    fib1 = fib2
    fib2 = fib_sum
    i += 1
 
print (fib_sum)

Линейная рекурсия: def fib(n,

Линейная рекурсия:

def fib(n, a=0, b=1):
    if n == 0:
        return a
    else:
        return fib(n-1, b, a+b)

еще вариант def

еще вариант

def fib(n):
    a = b = 1
    while n - 1:
        a, b = b, a + b
        n -= 1
    return a
print fib(3)

более оптимизированный

более оптимизированный вариант по скорости выполнения и коду

#№:0,1,2,3,4,5,6,7
#F:0,1,1,2,3,5,8,13...
def fib(n):
    a,b=0,1
    for x in range(1,n): a,b=b,a+b
    return b
 
print(fib(7)) #13

Данный вариант для fib(0)

Данный вариант для fib(0) выдает результат 0, что не совсем правильно.

А как совсем правильно?

А как совсем правильно? (ru.wikipedia.org/wiki/%D7%E8%F1%EB%E0_%D4%E8%E1%EE%ED%E0%F7%F7%E8)

еще вариант

ваш рекурсивный вариант имеет экспоненциальную сложность, что не есть хорошо)

Находит первые n чисел ряда:

def fib(n):
    l = []
    a, b = 0, 1
    for _ in range(0, n):
        l += [b]
        a, b = b, a+b
    return l
 
print fib(10)