有以下序列:
101001000100001...
如何定义一个函数,接受该序列中某个元素的索引作为参数,并返回该元素的值(0或1)?
public Element getValue(int index) {}
也许需要使用递归吗?我会感激任何想法!
小点表示该系列将继续。因此,这是您的解决方案:
让我们考虑基于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)的解决方案(不考虑平方根函数的复杂度),因此无需递归。
如果 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;
}
index+1
是否为三角形数:http://zh.wikipedia.org/wiki/%E4%B8%89%E8%A7%92%E5%BD%A2%E6%95%B0 - Henrik