算法找到序列的元素值

101001000100001 ...

如何确定，是以序列的元素的指数并返回的方法这个元素的值（0或1）？

public Element getValue(int index) {}

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

来源

2013-02-16 Chuck Worker

你如何保存你的序列？如果你知道这一点，那么答案将是相当微不足道的。许多数据结构允许通过索引（数组，列表，字符串）访问 – 2013-02-16 13:49:47

检查“索引+1”是否是三角形数字：http：//en.wikipedia.org/wiki/Triangular_number – Henrik 2013-02-16 13:54:24

小点表示此系列将继续。所以这里是你的解决方案：

让我们考虑基于1的索引。您注意到1出现在索引1处，（1 + 2）= 3，（1 + 2 + 3）= 6，（1 + 2 + 3 + 4）= 10等。我们有一个公式。它的n *（n + 1）/ 2。

所以对于给定的索引（现在这是基于作为Java数组0开始于索引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）溶液（未考虑平方根函数的复杂性）

来源

2013-02-16 14:05:05 pirate

返回1如果index + 1是triangular number。 x是三角形的，当且仅当8x + 1是正方形时。所以索引+1是三角形的，如果8 *索引+9是正方形，则索引+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

来源

2013-02-16 14:56:48 Henrik

算法找到序列的元素值

回答

相关问题