生成"自己的"斐波纳契数列

Question

我有一个不寻常的(我认为)问题.对于给定数量F_n(我不知道n的值),我必须找到数字F_0,F_1,使得F_ {n} = F_ {n-1} + F_ {n-2}.另外的困难是这个序列应该尽可能长(F_n的值n应该是最高的),如果存在多个解决方案,我必须用最小的F_0.总之,我必须生成我自己的"斐波那契"序列.一些例子:

in:F_n = 10; out:F_0 = 0; F_1 = 2;

in:F_n = 17; out:F_0 = 1; F_1 = 5;

in:F_n = 4181; out:F_0 = 0; F_1 = 1;

我观察到的每个序列("Fibonacci规则")F_n有:

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

其中Fib_n是第n个斐波那契数.特别是斐波纳契数列确实如此.但我不知道这种观察是否值得.我们不知道n,我们的任务是找到F_1,F_0因此我认为我们什么也没有获得.有任何想法吗？

Answer 1

你的等式

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

是两个变量和的线性丢番图方程 。该链接提供了一种有效的算法来计算解决方案集的描述，该算法允许您找到具有和和最小值的解决方案（如果存在）。然后你可以尝试猜测，直到发现没有解决方案。该方法是 中的多项式。F_1F_0F_1 >= 0F_0 >= 0F_0n = 0, 1, ...log(F_n)