5 способов вычисления чисел Фибоначчи: реализация и сравнение
Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.
Код предназначен для Python 3, хотя должен идти и на Python 2.
Для начала – напомню определение:
Замкнутая формула
Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого Fn = x n , а затем найти x.
Решаем квадратное уравнение:
Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:
что и используем для вычисления Fn.
from __future__ import division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5) Хорошее:
Быстро и просто для малых n
Плохое:
Требуются операции с плавающей запятой. Для больших n потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления Fn красиво с математической точки зрения, но уродливо — с компьютерной.
Рекурсия
Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:
fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1 Хорошее:
Очень простая реализация, повторяющая математическое определение
Плохое:
Экспоненциальное время выполнения. Для больших n очень медленно
Злое:
Переполнение стека
Запоминание
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.
Поэтому надо просто запоминать результаты, чтобы не подсчитывать их снова. Время и память у этого решения расходуются линейным образом. В решении я использую словарь, но можно было бы использовать и простой массив.
M = def fib(n): if n in M: return M[n] M[n] = fib(n - 1) + fib(n - 2) return M[n] (В Python это можно также сделать при помощи декоратора, functools.lru_cache.)
Хорошее:
Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти.
Плохое:
Тратит много памяти
Злое:
Возможно переполнение стека, как и у рекурсии
Динамическое программирование
После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.
Это решение часто приводится в качестве примера динамического программирования.
def fib(n): a = 0 b = 1 for __ in range(n): a, b = b, a + b return a Хорошее:
Быстро работает для малых n, простой код
Плохое:
Всё ещё линейное время выполнения
Злое:
Да особо ничего.
Матричная алгебра
И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что
А обобщение этого говорит о том, что
Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.
Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что
где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.
def pow(x, n, I, mult): """ Возвращает x в степени n. Предполагает, что I – это единичная матрица, которая перемножается с mult, а n – положительное целое """ if n == 0: return I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix(n): """Возвращает единичную матрицу n на n""" r = list(range(n)) return [[1 if i == j else 0 for i in r] for j in r] def matrix_multiply(A, B): BT = list(zip(*B)) return [[sum(a * b for a, b in zip(row_a, col_b)) for col_b in BT] for row_a in A] def fib(n): F = pow([[1, 1], [1, 0]], n, identity_matrix(2), matrix_multiply) return F[0][1] Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи
Сравнение быстродействия
Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.
n = 10 ** 6
Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд.
Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.
Теоретические замечания
Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:
Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности Fn. Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в А n — это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).
Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием «подсдвиги конечного типа», представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» . Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.
Посчитайте сумму элементов последовательности Фибоначчи в python
Нужно посчитать сумму из кода ниже. А так же минимум и максимум. Никак не могу понять. Получаются неправильные ответы. Помогите пожалуйста.
a = 0 b = 1 N = 30 print(a) print(b) for i in range(1, N-2): c = a a = b b = a + c if b % 2 == 0: print(-(b ** 2)) else: print(b) Отслеживать
CONTRAfact
задан 6 ноя 2022 в 5:57
CONTRAfact CONTRAfact
1 2 2 бронзовых знака
Добавьте в вопрос писание суммы, которую нужно сосчитать.
6 ноя 2022 в 8:00
0 1 1 -4 3 5 -64 13 21 -1156 55 89 -20736 233 377 -372100 987 1597 -6677056 4181 6765 -119814916 17711 28657 -2149991424 75025 121393 -38580030724 317811
6 ноя 2022 в 8:49
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Фактически здесь имеется некая последовательность на базе чисел Фибоначчи, поэтому известная формула суммы не подходит, так как чётные числа «превращаются» в отрицательные квадраты.
a = 0 b = 1 N = 30 min = 9E99 max = -9E99 sum = 0 for i in range(1, N-2): c = a a = b b = a + c f = - b * b if b % 2 == 0 else b sum += f if f < min: min = f if f >max: max = f print(f"sum = , min = , max=") sum = -40856333256, min = -38580030724, max=317811 Сумма чисел Фибоначчи
Сумма первых 15 нечетных чисел Фибоначчи с первыми 5 четными числами Фибоначчи
Ребята вообщем такое задание :Напишите программу для вычисления сумму первых 15 нечетных чисел.
Определить номер N числа Фибоначчи, при котором сумма N первых чисел Фибоначчи превышает заданное число М
Определить номер N числа Фибоначчи, при котором сумма N первых чисел Фибоначчи превышает заданное.
Сумма чисел Фибоначчи
Найти сумму чисел фибоначчи больше m или меньше n где m и n заданные натуральные числа 1<m<n. .
Сумма 11 и 13 чисел Фибоначчи
Не могу найти ошибку в коде. По заданию требуется найти сумму 11 и 13 чисел Фибоначчи. Вот.
35345 / 19945 / 4179
Регистрация: 12.02.2012
Сообщений: 33,093
Записей в блоге: 13
1 2 3 4 5 6 7 8
def sum_fib(n): c=1 p=0 s=0 while(cn): s+=c c,p=c+p,c return s
Регистрация: 14.05.2019
Сообщений: 132
Catstail, почему-то ничего не выводит, не понимаю решения
Am I evil? Yes, I am!
16119 / 9755 / 2730
Регистрация: 21.10.2017
Сообщений: 21,624
Сообщение от kokosic_n1 
не понимаю решения
А ты почитай, что такое функции. И сразу станет все понятно.
Регистрация: 14.05.2019
Сообщений: 132
iSmokeJC, причем здесь это, я читал об этом , я говорю о том, что не выводит ничего при вписывании какого-либо числа в программе Python
Am I evil? Yes, I am!
16119 / 9755 / 2730
Регистрация: 21.10.2017
Сообщений: 21,624
Сообщение было отмечено kokosic_n1 как решение
Решение
kokosic_n1, да действительно, при чем здесь то, что
— функцию нужно вызвать
— передать ей необходимые аргументы
— вывести то, что она возвращает
Вот я чушь сморозил!
Добавлено через 1 минуту
1 2 3 4 5 6 7 8 9 10 11
def sum_fib(n): c = 1 p = 0 s = 0 while c n: s += c c, p = c + p, c return s print(sum_fib(20))
Регистрация: 14.05.2019
Сообщений: 132
iSmokeJC, извините, спасибо большое, просто не понимаю,вам виднее конечно же
Am I evil? Yes, I am!
16119 / 9755 / 2730
Регистрация: 21.10.2017
Сообщений: 21,624
Сообщение от kokosic_n1
просто не понимаю
Ну вот я и говорю — почитай про функции!
814 / 526 / 214
Регистрация: 22.12.2017
Сообщений: 1,495
а лучше сначала начать с самого базового синтаксиса, print, input и тд.
Status 418
4357 / 2255 / 589
Регистрация: 26.11.2017
Сообщений: 5,186
Записей в блоге: 3
1 2 3 4 5 6
def sum_fib(n): c = 1 p = 0 while (c n): c, p = c+p, c return (c+p-1)
35345 / 19945 / 4179
Регистрация: 12.02.2012
Сообщений: 33,093
Записей в блоге: 13
Вот еще одно решение:
1 2 3 4 5 6 7 8 9 10 11 12
def fib_gen(): c=1 p=0 while(True): yield c c,p=c+p,c for f in fib_gen(): print(f) if (f > 1000000): break
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Сумма чисел Фибоначчи
1. Вычислить сумму чисел Фибоначчи , значение которых не превосходит 500.
Сумма чисел Фибоначчи
Здравствуйте, помогите решить задачу, пожалуйста! Напишите программу которая вычисляет сумму.
Сумма чисел Фибоначчи.
Составьте программу согласно следующему условию. Числа Фибоначчи определяются по формулам 1; (.
Сумма чисел Фибоначчи
Напишите сценарий (командный файл) в Linux, который бы считал сумму к – чисел Фибоначчи. Параметр к.
Сумма 10 чисел Фибоначчи
Необходимо написать программу на асемблере, что бы она считала сумму 10 первых чисел фибаначи и.
Сумма чисел Фибоначчи
здраствуйте, я только начинаю осваивать этот язык и очень нужна помощь. Дали задачку, а я понятия.
Сумма чисел Фибоначчи
Надо сделать программу: вводится число с клавиатуры, это число должно быть ровно, как бы.
Как вычислить миллионное число Фибоначчи на Python
Как-то раз я захотел найти оптимальное решение для вычисления чисел Фибоначчи и решил попробовать вычислить стотысячное число в последовательности, а потом подумал: если бы я мог вычислить стотысячное, то почему бы не вычислить миллионное число? Поэтому сейчас я покажу, как у меня это получилось и с какими проблемами я столкнулся.
Последовательность Фибоначчи является одной из наиболее известных математических последовательностей и самым простым примером рекурсий. Каждое число последовательности состоит из суммы двух предыдущих, где начальными числами выступают 0 и 1. Выглядит это всё вот так:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и так до бесконечности…
В течение следующих нескольких минут я пройдусь по нескольким различным подходам, а затем покажу оптимальное решение задачи:
1. Простая рекурсия.
2. Использование кэша с рекурсией.
3. Итеративный метод.
4. Использование формулы Бине.
5. Вычисление миллионного числа.
Перед тем как начать, нужно отметить, что все упомянутые замеры времени основаны именно на моем оборудовании и на версии Python 3.9.1.
1. Простая рекурсия
Это очень простой способ вычислить n-ное число Фибоначчи в Python:
def recursiveFib(n):
if n == 1 or n == 2:
return 1
return recursiveFib(n - 1) + recursiveFib(n - 2)
Этот метод использует рекурсию, чтобы многократно вызывать функцию вычисления, рассчитывая предыдущее число и применяя его для вычисления следующего. Однако это и является недостатком метода, так как эта функция крайне неэффективная и ресурсоёмкая, ведь на каждой стадии она вычисляет два предыдущих числа, потом два предыдущих числа этого числа и так далее. В какой-то момент вы заметите, что вычисление одного числа будет занимать слишком много времени. На моем компьютере, например, вычисление 35-го числа Фибоначчи заняло 1,43 секунды. Поэтому очевидно, что вычисление еще больших значений стало бы невероятно медленным либо вообще практически невыполнимым.
2. Использование кэша с рекурсией
Поскольку мы постоянно вычисляем предыдущие два числа, то мы также можем использовать возможности кэширования для хранения числа, чтобы нам больше не нужно было их вычислять. Встроенный модуль functools позволяет нам использовать метод вытеснения из кэша (least recently used cache) — тип кэша, при котором все элементы в нем упорядочиваются по мере использования. Этот метод может значительно ускорить процесс.
from functools import lru_cache
@lru_cache()
def recursiveFibCached(n):
if n == 1 or n == 2:
return 1
return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)Первым делом, из модуля functools нужно импортировать декоратор lru_cache и поместить его перед функцией. Мы можем указать значение maxsize, чтобы обозначить, сколько элементов должно храниться в кэше, однако по умолчанию указывается 128, чего точно должно хватить. Благодаря использованию кэша мы можем вычислить 200-е число Фибоначчи всего за 0.0002252 секунды!
Однако единственной проблемой такой рекурсии является то, что если попытаться вычислить 501-е число, то программа выдаст ошибку RecursionError: maximum recursion depth exceeded in comparison . Эту проблему можно обойти, установив глубину рекурсии на какое-нибудь большее значение.
import sys
sys.setrecursionlimit(5000)
Теперь, чтобы вычислить тысячное число Фибоначчи, требуется лишь 0,001198 секунд. Однако с этим методом у меня случилась еще одна проблема, потому что по какой-то неведомой причине я так и не смог вычислить 1553-е число в последовательности, и даже после увеличения глубины рекурсии ничего не помогло: терминал переставал выдавать число и просто завершал работу программы. Это, очевидно, проблема и недостаток на пути к вычислению миллионного числа Фибоначчи.
3. Итеративный метод
Можно заметить, что в среде программистов использование рекурсивного метода решения проблемы часто рассматривается как плохая практика, гораздо лучше считаются итеративные методы вычисления. Мы также можем придумать итеративное решение для генерации чисел Фибоначчи:
def iterativeFib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
Этот метод можно использовать для вычисления любого числа Фибоначчи (однако я не проверял его на огромных числах), что также происходит очень быстро, так как всего за 0.0028195 я смог вычислить десятитысячное число Фибоначчи. И если подумать, почему бы не использовать этот метод для вычисления миллионного числа: это возможно, однако займет какое-то время перед тем как полностью загрузиться. Читайте дальше, и я расскажу, почему так происходит.
4. Формула Бине
Формула Бине — это формула, которую можно использовать для вычисления n-ного числа последовательности Фибоначчи, а это как раз то, что нам нужно. Эта формула названа в честь французского математика Жака Филиппа Мари Бине. Вот как она выглядит:
Фи (φ) равна золотому сечению:
Эту формулу мы можем использовать, если перенести ее в Python:
def formulaFib(n):
root_5 = 5 ** 0.5
phi = ((1 + root_5) / 2)
a = ((phi ** n) - ((-phi) ** -n)) / root_5
return round(a)
Обратите внимание, что в реализации на Python нам следует вернуть округленную версию вычисленного числа, так как при вычислении больших чисел Python возвращает число, в котором после запятой может быть более двадцати девяток в периоде. И это хорошо, поскольку теперь у нас нет циклов и мы можем сразу вычислить ответ, ведь так? Но и в этом методе есть небольшой недостаток. Если мы попытаемся вычислить что-либо выше 1475-го числа, то столкнемся с ошибкой: OverflowError: (34, result too large) . Это связано с тем, что в Python реализована система float, и она может иметь только определенное максимальное значение, которое мы превышаем, используя этот метод.
Эту проблему можно очень легко решить с помощью встроенного модуля Decimal, чтобы создать десятичный объект с гораздо большей точностью и размером для использования в нашем уравнении:
import decimal
def formulaFibWithDecimal(n):
decimal.getcontext().prec = 10000
root_5 = decimal.Decimal(5).sqrt()
phi = ((1 + root_5) / 2)
a = ((phi ** n) - ((-phi) ** -n)) / root_5
return round(a)
В этой новой функции мы устанавливаем значение точности до 10000 цифр и преобразуем значение корня из 5 в десятичный объект, а затем используем его в нашем уравнении. Такой способ позволяет нам легко вычислить десятитысячное число последовательности за невероятные 0,0692986 секунд, что является огромным улучшением по сравнению со всеми предыдущими методами.
5. Вычисление миллионного числа
Как вы, возможно, заметили, применение формулы работает значительно медленнее итеративного метода, если n = 10000. Это связано с тем, что в формуле нам нужно создавать десятичный объект и использовать его в уравнении, а это занимает больше времени, чем повторение одного и того же действия 10000 раз. Однако это еще не конец истории.
Если увеличить количество повторений, необходимых для выполнения цикла, то это может значительно увеличить время завершения всего процесса. В какой-то момент, когда n достигает примерно 89200, время расчета при итеративном методе становится равным времени вычисления по формуле, а когда n увеличивается еще больше, то время итеративного метода увеличивается больше, чем по сравнению с увеличением времени по формуле.
На графике видно, в какой точке пересекаются формула и итеративный метод. По мере увеличения n, время, затрачиваемое на расчет чисел Фибоначчи по формуле, растет в линейной прогрессии. А при итеративном решении время увеличивается вместе со значением n. Это дает нам понять, что миллионное число нужно будет вычислять по формуле. Кроме того, в качестве дополнительной меры для более точного вычисления числа мне пришлось поменять точность десятичного объекта с помощью decimal.getcontext().prec = 300000 .
На моем компьютере (а у вас это время может быть другим) вычисление миллионного числа Фибоначчи заняло:
- 8,832661 секунд с применением итеративного метода
- 1,151380 секунд, используя формулу Бине, что в 7,7 раз быстрее!
Если вам хочется увидеть само число, оно состоит из 208988 цифр и в виде текстового файла весит 209 Кб:
Заключение
Вот так я и вычислил миллионное число Фибоначчи. Да, конечно, можно было вычислить число и побольше, но на самом деле это не имеет практического смысла, да и заняло бы много времени даже с применением формулы Бине. Из графика выше можно прикинуть, что на вычисление миллиардного числа Фибоначчи потребуется 310,8467 секунд. Оставлю эти расчёты на ваше усмотрение.
- Топ-15 лайфхаков для работы с Python
- F-строки и 3 эффективных способа их применения
- Асинхронная многопоточность в Python