如何在金字塔排名系统中获得挑战者

Question

所以我得到了一个基本上是金字塔的排名系统:

     01
    02 03
   04 05 06
  07 08 09 10
 11 12 13 14 15
16 17 18 19 20 21

现在每个人都可以挑战上面一行中同一行和右边的左边每个人.

所以例如18可以挑战13-17
基本上你可以进一步挑战你越低的阶梯.

关于如何解决这个功能的任何想法？在考虑这个问题时,我只是通过倒数来计算金字塔的层数,从而得出一些非常复杂的范围计算,但我确信必须有一个简单的解决方案.

更多范围的例子:
02 - 01
03 - 02
04 - 02-03
05 - 03-04
06 - 04-05
07 - 04-06
08 - 05-07
11 - 07-10
17 - 12-16

顺便说一下,即使它看起来像家庭作业,我可以向你保证,我已经失学多年了.这实际上是进入射箭梯系统,我正在尝试为当地射箭俱乐部数字化:)

Answer 1

对于玩家x来说,很容易看出范围中的上限值总是如此x - 1.棘手的部分是找到较低的值.

首先请注意,您可以挑战的人数等于您上方行中的人数.您可以通过查看下图来更容易理解为什么这是真的,其中每个椭圆包含玩家13可以挑战的人中的一个(9,10,11,12):

有13个人可以挑战,有4个人排在第13位.

所以我们需要找到x以上行中的人数.请注意,x之上的总人数是某些人的三角数 .而值是x以上行中的人数.T(n)nn

要查找三角形数字,您可能会发现此公式很有用:

T(n) = n * (n+1) / 2

问题是要找到最大的n那样的T(n) < x.

您可以使用循环来遍历所有可能的值n,计算T(n)直到超过它x.这样做很简单,而且几乎可以肯定它足够快.

但是你也可以通过使用上述二次方程的逆函数直接到达那里:

所需要的唯一调整是先减去1从x因为我们希望三角形数量比严格更小x.如果没有这种调整,它将为当前行提供精确的三角形数字,而不是上面的行.

使用此公式并将其转换为PHP,我们可以直接获得结果x:

$n = floor((sqrt(1 + 8 * ($x - 1)) - 1) / 2);
$lower = $x - $n;
$upper = $x - 1;

结果:

2: 1 - 1
3: 2 - 2
4: 2 - 3
5: 3 - 4
6: 4 - 5
7: 4 - 6
8: 5 - 7
9: 6 - 8
10: 7 - 9
11: 7 - 10
12: 8 - 11
13: 9 - 12
14: 10 - 13
15: 11 - 14
16: 11 - 15
17: 12 - 16
18: 13 - 17
19: 14 - 18
20: 15 - 19
21: 16 - 20

看到它在线工作:ideone