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

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