📖 Типовая задача на собеседование Python

Условие задачи:
Напишите функцию, которая возвращает n-ое число Фибоначчи. Числа Фибоначчи определяются следующим образом:
— F(0) = 0
— F(1) = 1
— F(n) = F(n-1) + F(n-2) для n > 1

Примеры:
— Для n = 10 ожидается результат 55
— Для n = 15 — 610

Решение:

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

# Тестирование
print(fibonacci(10))  # 55
print(fibonacci(15))  # 610

Пояснение:
1️⃣ При n = 0 и n = 1 функция возвращает предопределённые значения 0 и 1 соответственно.
2️⃣ Для n > 1 используются две переменные a и b, которые хранят предыдущие числа Фибоначчи. На каждом шаге цикла они обновляются: a принимает значение b; b — сумму a + b. После завершения цикла возвращается b, содержащее искомое число.
3️⃣ Время работы: O(n), так как требуется n итераций. Память: O(1), потому что используются только две переменные.

Пишите свои варианты решения в комментариях 👇

@python_job_interview