查找序列元素值的算法

Question

有以下顺序:

101001000100001 ...

如何定义一个方法,该方法接受序列的元素索引并返回该元素的值(0或1)？

public Element getValue(int index) {}

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

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) 解决方案（不考虑平方根函数的复杂性）