string - 检查数字中的数字是否可以重新排列以形成斐波那契数

Question

这个问题是在编程竞赛中提出的。除了生成所有排列之外，我找不到任何方法。但是位数最多为 15 并且没有排列（15！）非常大。还有其他方法吗？

我知道如果 (5*N^2 + 4) 或 (5*N^2 - 4) 是一个完美的正方形，则 n 是斐波那契。

标签： stringalgorithmfibonacci

Answer 1

您不需要生成所有排列。生成所需长度的斐波那契数（将小于 74 个数字，因为第 73 个斐波那契数是最高的 15 位数字），然后只需检查那些少数是否可以从给定数字中的数字“构造”。