Числа Фибоначчи. Подборка алгоритмов на python

Эта шутка про числа Фибоначчи хуже, чем две предыдущие вместе взятые...

Кто такой Фибоначчи?

Леона́рдо Пиза́нский (ок. 1170 - 1250 гг, г. Пиза, Италия) — первый крупный математик средневековой Европы.

Фибоначчи (итал. Fibonacci) - это прозвище Леонардо, сокращение от двух слов «filius Bonacci» (сын Боначчи).

Числа Фибоначчи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …

Последовательность, в которой каждое последующее число равно сумме двух предыдущих.

Алгоритмы

Иногда на собеседованиях просят написать код для расчёта ряда Фибоначчи из n элементов. Приводим несколько популярных алгоритмов.

1. Обычный и неэффективный код с рекурсией.

Результат: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

В данном случае мы считаем ряд для числа 20, но в функцию range() передается 21, т.к. последний элемент с конца не учитывается из-за особенностей работы функции.

Проблемность этого алгоритма заключается в том, что происходит повторный перерасчет уже рассчитанных сумм. При больших числах скорость расчета существенно снижается.

Посмотрим на примере числа 20 (часть работы рекурсивной функции).

Повторный вызов функции для уже рассчитанных значений выделен цветом

2. Алгоритм с мемоизацией (с запоминанием уже рассчитанных сумм чисел без повторного пересчета).

Результат: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

Создается словарь memo, который хранит в себе уже рассчитанные значения, что позволяет их не пересчитывать.

3. Алгоритм через "золотое число" фи (1,61...).

Результат: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]

4. Алгоритм с обычным циклом.

Результат: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] #фибоначчи #алгоритмы #питон #pythonснуля #python3 #python #программированиедляначинающих #програмирование #технологии