Последовательность/числа Фибоначчи
Всем ку. Сегодня рассмотрим тему, которая скорее относится к математике, но мы напишем реализацию этого алгоритма на питоне. Начнем-с...
Для начала немного теории для тех, кто не шарит или забыл.
Ряд Фибоначчи - это числовая последовательность, в которой каждое следующее число является суммой двух предыдущих чисел. Обычно ряд Фибоначчи начинается с двух начальных членов: 0 и 1.
Краткая формула для ряда Фибоначчи:
Где F(n) - n-ное число в ряду Фибоначчи.
Пример последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
Если прям совсем просто, то был тип один. Взял он два числа - 0 и 1. Потом мозгами пошевелил и подумал "а что если сложить их?" и получил ряд: 0, 1, 1. Потом снова подумал и решил сложить уже следующие два числа и получил следующий ряд: 0, 1, 1, 2. А потом по новой и ряд был уже такой: 0, 1, 1, 2, 3.
Ну и дальше просто складывал число стоящие рядом и получилась ✨Последовательность Фибоначчи✨.
И вот вы, как простой обыватель, которому просто интересно изучать математику или информатику, зададитесь вопросом - " А зачем вообще все это нужно и где оно применяется то?". Ответ не заставит себя долго ждать.
- Простота конструкции: Ряд Фибоначчи легко определить и понять. Его правило очень простое: каждое число равно сумме двух предыдущих чисел.
- Широкое применение: Последовательность Фибоначчи встречается в различных областях математики, информатики и естественных наук. Она используется в алгоритмах оптимизации, теории вероятностей, теории чисел, компьютерной графике и даже в биологии.
- Приближение золотого сечения: Отношение двух последовательных чисел Фибоначчи приближается к золотому сечению, которое является важным математическим и эстетическим концептом.
Короче говоря, кент просто цифры складывал, а в итоге открыл довольно-таки фундаментальную штуку.
Что еще интересно - количество и способы реализации этого алгоритма в информатике. Сегодня я покажу вам аж целых три реализации данного алгоритма на Питухоне.
Рекурсивный подход
Ну тут распинаться не будем, кто знает что такое рекурсия - красавчик, кто не знает - тому в следующий раз постик сделаю. И вообще вернемся к коду.
Чтобы было нагляднее взгляните на картинку:
Примечание: в данном примере мы рассматриваем число ноль как нулевой член последовательности. Почему? Потому что в некоторых вариациях ряд Фибоначчи начинают сразу с единицы и он выглядит не как: 0, 1, 1, 2, 3, 5...; а как: 1, 1, 2, 3, 5, 8... Короче суть вы уловили, число ноль - нулевой член последовательности, а единица - первый член последовательности.
Объяснение очень подробное
Вот смотрите, нам нужно найти пятое число Фибоначчи, а оно является чем? Правильно, суммой 4 и 3 членов, значит для того, чтобы найти 5 член нужно знать чем является 3 и 4 члены. Далее, чтобы найти 3 член нужно сложить второй и первый члены. 1 член нам известен, а второй нет. Второй член это что? Правильно, сумма 1 и 0 члена. Отсюда мы находим - второй член это 0+1 = 1
Далее, третий член это второй плюс первый, то есть - 1+1 = 2.
Так, третий член мы нашли, теперь надо найти четвертый. Как мы говорили ранее - четвертый член это сумма третьего и второго, а они нам уже известны. Отсюда следует, что четвертый член последовательности это - 2+1 = 3.
Ура, вот теперь мы можем наконец найти чему равен пятый член последовательности - 3+2 = 5.
Надеюсь вы уловили идею. Мы берем нужный нам индекс и расписываем чем он является до тех пор, пока не дойдем до нулевого и первого членов последовательности, а далее собираем пазл обратно и получаем нужное нам значение. Так, зная значения 5 и 4 членов последовательности мы можем найти шестой - 5+3 = 8. И так далее до бесконечности.
Этот метод реализует формулу ряда Фибоначчи напрямую, но может быть неэффективным из-за повторных вычислений. Если попросить его вычислить, например, 175 член последовательности, то будем ждать вечность, ребят.
Итеративный подход
Тут код выглядит немного элегантней, но нужно еще учитывать, что такой подход считает НАМНОООООГО быстрее, чем рекурсивный.
Этот метод использует цикл for для генерации последовательности Фибоначчи. Переменные a и b инициализируются значениями первых двух чисел Фибоначчи: 0 и 1. Затем цикл выполняется n раз, на каждой итерации обновляя значения переменных a и b, чтобы получить следующее число Фибоначчи.
Использование генератора
Этот подход использует функцию-генератор для генерации бесконечной последовательности чисел Фибоначчи. Он работает аналогично итеративному методу, но вместо того, чтобы возвращать одно число, он возвращает числа по мере запроса с помощью оператора yield.
Функция-генератор сохраняет свое состояние между вызовами, позволяя ей "запоминать", на каком числе она остановилась. Это позволяет создавать бесконечные последовательности без необходимости заранее вычислять все элементы.
Этот код выведет первые 10 чисел последовательности Фибоначчи. После каждого вызова next(fib_sequence) генератор возвращает следующее число Фибоначчи.
Заключение
Ну вот собсна и все. Надеюсь, что вы усвоили для себя что-то новое и я был полезен для вас. Все три метода залью на пастбин чтобы вы могли покопаться во всем этом. Всё, всем спасибо и пока😘
ссылка на исходники - https://pastebin.com/4Ypz4ap1