Как Написать Формулу Фибоначчи в Excel • Рекуррентное вычисление

Как Написать Формулу Фибоначчи в Excel

Увы, это доказательство не приносит полного удовлетворения, поскольку не отвечает на вопрос, откуда вообще берутся подобные удивительные формулы. Мы выясним это в разделе «Вывод формулы Бине».

Мы провели эксперимент, и выяснилось, что вычисление по формуле Бине даёт первую ошибку для числа F 71 : вместо правильного значения 308061521170129 получилось 308061521170130 .

Вывод формулы Бине

Для вывода формулы Бине мы без колебаний выбрали из миллиона различных методов самый, на наш взгляд, впечатляющий — метод производящих функций.

Пусть нас не волнует то, как именно будет вычисляться эта бесконечная сумма при тех или иных значениях z — мы отнесёмся к ней формально. Для наших целей важно лишь то, что определённые операции над последовательностями соответствуют определённым действиям над производящими функциями:

  • Умножение всех элементов последовательности A на число q приводит к умножению на q её производящей функции: q ⁢ A ⇄ q ⁢ A ⁡ z .
  • Поэлементной сумме или разности двух последовательностей отвечает сумма или разность их производящих функций: A ± B ⇄ A ⁡ z ± B ⁡ z .
  • Начальный элемент последовательности равен значению её производящей функции при нулевом z : A 0 = A ⁡ 0 .
  • Вставке нуля в начало последовательности соответствует умножение её производящей функции на z : ⊢ A = 0 A 0 A 1 A 2 A 3 … ⇄ z ⁢ A ⁡ z .
  • Удаление первого элемента последовательности приводит к вычитанию этого элемента из производящей функции и последующему делению на z : ⊣ A = A 1 A 2 A 3 … ⇄ A ⁡ z − A 0 z . Для удаления первых n элементов получаем ⊣ n A = A n A n + 1 A n + 2 … ⇄ A ⁡ z − A 0 + A 1 ⁢ z + A 2 ⁢ z 2 + … + A n − 1 ⁢ z n − 1 z n .

Сделаем небольшое замечание, которое читатели, не знакомые с производными, могут спокойно пропустить. Попытки вычислить A 1 как значение A ⁡ z − A ⁡ 0 z при нулевом z приводят к неопределённости типа 0 0 , которая раскрывается по правилу Лопиталя: A ⁡ z − A ⁡ 0 z ⁡ 0 = A ′ ⁡ 0 (штрих означает производную по z ). Впрочем, и так понятно, что A n = A n ⁡ 0 n ! ( A n — n -я производная по z ).

Рекуррентное вычисление

Рекурсивная версия

Рекуррентная сводит задачу вычисления F n к задачам вычисления чисел F n − 1 и F n − 2 . Это соображение приводит нас к рекурсивному решению, в котором вычислению F n посвящена отдельная процедура F с параметром n . Она возвращает n , если n < 2 . В противном случае она дважды рекурсивно вызывает сама себя — с параметрами n − 1 и n − 2 , после чего возвращает сумму значений, возвращённых при этих вызовах. Проще некуда.

Но, несмотря на изящество и простоту алгоритма, мы получаем программу-катастрофу. Мы убедились в этом, попытавшись вычислить с её помощью всего-то F 40 — это заняло на нашем компьютере около 108 секунд. Чтобы дождаться F 50 , у нас уже не хватило терпения.

Постараемся разобраться, что же приводит к столь долгой работе программы. На рисунке 9.1. «Рекурсивные вызовы при вычислении чисел Фибоначчи» мы протянули стрелки от одного числа Фибоначчи к другому, если вычисление первого из них повлекло рекурсивный вызов для вычисления другого.

Теперь, глядя на рисунок, подсчитаем, сколько раз вызывалась рекурсивная процедура для вычисления F 5 :

F 5 1 раз
F 4 1 раз (для вычисления F 5 )
F 3 2 раза (1 раз для вычисления F 5 и 1 раз для F 4 )
F 2 3 раза (1 раз для вычисления F 4 и 2 раза для F 3 )
F 1 5 раз (2 раза для вычисления F 3 и 3 раза для F 2 )
F 0 2 раза (для вычисления F 2 )

Всего для вычисления F 5 рекурсивная процедура вызывалась 14 раз, причём для каждого значения параметра в среднем больше двух раз. Это явный перебор, но пока это не производит столь жуткого впечатления. Что же будет при больших n ?

Рекурсивная версия с мемоизацией

Матричная версия

Матрицы

