algorithm - 如何有效地将整数转换为斐波那契编码？

Question

斐波那契数列是从 0 和 1 开始，然后将最后两个数字相加得到下一个。

所有正整数都可以表示为一组不重复的斐波那契数之和。例如:13 可以是集合 {13}、{5,8} 或 {2,3,8} 的总和。但是，正如我们所见，有些数字有不止一组，其总和就是数字。如果我们添加集合不能有两个连续的斐波那契数的约束，那么每个数都有一个唯一的表示。

我们将使用一个二进制序列(只有零和一个)来做到这一点。例如，17 = 1 + 3 + 13。那么，17 = 100101。详细解释见图2。

我想把一些整数变成这个表示，但是整数可能非常大。如何有效地执行此操作。

Answer 1

问题本身很简单。您总是选择小于余数的最大斐波那契数。您可以忽略连续数字的约束(因为如果您需要两者，下一个是两者的总和，所以您应该选择那个而不是最初的两个)。

所以问题仍然是如何快速找到小于某个数 X 的最大斐波那契数。有一个已知的技巧，从矩阵开始(称之为 M)

1 1
1 0

您可以通过矩阵乘法计算斐波那契数(第 x 个数是 M^x)。更多详情:https://www.nayuki.io/page/fast-fibonacci-algorithms .最终结果是您可以计算出您在 O(logN) 矩阵乘法中查找的数字。

如果它们不适合现有类型，您将需要进行大量计算(乘法和加法)。还要存储与您第一次计算的 2 的幂对应的矩阵，因为您将再次需要它们来获取结果。

总的来说这应该是 O((logN)^2 * large_number_multiplications/additions)。