Теория чисел
Последовательность Фибоначчи в Python
Научитесь писать программы, использующие последовательность Фибоначчи!
Последовательность Фибоначчи проявляется и проявляется довольно многими способами в математике и информатике/программировании. Цель этой статьи — описать несколько способов, которыми вы можете увидеть появление Фибоначчи, и то, как использовать Python для обнаружения различных аспектов последовательности.
Что такое последовательность Фибоначчи?
Последовательность Фибоначчи — это последовательность натуральных чисел, начинающаяся с 1. Это выглядит так:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ....
Вы видите образец? N-е число Фибоначчи представляет собой сумму n-1-го и n-2-го чисел Фибоначчи.
Это важный момент, потому что с его помощью можно рекурсивно вычислить многие значения последовательности Фибоначчи. Давайте посмотрим, что мы можем сделать!
Последовательность Фибоначчи — это последовательность натуральных чисел, начинающаяся с
1, 1, а n-е число Фибоначчи — это сумма двух предыдущих членов.
Создание терминов последовательности Фибоначчи
Давайте сначала посмотрим, как мы можем эффективно генерировать термины Фибоначчи. Самый простой способ — использовать пустой список и цикл for для генерации терминов.
Во-первых, давайте определим наши переменные. Мы определяем a и b как первые два термина в последовательности и инициализируем список (с первыми двумя терминами, 1, 1 уже внутри него) с именем series .
Теперь мы кодируем наш цикл for. Мы хотим, чтобы он работал в цикле, генерируя n терминов последовательности Фибоначчи. Для целей этого примера мы установили n = 20 .
Здесь я настроил цикл for в range(2, n) . Поскольку в этом примере n равно 20, цикл for повторяется для каждого x в интервале [2,n]. Внутри цикла находится наше определение последовательности Фибоначчи: каждый элемент представляет собой сумму двух предшествующих ему элементов. Наконец, цикл добавляет этот термин в список series.
Печать series дает именно то, что мы хотим:
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
Нахождение n-го члена
Мы можем найти n-й член, используя код, который мы придумали в предыдущем разделе. Допустим, мы хотим найти i-й термин (здесь я использую i, потому что n уже является переменной). Для этого примера предположим, что мы хотим найти 200 034 члена последовательности Фибоначчи.
Я просто добавил еще одну переменную, i, и заменил print(series) на print(series[i - 1]). Вот результат:
192373285415866760557173433121516375224056333183434393978124354879532171146744121900663998692213158072140530482128152339686087292623251900269329431030759110518214979329456400212272402706074377403263085149104405417566753948669711296429582649835058544457983707589484754554876558078026664214361845487674198261493554551752199998272364859229929664626978362056289296383617431515020113224233955551537148621593421931721823689908385768027872232929533372485.............................
Обратите внимание, что я поставил длинную линию многоточий после числа. Это связано с тем, что весь результат слишком длинный, чтобы помещать его сюда! Приведенная выше часть составляет всего около 1 % от фактических цифр. Проведя некоторые тесты, оказалось, что печать этого числа заняла 4 секунды, не говоря уже о всем списке.
Нахождение суммы терминов
Теперь мы сделаем еще один шаг и попытаемся найти сумму членов последовательности Фибоначчи до члена n . Начнем с исходного кода, как всегда:
Теперь нам просто нужно написать еще один цикл for, чтобы найти сумму всех терминов в списке series. Для этого примера мы допустим n = 300: сумма первых 300 чисел Фибоначчи. Это должно быть легко:
Мы просто сказали, что для каждого термина в списке series установите сумму, равную существующей совокупной сумме плюс этот термин. Когда мы запускаем этот код, мы получаем ожидаемый результат:
581811569836004006491505558634099066259034153405766997246569400
Заключительные мысли и заключение
Теперь, когда я рассмотрел все основы последовательности Фибоначчи, позвольте оставить вам несколько вопросов для размышления:
- Попробуйте найти сумму всех нечетных членов до
n = 1000. - Попробуйте найти сумму всех четных членов до
n = 1000. - Попробуйте создать инструмент Python для Фибоначчи: пусть пользователь вводит собственные числа
А пока берегите себя и удачного кодирования!
