贪心算法用于找到一个数的负斐波那契表示？

Question

贪心算法用于找到一个数的负斐波那契表示？

algorithmmathfibonaccigreedydecomposition

7

根据 Zeckendorf's theorem，每个正整数都可以唯一地表示为非连续不同的斐波那契数之和。这样的分解可以通过贪心算法轻松找到，基本上是减去适合的最大斐波那契数并迭代，例如：

20 = 13 + 7 = 13 + 5 + 2

然而，该定理还意味着任何整数（也包括<=0）都有一个唯一的分解，作为不同的、非连续的负斐波那契数之和，即序列

0, 1, -1, 2, -3, 5, -8, ...

或F_(-n) = (-1)^(n+1) F_n。一些例子：

-4 = - 3 - 1

4 = 5 + 1

11 = 13 - 3 + 1

是否有已知的简单算法来以这种方式分解给定的整数？

- Riccardo Antonelli

参见：n的NegaFibonacci表示法，-n的NegaFibonacci表示法。 - greybeard

糟糕，我在示例中修正了拼写错误。谢谢，我没有注意到OEIS有那几行代码。 - Riccardo Antonelli

这个问题太棒了！解决它非常有趣！ - templatetypedef

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

有一个很好的贪心算法可以用来在 negafibonacci 中表示数字。

该算法的思想是将整数分为由偶斐波那契数对（在正数情况下）和奇斐波那契数对（在负数情况下）界定的区间。具体来说，我们将正数分成以下区间：

- 从 F₀ + 1 到 F₂（包括）， - 从 F₂ + 1 到 F₄（包括）， - 从 F₄ + 1 到 F₆（包括）， - 从 F₆ + 1 到 F₈（包括）， - 从 F₈ + 1 到 F₁₀（包括）， - ... - 从 F_2k + 1 到 F_2k+2（包括）， - ...

同样地，我们将 n 个数字分成以下由负斐波那契数界定的区间：

- 从 -F₁ 到 -F₃ + 1（包括）， - 从 -F₃ 到 -F₅ + 1（包括）， - 从 -F₅ 到 -F₇ + 1（包括）， - 从 -F₇ 到 -F₉ + 1（包括）， - ... - 从 -F_2k-1 到 -F_2k+1 + 1（包括）， - ...

该贪心算法的步骤如下：

- 如果数字是正数，则找到包含 n 的区间 [F_2k + 1, F_2k+2]，将 F_2k+1 添加到表示中，并从 n 中减去 F_2k+1。 - 如果数字是负数，则找到包含 n 的区间 [-F_2k-1, -F_2k+1 + 1]，将 -F_2k 添加到表示中，并将 F_2k 添加到总和中。 - 如果数字是零，则完成。

让我们来举个例子。假设我想将 27 转换为 negafibonacci。我发现 21 + 1 ≤ 27 ≤ 55。这夹在斐波那契数 34（在奇数位置）之间，所以我将 34 添加到总和中，然后尝试将 27 - 34 = -7 转换为 negafibonacci。

接下来，我们注意到5 + 1 ≤ 7 ≤ 13，所以7被夹在包含（偶数索引）斐波那契数8的范围内。因此，我们将-8加入总和并尝试将1转换为负斐波那契数。

现在，我们注意到0 + 1 ≤ 1 ≤ 1，所以1被夹在包含（奇数索引）斐波那契数1的范围内。因此，我们将1加入总和并尝试将0转换为负斐波那契数。

这样总和剩下0，所以我们完成了！嘿！34 - 8 + 1 = 27。

首先让我们证明正确性。首先，请注意，如果我们加入一个正斐波那契数，则它必须是奇斐波那契数（因为我们选择形式为F_2k+1的内容），如果我们加入一个负斐波那契数，则它必须是负偶数斐波那契数（因为我们选择形式为-F_2k的内容）。因此，每个添加的数字都将具有适当的符号。

接下来，我们将证明终止性。首先看看正面的情况。如果我们发现我们有一个数字在[F_2k+1，F_2k+2]范围内，则我们减去F_2k+1。那么数字的上限就是F_2k+2−F_2k+1=F_2k，因此包含剩余部分的最大区间将落在[F_2k-2+1，F_2k]范围内，我们可以提取的最高斐波那契数是F_2k-1。因此，我们无法重复以前删除的斐波那契数，并且正数中提取的数字之间将存在间隙。

数字的下限是F_2k+1−F_2k+1=−F_2k-1+1。这意味着如果数字为负，则包含它的“最高”负区间将是[F_2k-1+1，F_2k-3]，因此我们可以提取的最高负斐波那契数是F_2k-2。因此，我们将提取一个较低阶的斐波那契数。

我们可以进行类似的数学推导，以证明提取负斐波那契数会将窗口向下移动一个步骤。

为了高效实现这个算法，我们可以跟踪三个连续的斐波那契数（F_k-1、F_k、F_k+1），并将其向上或向下移动，直到找到包含数字n的范围。然后我们可以取出可能为负的斐波那契数，并将窗口向0移回，直到完成。总体而言，这将以O(log n)的时间运行。