根据Zeckendorf's theorem，每一个正整数都可以作为非连续的不同fibonacci数之和以唯一的方式写入。贪心算法可以很容易地找到这样的分解，贪心算法主要是减去适合的最大fibonacci数并进行迭代，例如：20 = 13 + 7 = 13 + 5 + 2
然而，这个定理也意味着任何整数（也0，1，-1，2，-3，5，-8，…
或f（-n）=（-1）^（n+1）f_n。一些示例：-4 = - 3 - 14 = 5 + 111 = 13 - 3 + 1
有没有一种已知的简单算法可以用这种方法分解给定的整数？
最佳答案
在negafibonacci中有一个很好的贪婪算法可以用来表示数字。
该算法的思想是将整数分割成由偶数fibonacci数（在正数情况下）和奇数fibonacci数（在负数情况下）对分隔的范围。具体来说，我们将正数分成范围
f0+1至f2，包括，
2+1至4层，包括，
F4+1至F6，包括，
F6+1到F8，包括，
F8+1至F10（含）
…
f2k+1到f2k+2，包括，
…
我们同样将n个数分成这些范围，这些范围由负fibonacci数划分：
-F1到-F3+1，包括，
-F3至-F5+1，含，
-F5至-F7+1，含，
-七层到九层加一层，
…
-f2k-1至-f2k+1+1，包括，
…
贪心算法然后进行如下操作：
如果数字是正的，找到包含n的范围[f2k+1，f2k+2]，将f2k+1加到表示中，然后从n减去f2k+1。
如果数字为负，则找到包含n的范围[-f2k-1，-f2k+1+1]，将-f2k添加到表示中，并将f2k添加到总数中。
如果数字是零，你就完了。
举个例子。假设我想把27转换成negafibonacci。我发现21+1≤27≤55。这个三明治是（奇数索引）斐波那契数34，所以我加上34，然后尝试将27-34=-7转换成negafibonacci。
接下来，我们注意到5+1≤7≤13，所以7被夹在包含（偶数索引）fibonacci数8的范围内。因此，我们将-8加到总数中，并尝试将1转换为negafibonacci。
现在，我们注意到0+1≤1≤1，所以1被夹在一个包含（奇数索引）fibonacci数1的范围内。因此，我们将1添加到总数中，并尝试将0转换为negafibonacci。
总共剩下0个，所以我们结束了！嘿！34-8+1=27。
让我们先论证一下正确性。首先，注意如果我们加上一个正的fibonacci数，它必须是奇数的fibonacci数（因为我们选择了形式f2k+1），如果我们加上一个负的fibonacci数，它必须是一个负偶数的fibonacci数（因为我们选择了形式f2k）。所以每个加进去的数字都有正确的符号。
下一步，我们将证明终止协议。先看阳性病例。如果我们发现有一个数在[f2k+1，f2k+2]范围内，那么我们减去f2k+1。这个数的上界是f2k+2-f2k+1=f2k，所以包含余数的最大区间将落在[f2k-2+1，f2k]范围内，我们可以得出的最高fibonacci数是f2k-1。因此，我们不能重复之前删除的斐波那契数，并且在取出的正数之间会有一个间隙。
数字的下界是f2k+1-f2k+1=-f2k-1+1。这意味着如果这个数是负的，包含它的“最高”负区间应该是[f2k-1+1，f2k-3]，所以我们可以得出的最高负fibonacci数是f2k-2。因此，我们将得到一个低阶fibonacci数。
我们可以做类似的数学运算来证明，拉出一个负的fibonacci数会使我们的窗口向下移动一步。
为了有效地实现这一点，我们可以跟踪三个连续的fibonacci数（fk-1，fk，fk+1），并不断地向上（或向下）移动，直到找到包含数字n的范围。然后我们可以拉出我们的（可能是负的）fibonacci数，然后将窗口移回0，直到完成。总的来说，这将在时间o（log n）内运行。