Быстрый поиск члена рекуррентного соотношения схожего с числами Фибоначчи
Fn = Fn-3 + Fn-1. F0 = 0, F1 = 1, F2 = 1. Можно ли модифицировать матрический способ поиска числа Фибоначчи для решения этой проблемы? Если нет, то возможен ли поиск члена быстрее O(n)?
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Ну давайте покумекаем. Имеется три члена ряда, нужно получить три следующих (с номерами на единицу больше)
[a b c]
[Fn-3 Fn-2 Fn-1] x [d e f] = [Fn-2 Fn-1 Fn]
[g h i]
Первый столбец матрицы перемножается со вектором слева и должен дать первый элемент вектора-результата Fn-2 из соотношения
Fn-2 = a * Fn-3 + d * Fn-2 + g * Fn-1
так что a=0, d=1, g=0
Второй столбец матрицы перемножается со вектором слева и должен дать Fn-1
Третий столбец матрицы перемножается со вектором слева и должен дать Fn
Получается
[0 0 1] ^(n-2)
[0 1 1] x [1 0 0] = [Fn-2 Fn-1 Fn]
[0 1 1]
Попробуйте проверить
Я проверил, для 43 степени даёт 8407925