java - シーケンスの要素値を見つけるためのアルゴリズム

Question

次のシーケンスがあります。

101001000100001..。

シーケンスの要素のインデックスを取得し、この要素の値（0または1）を返すメソッドを定義するにはどうすればよいですか？

public Element getValue(int index) {}

たぶん、再帰を使用する必要がありますか？どんなアイデアでもありがたいです！

Answer 1

小さな点は、このシリーズが続くことを示しています。だからここにあなたの解決策があります：

1ベースのインデックスを考えてみましょう。インデックス1、（1 + 2）= 3、（1 + 2 + 3）= 6、（1 + 2 + 3 + 4）=10などで1が発生することに注意してください。この式があります。その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）ソリューションであるため、再帰の必要はありません（平方根関数の複雑さを考慮していません）

Answer 2

が三角数1の場合に戻ります。8x + 1が正方形である場合に限り、xは三角形です。したがって、8 * index + 9が正方形の場合、インデックス+1は三角形になります。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