代码之家 › 专栏 › 技术社区 › Aryabhatta

无交叉序列计算

math algorithm

Aryabhatta · 技术社区 · 16 年前

从 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。

尝试获取对数n中的多项式算法。

2 回复 | 直到 16 年前

Aryabhatta 16 年前

很抱歉发布此问题。

显然,这是一个著名的序列,叫做Wythoff序列,有一个简洁的公式,由a[n]=[n*phi]给出,其中[x]=x和phi的整数部分是黄金比率。

计算[ n ] phi),我们可以将phi近似为连续斐波那契数的比值,给出一个o(logn loglogn)算法。(O(log n)对O(log n)位数字进行算术运算的时间)。

Antti Huima 16 年前

这是它的开始

1 2 3 4 5 6 7 8 ... A[1] = 1, cross 2
1 X 3 4 5 6 7 8 ... A[2] = 1, cross 3
1 X X 4 5 6 7 8 ... A[3] = 1, cross 4
...

数字1从不交叉,因为可以交叉的最小数字是1+1==2。

所以有一个常数时间算法:所有n的a[n]=1。

推荐文章

Muhammad Umer · 为什么这个随机数猜谜游戏模拟产生5.8

1 年前

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

Jack Maessen · 当min-val不为0时,如何计算输入type=“range”中点之间的填充颜色

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Jukka · 计算中值

1 年前

D W · Python-将浮点数从2转换为10到100位小数

1 年前

Bartol · 确定python龟图形中的角度

2 年前

randomAlgo · 将弹簧设置为相同长度的成本最低

2 年前

Fyodor · 在C中使用sin和cos计算数学表达式不正确?

2 年前

Sergio · python中大量数字的乘法

2 年前