Числа Фибоначчи (вычисление с помощью цикла 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)

Создано