基於索引查找金字塔的行？

Question

鑑於像一個金字塔：

 0 
    1 2 
    3 4 5 
    6 7 8 9 
    ... 

並給出了金字塔i其中i代表金字塔的i日數的指標，有沒有辦法找到該行該i個元素的索引屬於？ （例如，如果i = 6,7,8,9，它是第三行中，從第0行開始）

Answer 1

行號和三角形數之間存在連接。表示爲T _n，由T _n = n（n-1）/ 2給出。第一對三角形數字是0,1,3,6,10,15等，如果你會注意到，每一行的開始都是由第n個三角形數字給出的（它們來自這個三角形的事實是）

所以真的，這裏的目標是確定最大的n使得T _n ≤ i。沒有做任何聰明的數學，你可以通過計算T ，T ，T 等，直到你找到比我大的東西。更好的是，你可以爲它在時間O（log n）的通過對範圍計算Ť，T ，T ，T ，等等，直到你超調，然後二進制搜索二進制搜索你發現了。

或者，我們可以嘗試直接解決此問題。假設我們想找到n的選擇使得

N（N + 1）/ 2 =我

擴大，我們得到

ň/2 + n/2 = i。

等效地，

Ñ/2 + N/2 - I = 0，

，或者更容易：

Ñ + n - 2i = 0。

現在我們使用二次公式：

N =（-1 ± √（1 + 8I））/ 2

負根我們可以忽略，因此該值的n個我們要的是

N =（-1 + √（1 + 8I））/ 2。

這個數字不一定是一個整數，所以找到你想要的行，我們只是向下取整：

行= lfloor;（ - 1 + √（1 + 8I））/ 2 rfloor ;.

在代碼：

int row = int((-1 + sqrt(1 + 8 * i))/2); 

讓我們確認這是通過測試出來一點。 9去哪裏？那麼，我們有

（-1 + √（1 + 72））/ 2 =（ - 1 + 73 √）/ 2 = 3.77

向下取整，我們看到它進入在排3 - 這是正確的！

嘗試另一個，55去哪裏？那麼，

（-1 + √（1 + 440））/ 2 =（441 √ - 1）/ 2 = 10

所以應該進去行10.第十三角形數是T = 55，所以實際上，55從那一行開始。看起來像它的作品！

Answer 2

我認爲i個元素屬於n第i行，其中n是n(n+1)/2 <= i < (n+1)(n+2)/2

例如號碼，如果i = 6，然後n = 3因爲n(n+1)/2 <= 6 並且如果i = 8，則n = 3，因爲n(n+1)/2 <= 8

Answer 3

我得到行= math.floor（√（2I + 0.25） - 0.5）其中，i是你的電話號碼

基本上與上述相同的人，但我降低Ñ + n至第（n + 0.5） - 0.25