我遇到了一个不寻常的(我认为)问题。对于给定的数字F_n(我不知道n的值)，我必须找到数字F_0，F_1，以使F_ {n} = F_ {n-1} + F_ {n-2}。另一个困难是该序列应尽可能长(F_n的值n应该是最高的)，如果存在更多的解决方案，那么我必须采用最小的F_0来解决。简而言之，我必须生成我自己的“斐波那契”序列。一些例子:
在:F_n = 10;
出:F_0 = 0; F_1 = 2;
在:F_n = 17;
出:F_0 = 1; F_1 = 5；
在:F_n = 4181;
出:F_0 = 0; F_1 = 1；
我观察到的每个序列(使用“斐波那契规则”)F_n都有:
F_n = Fib_n * F_1 + Fib_ {n-1} * F_0
其中Fib_n是第n个斐波那契数。对于斐波那契数列尤其如此。但是我不知道这种观察是否值得。我们不知道n，我们的任务是找到F_1，F_0，所以我认为我们一无所获。有任何想法吗？
最佳答案
你的方程式
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)中的多项式。