问生成“自己的”Fibonacci序列

EN

你的方程式

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

是一个linear Diophantine equation in two variables F_1和F_0。该链接提供了一种高效的算法来计算解集的描述，该算法允许您找到一个解，如果存在，则具有最小的F_1 >= 0、F_0 >= 0和F_0。然后，您可以尝试猜测n = 0, 1, ...，直到您发现没有解决方案。这种方法在log(F_n)中是多项式的。

我不知道你在找什么。您提到的递归序列定义为：

Fn = F{n-1} + F{n-2}

显然，如果开始值可以是任何值，我们可以任意选择F{n-1}，这将给出F{n-2} ( = Fn=F{n-1})。知道了F{n-1} = F{n-2} + F{n-3}，就可以从F{n-1} and F{n-2}计算出F{n-3}。这意味着你可以追溯到无穷大的数字，因此没有“最长”的序列，有无限多的有效序列。

在某种程度上，您正在计算一个具有初始值F{n}和F{n-1}的斐波那契逆序列，其中F{i} = F{i+2}-F{i+1}，i永远递减

更新:如果您希望将解决方案空间约束到所有F{i}都是非负整数的结果，那么您将只能得到少数(大多数情况下是单例)解决方案。

如果计算原始的斐波那契数(Fib{i})，很快就会得到F{n} < Fib{i-1}；很明显，您不需要进一步计算。然后，您可以尝试F{0}和F{1}的所有可能组合，这样F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0} --对于非负的F{0}和F{1}，只有有限的可能性(显然可以排除F{0}=F{1}=0)。然后看看在满足相等的i中，哪个(哪些)是最高的--您还可以得到F{0}和F{1}

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

其中Fib_n是第n个斐波纳契数。尤其是对于斐波那契数列，更是如此。但我不知道这个观察结果是否有价值。我们不知道n，我们的任务是找到F_1，F_0，所以我认为我们什么也没得到。

嗯，你在寻找最长的序列，这意味着你想要最大化n。

创建斐波那契数的查询表。从最大的n开始，比如Fib_n <= F_n，表中的前一个条目是fib_n{n-1}。现在唯一的变量是F_1和F_0。解决linear Diophantine equation问题。如果它有解决方案，你就完成了。如果没有，请将n减去1，然后重试，直到找到解决方案。

注意:解决方案总是存在的，因为F_2 = 1 * F_1 + 0 * F_0有解决方案F_2 = F_1。