algorithm - 未交叉序列计算

Question

来自 http://discuss.joelonsoftware.com/default.asp?interview.11.794054.1

序列A定义如下:

从自然数开始1,2,3,...

Initialize count = 1;

    while(there are uncrossed numbers)
    {
        pick the first uncrossed number say n.
      set A[count] = n.
      Cross out the number count+n.
      Cross out the number n
      Increment count.
    }

给出一个快速算法来确定 A[n]，给定 n。

尝试获得一个在 log n 中为多项式的算法。

Answer 1

很抱歉提出这个问题。

显然，这是一个著名的序列，称为 Wythoff 序列，A[n] 有一个简洁的公式，由 A[n] = [n*phi] 给出，其中 [x] = x 的整数部分，phi 是黄金比例.

要计算 [nphi]，我们可以将 phi 近似为连续斐波那契数的比率，给出 O(lognloglogn) 算法。 (O(logn) 时间对 O(log n) 位数进行算术)。