algorithm - 生成 "own"斐波那契数列

Question

我有一个不寻常的(我认为)问题。对于给定的数字 F_n(我不知道 n 的值)，我必须找到满足 F_{n}=F_{n-1}+F_{n-2} 的数字 F_0、F_1。额外的困难是这个序列应该尽可能长(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;

我观察到的每个序列(使用“Fibonacci 规则”)F_n 是:

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

其中 Fib_n 是第 n 个斐波那契数。斐波那契数列尤其如此。但我不知道这种观察是否有值(value)。我们不知道 n，我们的任务是找到 F_1、F_0，所以我认为我们一无所获。有什么想法吗？

Answer 1

F _n-1 = round(F _n/φ)

其中 φ=(√5+1)/2。

证明留给读者作为练习;^P

更新 这是不正确的，回到绘图板。

更新 2 让我们从 F_n 和 F_n-1 向后计算。

F_n-2 = F_n - F_n-1
F_n-3 = F_n-1 - F_n-2 = F_n-1 - (F _n - F_n-1) = 2F_n-1 - F_n
F_n-4 = F_n-2 - F_n-3 = (F_n - F_n-1) - (2F_n-1 - F_n) = 2F_n - 3F_{n- 1}
F_n-5 = F_n-3 - F_n-4 = (2F_n-1 - F _n) - (2F_n - 3F_n-1) = 5F_n-1 - 3F
F_n-6 = F_n-4 - F_n-5 = (2F_n - 3F_n-1) - (5F_n-1 - 3F_n) = 5F_n - 8F_{n- 1}

注意到模式了吗？从真实斐波那契数列和最后两个成员中很容易计算出该数列的任何成员。但是我们只知道最后一个成员，怎么知道最后一个呢？

让我们根据 F_n-1 写下要求 F_i>0。

F_n-2 = F_n - F_n-1> 0 ⇒ F_n-1 < F_n
F_n-3 = 2F_n-1 - F_n> 0 ⇒ F_n-1> F<子>n /2
F_n-4 = 2F_n - 3F_n-1 ⇒ F_n-1 < 2F _n/3
F_n-5 = 5F_n-1 - 3F_n ⇒ F_n-1> 3F _n/5

因此，我们在 F_n-1 上有一系列以实际斐波那契数列的书面形式表示的边界，每一个都比前一个更紧。仍然可满足的最后一个边界确定对应于最长序列的 F_n-1。如果有多个数字满足最后一个边界，则使用最小或最大的数字，具体取决于序列的长度是偶数还是奇数。

例如，如果 F_n=101，则
101*5/8 < F_n-1 < 101*8/13 ⇒ F_n-1 = 63

之前的(不正确的)解决方案意味着 F_n-1 = 62，这很接近但没有雪茄。