Матрица представляет собой прямоугольную таблицу, заполненную числами: a 1 , 1 a 1 , 2 ⋯ a 1 , n ⋮ ⋮ ⋮ ⋮ a k , 1 a k , 2 ⋯ a k , n . Каждое число (элемент матрицы) снабжается двумя индексами: первый — номер строки, а второй — столбца. Упомянутую матрицу можно кратко обозначить как a i , j , i = 1 ‥ k , j = 1 ‥ n .

Проиллюстрируем умножение матриц на примере: 2 3 1 − 5 4 6 ⁢ − 1 7 3 0 2 4 1 5 8 − 2 0 4 = 2 ⋅ − 1 + 3 ⋅ 2 + 1 ⋅ 8 2 ⋅ 7 + 3 ⋅ 4 + 1 ⋅ − 2 2 ⋅ 3 + 3 ⋅ 1 + 1 ⋅ 0 2 ⋅ 0 + 3 ⋅ 5 + 1 ⋅ 4 − 5 ⋅ − 1 + 4 ⋅ 2 + 6 ⋅ 8 − 5 ⋅ 7 + 4 ⋅ 4 + 6 ⋅ − 2 − 5 ⋅ 3 + 4 ⋅ 1 + 6 ⋅ 0 − 5 ⋅ 0 + 4 ⋅ 5 + 6 ⋅ 4 = 12 24 9 19 61 − 31 − 11 44 .

Матричные соотношения для чисел Фибоначчи

Довольно интриговать читателей. Пора уже объяснить, какое отношение матрицы имеют к числам Фибоначчи.

Оказывается, рекуррентное соотношение для чисел Фибоначчи можно записать в матричной форме: F n + 1 F n + 2 = 0 1 1 1 ⁢ F n F n + 1 = F n + 1 F n + F n + 1 . В качестве очевидного следствия этого равенства получим F n + k F n + k + 1 = 0 1 1 1 k ⁢ F n F n + 1 . В частности, при n = 0 получим F k F k + 1 = 0 1 1 1 k ⁢ 0 1 .

[expert_bq id=»1570″]При жизни Леонардо Пизанский очень любил математические турниры, по причине чего в своих работах Liber abaci Книга абака , 1202; Practica geometriae Практика геометрии , 1220, Flos Цветок , 1225 год исследование на тему кубических уравнений и Liber quadratorum Книга квадратов , 1225 задачи о неопределенных квадратных уравнениях очень часто разбирал всевозможные математические задачи. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] При жизни Леонардо Пизанский очень любил математические турниры, по причине чего в своих работах («Liber abaci» /«Книга абака», 1202; «Practica geometriae»/«Практика геометрии», 1220, «Flos»/«Цветок», 1225 год – исследование на тему кубических уравнений и «Liber quadratorum»/«Книга квадратов», 1225 – задачи о неопределенных квадратных уравнениях) очень часто разбирал всевозможные математические задачи.
Как Написать Формулу Фибоначчи в Excel • Рекуррентное вычисление

Как вычислить миллионное число Фибоначчи на Python

  • Умножение всех элементов последовательности A на число q приводит к умножению на q её производящей функции: q ⁢ A ⇄ q ⁢ A ⁡ z .
  • Поэлементной сумме или разности двух последовательностей отвечает сумма или разность их производящих функций: A ± B ⇄ A ⁡ z ± B ⁡ z .
  • Начальный элемент последовательности равен значению её производящей функции при нулевом z : A 0 = A ⁡ 0 .
  • Вставке нуля в начало последовательности соответствует умножение её производящей функции на z : ⊢ A = 0 A 0 A 1 A 2 A 3 … ⇄ z ⁢ A ⁡ z .
  • Удаление первого элемента последовательности приводит к вычитанию этого элемента из производящей функции и последующему делению на z : ⊣ A = A 1 A 2 A 3 … ⇄ A ⁡ z − A 0 z . Для удаления первых n элементов получаем ⊣ n A = A n A n + 1 A n + 2 … ⇄ A ⁡ z − A 0 + A 1 ⁢ z + A 2 ⁢ z 2 + … + A n − 1 ⁢ z n − 1 z n .

Метод 5 (Оптимизированный метод 4)
Способ 4 может быть оптимизирован для работы в O (Logn) временной сложности. Мы можем сделать рекурсивное умножение, чтобы получить мощность (M, n) в преобладающем методе (аналогично оптимизации, сделанной в этом посте)

F 5 1 раз
F 4 1 раз (для вычисления F 5 )
F 3 2 раза (1 раз для вычисления F 5 и 1 раз для F 4 )
F 2 3 раза (1 раз для вычисления F 4 и 2 раза для F 3 )
F 1 5 раз (2 раза для вычисления F 3 и 3 раза для F 2 )
F 0 2 раза (для вычисления F 2 )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: