6

我有一个不寻常的（我认为）问题。对于给定的数字 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，所以我认为我们一无所获。有任何想法吗？

4

5 回答 5

3

F n-1 = 圆形(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 n
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，这是接近但没有雪茄。

于 2012-04-14T16:41:13.657 回答
2

你的方程式

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

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

于 2012-04-14T14:52:26.230 回答
2

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。求解线性丢番图方程。如果它有解决方案，你就完成了。如果不是，则减n1 并重试，直到找到解决方案。

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

于 2012-04-14T14:54:12.707 回答
2

我不确定你在找什么。您提到的递归系列定义为：

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-3}就可以计算出F{n-1} and F{n-2}。这意味着您可以将数字追溯到无穷大，因此没有“最长”序列并且有无限多个有效序列。

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

更新：如果您希望将解决方案空间限制为所有F{i}都是非负整数的结果，您将只能获得少数（大多数情况下是单例）解决方案。

如果你计算原始斐波那契数（Fib{i}），很快你就会得到F{n} < Fib{i-1}；显然你不需要更进一步。然后，您可以尝试所有可能的 and 组合，F{0}这样F{1}-F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0}只有有限数量的非负F{0}and的可能性F{1}（您显然可以排除F{0}=F{1}=0）。然后看看哪些i（s）在满足平等的那些（s）中是最高的——你也F{0}得到F{1}了

于 2012-04-14T14:31:46.693 回答
0

Mimic the computation of Fibonacci numbers with a matrix (but with different initial values). [[0 1] [1 1]] to power k will yield [F_{n+k}, F_{n+1+k}] when multiplied by [F_{n}, F_{n+1}].

Since raising of a matrix to a power is an O(log n) (assuming multiplications of integers is O(1)), you can perform the whole calculation in O(log n) time until matrix coefficients start to dominate the computation.

I don't know how large the numbers with which you are working happen to be, but the nth power of this matrix is [[F_{n-1} F_n] [F_n F_{n+1}]]. And log(F_n) ~ n/5 (so the billionth Fibonacci number will have roughly 200 million digits).

于 2016-10-07T01:16:36.963 回答