算法找到序列的元素值

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

算法找到序列的元素值

回答

相關問題