algorithm - 找出一个号码属于哪个组？

Question

我正在处理一个编码问题，作为它的一部分，我遇到了这个问题:

我们得到一个数字 x，我们将它平方，所以数字变成 x^2。现在我们有从 1 到 x^2 的数字，例如:如果数字=4；然后4^2=16

         1             ----->1
      2     3          ----->2
   4     5     6       ----->3
7     8     9    10    ----->4
  11    12    13       ----->5
     14    15          ----->6
        16             ----->7

现在我得到一个数字 k，我需要告诉它它属于哪个组。这里 8 属于第 4 组。

我想到的是从1开始，保持计数初始化为1，然后检查是否1<8？如果是则将 2 加到 1(prev sum)，将计数增加到 2 并检查 3<8？如果是，则将 3 加到 3(上一个总和)，将计数增加到 3，并检查是否 6<8 如果是，则将 4 加到 6，将计数增加到 4，并检查是否 10<9？如果没有则退出。所以组号是数，即 4。

但是有没有比我的方法更快的方法呢？

编辑 1:我忘了在我的算法中提到，当计数达到给定数字(在上一个示例中为 4)时，我不应该加 5，而是加 3。例如:

如果要搜索的数字是 14 那么

1<14 yes then add 2

3<14 yes then add 3

6<14 yes then add 4

10<14 yes then add **3**  ---->here I need to add 3 instead of 5

13<14 yes then add **2**  ---->here I need to add 2 instead of 6

15<14 No so output count.

可以使用 if 条件添加 3 而不是 5，但是是否有任何方法可以根据 x 的值自动增加然后减少值(参见上面的示例以了解 x 指的是什么)

Answer 1

矩形的上半部分是三角形:

         1             ----->1
      2     3          ----->2
   4     5     6       ----->3
7     8     9    10    ----->4

右边的数字(1、3、6、10)叫做triangular numbers .那里的反公式(在副标题“三角根和三角数的检验”下)可用于您的问题:

def group(x, number):
    if number <= x^2 / 2 :
        return ceiling( (sqrt(8*number+1) - 1) / 2 )
    else:
        return 2*x - group(x, x^2+1-number)