F(n) = F(n-1) - F(n-2)
Я столкнулся с этой последовательностью в соревновании по программированию F(n)= F(n-1)-F(n-2); Учитывая F0 и F1 найти n-й член
( http://codeforces.com/contest/450/problem/B) (конкурс окончен)
Теперь решение этой проблемы выглядит следующим образом. Последовательность принимает значение f0, f1, f1-f0, -f0, -f1, f0 - f1, затем снова f0 и вся последовательность повторяется.
Я понял, что это значение повторяется, но не смог найти причину этого циклического порядка. Я искал циклический порядок и последовательности, но не смог найти достаточно материала, который мог бы дать реальное представление о причине цикла.
2 ответа
Еще один способ подойти к этой проблеме. Обратите внимание, что F(n) = F(n - 1) - F(n - 2) совпадает с F(n) - F(n - 1) + F(n - 2) = 0, что делает его линейной разностью уравнение. Такие уравнения имеют фундаментальные решения a ^ n, где a - корень многочлена: пусть F(n) = a^n, тогда a^n - a^(n - 1) + a^(n - 2) = (a^2 - a + 1)*a^(n - 2) = 0, поэтому a^2 - a + 1 = 0, который имеет два сложных корня (вы можете их найти), которые имеют модуль 1 и аргумент pi/3. Таким образом, их способности 1, a, a^2, a^3, ... перемещаются по окружности юнитов и возвращаются к 1 после 2 пи /(пи /3) = 6 шагов.
Этот анализ имеет тот же недостаток, что и соответствующий анализ для дифференциальных уравнений - как вы знаете, искать решения определенного вида? У меня нет ответа на этот вопрос, может быть, кто-то другой. В то же время, когда вы видите линейное разностное уравнение, подумайте о решениях вида a ^ n.
Если применить вашу оригинальную формулу для N-1
F(n -1) = F(n-2) - F(n -3)
Чем, если я заменю F(n-1) в исходном выражении F(n)
F(n) = F(n-2) - F(n -3) - F(n-2) = -F(n - 3)
F(n) = - F(n-3)
Поскольку позднее также действует, если я заменю n на n-3
F(n - 3) = - F(n -6)
Объединение двух последних
F(n) = -(-F(n-6)) = F(n-6)
Таким образом, последовательность является циклической с периодом шести