寻找数字的negafibonacci表示的贪婪算法？

Question

根据Zeckendorf定理，每个正整数都可以以唯一的方式写为非连续的不同斐波那契数之和。可以使用贪婪算法轻松找到这种分解，该算法主要包括减去适合并迭代的最大斐波那契数，例如：

20 = 13 + 7 = 13 + 5 + 2

但是，该定理还暗示，任何整数（也<= 0）作为唯一的，非连续的negaFibonacci数之和具有唯一分解，即序列

0、1，-1、2，-3、5，-8，...

或F _（-n）=（-1）^（n + 1）F_n。一些例子：

-4 = - 3 - 1

4 = 5 + 1

11 = 13 - 3 + 1

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

Answer 1

有一个很好的贪心算法可以用来表示负斐波那契数。

该算法背后的思想是将整数分割成由偶数斐波那契数对（在正数情况下）和奇数斐波那契数对（在负数情况下）界定的范围。具体来说，我们将把正数分成范围

• 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 转换为负斐波那契数。我发现 21 + 1 ≤ 27 ≤ 55。这将（奇数索引）斐波那契数 34 夹在中间，因此我将 34 添加到总数中，然后尝试将 27 - 34 = -7 转换为负斐波那契数。

接下来，我们注意到 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) 时间内运行。