寻找序列元素值的算法

Question

有以下序列：

101001000100001...

如何定义一个函数，接受该序列中某个元素的索引作为参数，并返回该元素的值（0或1）？

public Element getValue(int index) {}

也许需要使用递归吗？我会感激任何想法！

- Chuck Worker

---

你如何存储序列？如果你知道，那么答案就很简单了。许多数据结构都允许通过索引进行访问（数组、列表、字符串）。 - Andreas Dolk

检查index+1是否为三角形数：http://zh.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E5%BD%A2%E6%95%B0 - Henrik

Answer 1

小点表示该系列将继续。因此，这是您的解决方案：

让我们考虑基于1的索引。您会注意到1出现在索引1处，(1+2)=3，(1+2+3)=6，(1+2+3+4)=10等。我们有一个公式用于计算这个和，即n*(n+1)/2。

因此，对于给定的索引（现在这是以0为基础的，因为Java数组从索引0开始），请执行以下操作：

index = index + 1;   // now it is 1 based index and our formula would fit in nicely.
index = index * 2;
sqroot = integer part of square root of index;
if( sqroot * (sqroot+1) == index)
  print 1;
else 
  print 0;

此外，由于这是O(1)的解决方案（不考虑平方根函数的复杂度），因此无需递归。

- pirate

Answer 2

如果 index + 1 是一个三角形数，则返回1。当且仅当8x+1是一个完全平方数时，x是三角形数。因此，当且仅当8*index+9是一个完全平方数时，index + 1是三角形数。

public int getValue(int index) {
    int i = (int)Math.round( Math.sqrt(8*index + 9));
    if (i*i == 8*index+9)
        return 1;
    else
        return 0;
}

http://ideone.com/8L9A96

- Henrik