algorithm - 斐波那契算法查找数字(或近邻)是否是 2 个斐波那契数之间的差异

Question

我希望有人能帮助我。给定一个数字 n(不一定是斐波那契数)，我必须找出该数字是否等于两个斐波那契数之间的差值，如果不相等，我必须返回最接近 n 的数字，我们称它为 m(这是不一定是斐波那契数)，这是两个斐波那契数之间的差异。

我不是在寻找确切的算法实现，而是在寻找一些可以查看的指针。

Answer 1

不失一般性地假设n > 0 .自 1 = 1 - 0 = fib(1) - fib(0) , 结果 m也是积极的。让0 ≤ i < j并考虑 fib(j) - fib(i) .我们有界限

fib(j-2) = fib(j) - fib(j-1) ≤ fib(j) - fib(i) ≤ fib(j).

因此，对于每个 n , 只有 fib(j-2) ≤ n ≤ fib(j) 的可能性需要考虑。事实上，我们可以将其收紧到 fib(j-2) < n ≤ fib(j) , 因为我们也可以写 fib(j) - fib(j-1)作为fib(j-2) - fib(0) .计算对数/使用二进制搜索来查找 j 的两个有效设置.对于 j 的每个设置, 找到 i 的最佳值同理。