F(n) = F(n-1) - F(n-2)
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 并重复整个序列。
我知道这个值正在重复，但找不到这个循环顺序的原因。我搜索了循环顺序和顺序，但找不到足够的 material 可以给出循环原因的实际感觉。
如果应用 n-1 的原始公式
F(n -1) = F(n-2) - F(n -3)
如果我在原始 F(n) 表达式中替换 F(n-1)
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)
因此序列是以六为周期循环的
解决此问题的另一种方法。请注意，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, ... 绕单位圆并在 2 pi/(pi/3) = 6 步后回到 1.
这个分析与对应的微分方程分析有同样的缺陷——你怎么知道要寻找某种解？我对此没有答案，也许其他人有。与此同时，每当你看到线性差分方程时，请考虑 a^n.
形式的解
我在一次编程竞赛中遇到了这个序列 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 并重复整个序列。
我知道这个值正在重复，但找不到这个循环顺序的原因。我搜索了循环顺序和顺序，但找不到足够的 material 可以给出循环原因的实际感觉。
如果应用 n-1 的原始公式
F(n -1) = F(n-2) - F(n -3)
如果我在原始 F(n) 表达式中替换 F(n-1)
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)
因此序列是以六为周期循环的
解决此问题的另一种方法。请注意，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, ... 绕单位圆并在 2 pi/(pi/3) = 6 步后回到 1.
这个分析与对应的微分方程分析有同样的缺陷——你怎么知道要寻找某种解？我对此没有答案，也许其他人有。与此同时，每当你看到线性差分方程时，请考虑 a^n.
形式的解