Нахождение чисел фибоначчи c. Находим N’е число Фибоначчи тремя способами за приемлемое время: основы динамического программирования. Вычисление n-го числа ряда Фибоначчи с помощью цикла while

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, ... . Иногда ряд начинают с нуля: 0, 1, 1, 2, 3, 5, ... . В данном случае мы будем придерживаться первого варианта.

Формула:

F 1 = 1
F 2 = 1
F n = F n-1 + F n-2

Пример вычисления:

F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...

Вычисление n-го числа ряда Фибоначчи с помощью цикла while

1. Присвоить переменным fib1 и fib2 значения двух первых элементов ряда, то есть присвоить переменным единицы.
2. Запросить у пользователя номер элемента, значение которого он хочет получить. Присвоить номер переменной n .
3. Выполнять следующие действия n - 2 раз, так как первые два элемента уже учтены:
   1. Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
   2. Переменной fib1 присвоить значение fib2 .
   3. Переменной fib2 присвоить значение fib_sum .
4. Вывести на экран значение fib2 .

Примечание. Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2 .

fib1 = 1 fib2 = 1 n = input () n = int (n) i = 0 while i < n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

Компактный вариант кода:

fib1 = fib2 = 1 n = int (input ("Номер элемента ряда Фибоначчи: " ) ) - 2 while n > 0 : fib1, fib2 = fib2, fib1 + fib2 n -= 1 print (fib2)

Вывод чисел Фибоначчи циклом for

В данном случае выводится не только значение искомого элемента ряда Фибоначчи, но и все числа до него включительно. Для этого вывод значения fib2 помещен в цикл.

fib1 = fib2 = 1 n = int (input () ) if n < 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

Пример выполнения:

10 1 1 2 3 5 8 13 21 34 55

Рекурсивное вычисление n-го числа ряда Фибоначчи

1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
2. Во всех остальных случаях вызвать эту же функцию с аргументами n - 1 и n - 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.

def fibonacci(n) : if n in (1 , 2 ) : return 1 return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )

Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

F n = F n-1 + F n-2

И F 1 = F 2 =1.

Замкнутая формула

Пропустим детали, но желающие могут ознакомиться с выводом формулы . Идея в том, чтобы предположить, что есть некий x, для которого F n = x n , а затем найти x.

Что означает

Сокращаем x n-2

Решаем квадратное уравнение:

Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:

Что и используем для вычисления F n .

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 потребуется большая точность.
Злое:
Использование комплексных чисел для вычисления F n красиво с математической точки зрения, но уродливо - с компьютерной.

Рекурсия

Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В 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 = {0: 0, 1: 1} 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 [ for j in r] def matrix_multiply(A, B): BT = list(zip(*B)) return [ for row_a in A] def fib(n): F = pow([, ], n, identity_matrix(2), matrix_multiply) return F

Хорошее:
Фиксированный объём памяти, логарифмическое время
Плохое:
Код посложнее
Злое:
Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия

Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе 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 от А до В равно в точности F n . Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в А n - это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).

Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием "подсдвиги конечного типа ", представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» {11}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.

Очень часто на разнообразных олимпиадах попадаются задачи вроде этой, которые, как думается на первый взгляд, можно решить с помощью простого перебора. Но если мы подсчитаем количество возможных вариантов, то сразу убедимся в неэффективности такого подхода: например, простая рекурсивная функция, приведенная ниже, будет потреблять существенные ресурсы уже на 30-ом числе Фибоначчи, тогда как на олимпиадах время решения часто ограничено 1-5 секундами.

Int fibo(int n) { if (n == 1 || n == 2) { return 1; } else { return fibo(n - 1) + fibo(n - 2); } }

Давайте подумаем, почему так происходит. Например, для вычисления fibo(30) мы сначала вычисляем fibo(29) и fibo(28). Но при этом наша программа «забывает», что fibo(28) мы уже вычисляли при поиске fibo(29).

Основная ошибка такого подхода «в лоб» в том, что одинаковые значения аргументов функции исчисляются многократно - а ведь это достаточно ресурсоемкие операции. Избавиться от повторяющихся вычислений нам поможет метод динамического программирования - это прием, при использовании которого задача разбивается на общие и повторяющиеся подзадачи, каждая из которых решается только 1 раз - это значительно повышает эффективность программы. Этот метод подробно описан в , там же есть и примеры решения других задач.

Самый просто вариант улучшения нашей функции - запоминать, какие значения мы уже вычисляли. Для этого нужно ввести дополнительный массив, который будет служить как бы «кэшем» для наших вычислений: перед вычислением нового значения мы будем проверять, не вычисляли ли его раньше. Если вычисляли, то будем брать из массива готовое значение, а если не вычисляли - придётся считать его на основе предыдущих и запоминать на будущее:

Int cache; int fibo(int n) { if (cache[n] == 0) { if (n == 1 || n == 2) { cache[n] = 1; } else { cache[n] = fibo(n - 1) + fibo(n - 2); } } return cache[n]; }

Так как в данной задаче для вычисления N-ого значения нам гарантированно понадобится (N-1)-е, то не составит труда переписать формулу в итерационный вид - просто будем заполнять наш массив подряд до тех пор, пока не дойдём до нужной ячейки:

<= n; i++) { cache[i] = cache + cache; } cout << cache;

Теперь мы можем заметить, что когда мы вычисляем значение F(N) , то значение F(N-3) нам уже гарантированно никогда не понадобится. То есть нам достаточно хранить в памяти лишь два значения - F(N-1) и F(N-2) . Причём, как только мы вычислили F(N) , хранение F(N-2) теряет всякий смысл. Попробуем записать эти размышления в виде кода:

//Два предыдущих значения: int cache1 = 1; int cache2 = 1; //Новое значение int cache3; for (int i = 2; i <= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 => через итерацию потеряет актуальность cache2, т.е. он и должен стать cache1 //Иными словами, cache1 -- f(n-2), cache2 -- f(n-1), cache3 -- f(n). //Пусть N=n+1 (номер, который мы вычисляем на следующей итерации). Тогда n-2=N-3, n-1=N-2, n=N-1. //В соответствии с новыми реалиями мы и переписываем значения наших переменных: cache1 = cache2; cache2 = cache3; } cout << cache3;

Бывалому программисту понятно, что код выше, в общем-то ерунда, так как cache3 никогда не используется (он сразу записывается в cache2), и всю итерацию можно переписать, используя всего одно выражение:

Cache = 1; cache = 1; for (int i = 2; i <= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Для тех, кто не может понять, как работает магия с остатком от деления, или просто хочет увидеть более неочевидную формулу, существует ещё одно решение:

Int x = 1; int y = 1; for (int i = 2; i < n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

Попробуйте проследить за выполнением этой программы: вы убедитесь в правильности алгоритма.

P.S. Вообще, существует единая формула для вычисления любого числа Фибоначчи, которая не требует никаких итераций или рекурсии:

Const double SQRT5 = sqrt(5); const double PHI = (SQRT5 + 1) / 2; int fibo(int n){ return int(pow(PHI, n) / SQRT5 + 0.5); }

Но, как можете догадаться, подвох в том, что цена вычисления степеней нецелых чисел довольно велика, как и их погрешность.