math - 根据索引查找金字塔行？

Question

给定一个金字塔，如:

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

并给出金字塔的索引 i哪里i代表i金字塔的第 th 个数字，有没有办法找到 i 所在行的索引第一个元素属于？ (例如，如果 i = 6,7,8,9 ，它在第 3 行，从第 0 行开始)

Answer 1

行号和三角号之间存在联系。 nth triangular number ，表示为 Tn，由 Tn = n(n-1)/2 给出。前几个三角形数是 0, 1, 3, 6, 10, 15, 等等，如果你注意到的话，每一行的开始都是由第 n 个三角形数给出的(它们来自这个三角形的事实是这个名字的由来。)

所以实际上，这里的目标是确定最大的 n 使得 Tn ≤ i。无需做任何巧妙的数学运算，您只需计算 T0、T1、T2 等，就可以在 O(√n) 时间内解决这个问题，直到找到比 i 大的东西。更好的是，您可以通过计算 T1、T2、T4、T8 等，在 O(log n) 时间对它进行二分搜索，直到您超调，然后在您找到的范围内进行二分搜索。

或者，我们可以尝试直接解决这个问题。假设我们想要找到 n 的选择使得

n(n + 1) / 2 = i

展开，我们得到

n² / 2 + n / 2 = i.

同样，

n² / 2 + n / 2 - i = 0,

或者，更容易:

n² + n - 2i = 0.

现在我们使用二次公式:

n = (-1 ± √(1 + 8i)) / 2

我们可以忽略的负根，所以我们想要的 n 的值是

n = (-1 + √(1 + 8i)) / 2.

这个数字不一定是整数，所以要找到你想要的行，我们只需四舍五入:

row = ⌊(-1 + √(1 + 8i)) / 2⌋.

在代码中:

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 行。第十个三角形数是 T10 = 55，所以实际上，55 从该行开始。看起来它有效!