逆斐波那契算法？ [英] The inverse Fibonacci algorithm?

问题描述

有几十计算F（N）的任意n个方法，其中有许多伟大的运行时间和内存使用情况。

There are dozens of ways of computing F(n) for an arbitrary n, many of which have great runtime and memory usage.

不过，假设我想问相反的问题：

However, suppose I wanted to ask the opposite question:

由于F（N）的N> 2，什么是正？

Given F(n) for n > 2, what is n?

（第n> 2的限制是在那里，因为F（1）= F（2）= 1，并没有明确的倒数）。

(The n > 2 restriction is in there since F(1) = F(2) = 1 and there's no unambiguous inverse).

什么是解决这一问题的最有效方法是什么？这很容易通过枚举斐波那契数和停止时，你击中目标数量要做到这一点的线性时间，但有这样做的任何快于某种方式？

What would be the most efficient way of solving this problem? It's easy to do this in linear time by enumerating the Fibonacci numbers and stopping when you hit the target number, but is there some way of doing this any faster than that?

编辑：目前，贴在这里的最佳解决方案为O使用O（log n）的时间（log n）的内存，假设数学运算运行在O（1），并且机器字可以容纳任何数量的O（1）空间。我是否有可能放弃对内存的需求，因为你可以使用O（1）空间计算斐波那契数好奇。

currently, the best solution posted here runs in O(log n) time using O(log n) memory, assuming that mathematical operations run in O(1) and that a machine word can hold any number in O(1) space. I'm curious if it's possible to drop the memory requirements, since you can compute Fibonacci numbers using O(1) space.

推荐答案

由于OP已要求有关矩阵解决方案，不涉及任何浮点运算，在这儿呢。我们可以实现 O（LOGN）的复杂性就这样，假设数字运算有 O（1）的复杂性。

Since OP has asked about matrix solution not involving any floating point computations, here it is. We can achieve O(logn) complexity this way, assuming numeric operations have O(1) complexity.

让我们以2×2矩阵 A 具有以下结构

Let's take 2x2 matrix A having following structure

1 1
1 0

现在考虑向量（8,5），存储两个连续的斐波那契数。如果通过这个矩阵相乘，你会得到（8 * 1 + 5 * 1,8 * 1 + 5 * 0）=（13，8） - 中接下来的Fibonacci数。
如果我们概括， A ^ N *（1,0）=（F（N），F（N - 1））。

Now consider vector (8, 5), storing two consecutive fibonacci numbers. If you multiply it by this matrix, you'll get (8*1 + 5*1, 8*1 + 5*0) = (13, 8) - the next fibonacci number.
If we generalize, A^n * (1, 0) = (f(n), f(n - 1)).

在实际的算法需要两个步骤。

The actual algorithm takes two steps.

1. 计算 A ^ 2 ， A ^ 4 ， A ^ 8 ，等等，直到我们通所需的数字。
2. 请用二进制搜索 N ，使用 A 的计算力量。

1. Calculate A^2, A^4, A^8, etc. until we pass desired number.
2. Do a binary search by n, using calculated powers of A.

在一个侧面说明，表格中的任何序列 F（N）= K * F（N-1）+ K2 * F（N-2）+ K3 * F（N-3） + ... + KT * F（NT）可以psented这样$ P $。

On a side note, any sequence of the form f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t) can be presented like this.

这篇关于逆斐波那契算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！