На этом шаге мы рассмотрим два способа решения этой задачи.
Знаменитый итальянский математик Фибоначчи (Леонардо Пизанский) открыл числа Фибоначчи в 1202 году, неожиданно обнаружив, что они играют важную
роль в различных сферах: математике, искусстве и биологии. На этом шаге мы покажем, как вычислить их с помощью одной строки кода.
Общее описание
Ряд Фибоначчи начинается с чисел 0 и 1, а каждое последующее число равно сумме двух предыдущих элементов ряда. Ряд Фибоначчи представляет собой
готовый алгоритм!
Код
В примере 6.10 вычисляется список первых n чисел Фибоначчи, начиная с 0 и 1.
Пример 6.10. Вычисление последовательности Фибоначчи в одной строке кода на Python
## Зависимости from functools import reduce ## Данные n = 10 ## Однострочник fibs = reduce(lambda x, _: x + [x[-2] + x[-1]], [0] * (n - 2), [0, 1]) ## Результат print(fibs)
Взгляните на код и попробуйте угадать результаты его выполнения.
Принцип работы
Мы опять воспользовались замечательной функцией reduce(). Вообще говоря, она удобна, когда необходимо агрегировать вычисляемую на ходу информацию о состоянии, например на основе только что полученных чисел Фибоначчи вычислить следующее число Фибоначчи. С помощью спискового включения реализовать подобное непросто, ведь оно не позволяет обычно обращаться к только что созданным им значениям. Мы передаем в функцию reduce() три аргумента, соответствующие
reduce(функция, итерируемый_объект, начальное_значение),
Альтернативное решение
Суммирование раз за разом двух чисел Фибоначчи - простая идея, лежащая в основе однострочника из примера 6.10. В примере 6.11 приведено другое красивое решение.
Пример 6.11. Однострочное решение для поиска чисел Фибоначчи другим путем
n = 10 x = [0, 1] fibs = x[0:2] + [x.append(x[-1] + x[-2]) or x[-1] for i in range(n - 2)] print(fibs) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
В этом фрагменте кода используется списковое включение с побочным эффектом: переменная x обновляется новым элементом ряда Фибоначчи (n - 2) раз. Обратите внимание, что метод append() не возвращает значения, а только None, эквивалентное False. Таким образом, оператор спискового включения генерирует список целых чисел на основе следующей идеи:
print(0 or 10) # 10
На первый взгляд кажется, что нельзя производить операцию or над двумя целыми числами, но, как вы помните, в основе типа Boolean лежит тип integer. Любое отличное от нуля целочисленное значение интерпретируется как True. Таким образом, операция or позволяет просто возвращать второе целочисленное значение, вместо того чтобы преобразовывать его в булево значение True. Очень изящный фрагмент кода Python!
Объектом-агрегатором тут служит простой список с двумя начальными значениями: [0, 1]. Напомним, что объект-агрегатор передается функции в качестве первого аргумента (в нашем примере x).
Второй аргумент - следующий элемент из итерируемого_объекта. Мы задали (n - 2) фиктивных значения в качестве начального значения итерируемый_объект, чтобы заставить функцию reduce() выполнить функцию (n - 2) раз (чтобы найти первые n чисел Фибоначчи - первые два, 0 и 1, мы уже знаем). Чтобы показать, что фиктивные значения итерируемого_объекта нас не интересуют, мы воспользовались "мусорным" параметром _ и просто добавляем новые числа Фибоначчи, вычисленные как сумма двух предыдущих чисел Фибоначчи, в конец списка агрегатора x.
Резюмируя: вы научились работать еще с одним паттерном однострочников Python, а именно созданием с помощью функции reduce() списка, с динамическим использованием только что обновленных или добавленных элементов для вычисления его новых элементов. Этот удобный паттерн очень часто встречается на практике.
На следующем шаге мы рассмотрим рекурсивный алгоритм бинарного поиска.
