根据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
是否有已知的简便算法以这种方式分解给定整数?