根据索引查找金字塔行? [英] Find row of pyramid based on index?

问题描述

给出一个像这样的金字塔

Given a pyramid like:

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

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

and given the index of the pyramid i where i represents the ith number of the pyramid, is there a way to find the index of the row to which the ith element belongs? (e.g. if i = 6,7,8,9, it is in the 3rd row, starting from row 0)

推荐答案

行号和三角形号之间存在联系. 第n个三角数，表示为T _n ，由T _n = n(n-1)/2.第一个三角形对数是0、1、3、6、10、15等，并且，如果您会注意到，每行的起点由第n个三角形给定(它们来自该三角形的事实是这个名字的来源.)

There's a connection between the row numbers and the triangular numbers. The nth triangular number, denoted T_n, is given by T_n = n(n-1)/2. The first couple triangular numbers are 0, 1, 3, 6, 10, 15, etc., and if you'll notice, the starts of each row are given by the nth triangular number (the fact that they come from this triangle is where this name comes from.)

实际上，这里的目标是确定最大的n，以使T _n ≤一世.无需进行任何巧妙的数学运算，您就可以通过仅计算T ₀ ，T ₁ ，T ₂ 来及时解决O(√ n)问题.等等，直到您发现比我还大的东西.更好的是，您可以通过计算T ₁ ，T ₂ ，T ₄ ，T ₈ 等，直到出现超调，然后在找到的范围内进行二进制搜索.

So really, the goal here is to determine the largest n such that T_n ≤ i. Without doing any clever math, you could solve this in time O(√n) by just computing T₀, T₁, T₂, etc. until you find something bigger than i. Even better, you could binary search for it in time O(log n) by computing T₁, T₂, T₄, T₈, etc. until you overshoot, then binary searching on the range you found.

或者，我们可以尝试直接解决此问题.假设我们要找到n的选择，

Alternatively, we could try to solve for this directly. Suppose we want to find the choice of n such that

n(n +1)/2 = i

n(n + 1) / 2 = i

扩展，我们得到

n ² /2 + n/2 = i.

n² / 2 + n / 2 = i.

等效地，

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

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

或者，更容易地:

n ² + n-2i = 0.

n² + n - 2i = 0.

现在我们使用二次公式:

Now we use the quadratic formula:

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

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

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

The negative root we can ignore, so the value of n we want is

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

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

该数字不一定是整数，因此要查找所需的行，我们将四舍五入:

This number won't necessarily be an integer, so to find the row you want, we just round down:

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

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

在代码中:

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

让我们通过测试一下来确认它是否有效. 9到哪里去?好吧，我们有

Let's confirm that this works by testing it out a bit. Where does 9 go? Well, we have

(-1 +√(1 + 72))/2 =(-1 +√ 73)/2 = 3.77

(-1 + √(1 + 72)) / 2 = (-1 + √73) / 2 = 3.77

向下舍入，我们看到它进入第3行-正确！

Rounding down, we see it goes in row 3 - which is correct!

再试一次，55会去哪里?好吧，

Trying another one, where does 55 go? Well,

(-1 +√(1 + 440))/2 =(√ 441-1)/2 = 10

(-1 + √(1 + 440)) / 2 = (√441 - 1) / 2 = 10

因此它应该进入第10行.第十个三角数为T ₁₀ = 55，因此实际上55从该行开始.看起来很有效！

So it should go in row 10. The tenth triangular number is T₁₀ = 55, so in fact, 55 starts off that row. Looks like it works!

这篇关于根据索引查找金字塔行?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！