logo标签列表

生成“自己的”斐波那契数列

algorithmfibonacci
6
我有一个不寻常的（我认为）问题。对于给定的数字F_n（我不知道n的值），我必须找到数字F_0、F_1，使得F_{n}=F_{n-1}+F_{n-2}。额外的困难是这个序列应该尽可能长（F_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_1 = F_n 和 F_0 = 0 怎么样？你会得到最小的可能的 F_0！ - Shahbaz
@Shahbaz：但不是最长的序列。 - Gareth Rees
F_0和F_1必须是非负的吗？ - oldboy
所以我们又得到了另一个条件：F_{n} >= F_{n-1} :-) - xan
那么如何找到给定F_n的F_{n-1}呢？我的朋友告诉我应该这样看待它... 让F_n = 17，就像上面的例子一样，当我们知道F_{n-1} = 11时，我们有：F_{n-2} = 17 - 11 = 6; F_{n-3} = 11 - 6 = 5; F_{n-4} = 6 - 5 = 1，我们找到了前两个项（项必须是非负数）：F_0 = 1和F_1 = 5。但问题是如何找到F_{n-1}，有人有想法吗？也许这是解决这个问题最简单的方法。 - xan
显示剩余2条评论
5个回答
3

Fn-1 = round(Fn/φ)

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

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

更新 这是不正确的，请重新开始。

更新2 让我们从 Fn 和 Fn-1 开始逆向计算。

Fn-2 = Fn - Fn-1
Fn-3 = Fn-1 - Fn-2 = Fn-1 - (Fn - Fn-1) = 2Fn-1 - Fn
Fn-4 = Fn-2 - Fn-3 = (Fn - Fn-1) - (2Fn-1 - Fn) = 2Fn - 3Fn-1
Fn-5 = Fn-3 - Fn-4 = (2Fn-1 - Fn) - (2Fn - 3Fn-1) = 5Fn-1 - 3Fn
Fn-6 = Fn-4 - Fn-5 = (2Fn - 3Fn-1) - (5Fn-1 - 3Fn) = 5Fn - 8Fn-1

注意模式？很容易通过 真实的 Fibonacci 序列和最后两个成员计算任何序列成员。但我们只知道最后一个成员，如何知道倒数第二个成员呢？

让我们用 Fi>0 的要求来写出 Fn-1。

Fn-2 = Fn - Fn-1 > 0 ⇒ Fn-1 < Fn
Fn-3 = 2Fn-1 - Fn > 0 ⇒ Fn-1 > Fn/2
Fn-4 = 2Fn - 3Fn-1 ⇒ Fn-1 < 2Fn/3
Fn-5 = 5Fn-1 - 3Fn ⇒ Fn-1 > 3Fn/5

因此，我们有一个基于真实斐波那契数列的 Fn-1 边界序列，每个边界比前一个更紧。最后一个仍然可满足的边界确定了对应最长序列的 Fn-1 值。如果有多个数字满足最后一个边界条件，则根据序列长度是偶数还是奇数选择最小或最大的数字。

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

之前（不正确的）解决方案意味着 Fn-1 = 62，这接近但并不正确。

@Karoly Horvath：这不是以101结尾的最长斐波那契类数列。 - n. m.
2
“证明留给读者作为练习”这句话如果你只是猜测的话就不要说，因为[11, 1, 12, 13, 25, 38, 63, 101]比[9, 7, 16, 23, 39, 62, 101]更好。对于那些有足够知识和责任心的人来说，这会带来无尽的头痛。 - oldboy
@oldboy 你说得对，我以为我有证据，但显然它充满了漏洞。 - n. m.
另一方面，这是一个非常好的近似值 - 我测试了从10到1000的所有数字，它从未超过最佳倒数第二个元素的1.5。 - Neil
原来这个公式：F_{n-1} = round(F_n/φ) 是绝对正确的。每个满足 '斐波那契规律' 的序列，即 F_n=F_{n-1}+F_{n-2} 都满足：lim n to infty F_{n+1}/F_n = φ。这是直接从这些序列的生成函数推导出来的。 - xan
或许对于小的数字来说并不是那么简单（我不确定如何证明），但总的来说：这就是任务的作者所想要的，没问题。 - xan
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。解决线性丢番方程。如果它有解，你就完成了。如果没有，将n减1并重试，直到找到解为止。
注意：一定存在一个解，因为 F_2 = 1 * F_1 + 0 * F_0 有解 F_2 = F_1。
（Shahbaz在此帖子发布前21分钟从注释中找到了解决方案-这并不意味着他/她（不要介意面部毛发）是第一个注意到它的人。）如果你能够允许_F_1 < F_0_... - greybeard
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} 和 F{n-2} 计算得出。 这意味着您可以追溯无限数量的数字，因此没有“最长”的序列，且有无限多个有效序列。
在某种程度上，您正在计算具有初始值 F{n} 和 F{n-1} 的逆 Fibonacci 序列，其中 F{i} = F{i+2}-F{i+1}，i 不断减少。
更新： 如果您想将解空间限制为所有 F{i} 都是非负整数的结果，则只会得到少量（大多数情况下是单例）的解。
如果您计算原始的 Fibonacci 数字（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为结尾的序列。简单来说，值n（我们不知道它，我只是为了更好地理解引入它）必须是最高的。 - xan
1
虽然他没有提到，但我确定他正在寻找非负整数。 - Karoly Horvath
是的，所以你从 n 开始“向后”查找，发现没有“最高”的 n，使得序列停止。 - Attila
很容易猜测这将被定义在整数上，因此0 < F(0) <= F(1)。通过添加尽可能长的序列约束，应最小化F(0)和F(1)之间的差异，以满足最终结果。并且F(0)应尽可能小。鉴于所有这些，存在最长的序列（可能不止一个）；而且没有无限多个有效序列。 - DRVic
@DRVic，没错。如果存在多个序列，我们必须选择具有最小F_0的序列。其中F_n是非负整数。 - xan
@所有人 - 我猜到了，但问题的措辞让我的推理成立。请查看更新后的答案以获取额外的限制条件。 - Attila
2
你的方程式
F_n = Fib_n * F_1 + Fib_{n-1} * F_0

这是一个关于两个变量的线性丢番图方程（linear Diophantine equation）F_1和F_0的描述。链接中提供了一种有效的算法来计算解集的描述，从而可以找到一个解（如果存在），使得F_1>=0、F_0>=0且F_0最小。然后，您可以尝试猜测n = 0, 1, ...，直到发现没有解。这种方法在log(F_n)的多项式时间内完成。
奖励：您可以使用 Cassini's identity 来避免实现扩展欧几里得算法。 - oldboy
编程很难，但我认为最好的方法是，至少我最喜欢它。 - xan
0

使用矩阵模拟斐波那契数列的计算（但使用不同的初始值）。将[[0 1] [1 1]]的k次方乘以[F_{n}, F_{n+1}]，将得到[F_{n+k}, F_{n+1+k}]。

由于将矩阵提高到幂是O(log n)（假设整数乘法是O(1)），因此您可以在O(log n)时间内执行整个计算，直到矩阵系数开始支配计算为止。

我不知道您正在处理的数字有多大，但是这个矩阵的第n次幂是[[F_{n-1} F_n] [F_n F_{n+1}]]。而log(F_n) ~ n/5（因此第十亿个斐波那契数将具有大约2亿位数）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接