Step-by-step: the Fibonacci sequence (part 9011)

Пройдём задачу шаг за шагом — такой формат удобен для первого знакомства с алгоритмами.

Задача

Напечатать первые n чисел Фибоначчи: 0, 1, 1, 2, 3, 5, … Каждое следующее равно сумме двух предыдущих.

Решение

def fibonacci(n: int) -> list[int]:
    a, b = 0, 1
    result = []
    for _ in range(n):
        result.append(a)
        a, b = b, a + b
    return result


print(fibonacci(10))

Как это работает

Храним два последних числа и на каждом шаге сдвигаем пару вперёд одной строкой a, b = b, a + b. Рекурсия здесь не нужна и работает медленнее.

Пример работы

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Сложность

O(n) по времени, O(n) по памяти под результат.

Разбор по шагам

1. Шаг 1. Входные данные. Проверяем, что приходит в функцию, и какие значения считаются корректными.
2. Шаг 2. Основной цикл. Именно здесь происходит вся работа; следим за изменениями переменных на каждой итерации.
3. Шаг 3. Результат. Убеждаемся, что возвращаемое значение соответствует условию задачи, включая крайние случаи.

Когда каждый шаг понятен, доработка решения перестаёт быть лотереей.

Читайте также:

равно · print(fibonacci(10 · Решение · чисел · Задача · удобен · считаются · переменных · каждой · [listint · изменениями · каждом · вперёд · включая · Сложность · Пройдём · Фибоначчи · шагом · памяти · Именно · формат · соответствует · return