There is the following sequence:

101001000100001...

How to define a method that takes an element's index of the sequence and returns the value (0 or 1) ​​of this element?

public Element getValue(int index) {}

Maybe there's need to use recursion? I would be grateful for any ideas!

有帮助吗?

解决方案

Little dots indicate that this series will go on. So here is your solution:

Lets consider 1 based index. You notice that 1 occurs at index 1, (1+2)=3, (1+2+3)=6, (1+2+3+4)=10 etc. We have a formula for this. Its n*(n+1)/2 .

So for given index(now this is 0 based as java array begins at index 0) do the following:

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;

Also there is no need for recursion as this is O(1) solution(not considering complexity of square root function)

其他提示

Return 1 if index + 1 is a triangular number. x is triangular, if and only if 8x + 1 is a square. So index + 1 is triangular, if and oly if 8*index+9 is a square.

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

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top