3

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

我们得到一个数字 x，我们将它平方，所以数字变成 x^2。现在我们有从 1 到 x^2 的数字，例如： if number=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（上一个总和），将计数增加到 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 指的是什么）

4

5 回答 5

5

矩形的上半部分是一个三角形：

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

右边的数字（1、3、6、10）称为三角数。那里的逆公式（在副标题“三角根和三角数测试”下）可用于解决您的问题：

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)
于 2013-02-05T10:07:18.277 回答
4

上半场，小组i以数字结束i*(i+1)/2。所以让我们假设给你一个数字n，n <= x^2/2你需要找到最小i的i*(i+1)/2 <= n。

求解产量 ：i*i+i-2n = 0例如：i((sqrt(1+8n)-1/2)n = 8i = ceil((sqrt(65)-1)/2) = 4

当然，情况n > x^2/2稍微复杂一些。

于 2013-02-05T10:02:43.257 回答
3

首先为简单起见假设x <= n^2 / 2和x属于组t。然后：

t*(t-1)/2 < x <= t*(t+1)/2

从这里我们得到两个二次不等式：

t^2 - t - 2x < 0
t^2 + t - 2x >= 0

在这里D=1+8x，因为 t > 0 他们的共同解决方案将是

t ∈ [ (-1-sqrt(D))/2; (1+sqrt(D))/2 )

现在记住 t 是一个整数（并且根据定义是唯一的），所以我们将得到解决方案：

t = floor( 1+sqrt(D))/2 )

这是 case x <= n^2 / 2的解决方案。在其他情况下，我们可以通过执行以下操作来解决它：

  1. x := n^2 - x + 1
  2. 如上所述找到 t
  3. t := n - t + 1

希望这可以帮助。

于 2013-02-05T10:07:54.127 回答
2

右上角对角线上的数字是所谓的“三角形数字”，它们有公式n(n+1)/2。

右下角的数字等于 16 减去一个三角形数，它们有公式x^2 - (2*x-n-1)(2*x-n)/2。

因此，给定kand x，您正在寻找n公式大于或等于 的k最小值，根据是否k大于或小于x第 th 个三角形数x(x+1)/2（在本例中为 10）选择哪个公式。由于这两个函数都是单调的（总是增加），您可以通过求解n浮点的二次方程（使用二次公式）然后四舍五入到下一个整数（所谓的“上限”）来做到这一点。

为了在不引入太多复杂性的情况下解决浮点不准确性，您应该使用整数算术检查结果。浮点计算可能会略微超出或低于正确结果，并舍入到错误的整数值。对于小数字，在最坏的情况下它不会超过 1，因此检测和纠正它的代码很简单，只需与k通过将n结果放入公式中得到的值和n任一侧的值进行比较即可。

于 2013-02-05T10:11:29.940 回答
1

首先，您需要观察该xth行恰好是中间行并且其中有 x 个元素。那么这个特定行中的元素是什么 - 它们来自[x(x+1)/2-x, x(x+1)/2]. 所以算法是这样的：

  1. 检查要搜索的数字是否在中间行，小于或大于该数。
  2. 如果在中间行打印 x。
  3. 如果小于中间行，那么您需要观察所有行都以三角形数字结尾。您可以使用公式ceil((sqrt(8x+1)-1)/2)来获取确切的行。

  4. 否则，如果数字大于中间行，那么您可以将下三角形视为：

    6 5 4

    3 2

    1

也就是说，所有数字都等于x^2+1-that number。x^2+1-number to be searched因此，现在您将使用上述公式本身在下三角形中搜索。这以倒置的形式给出了行号。让那个数字变成k。那么正确形式的值为x-1+k+1。最后添加x到值以将答案转移到下三角形。因此答案变为2x+k。

这是该问题的 O(1) 解决方案。

于 2013-02-05T10:25:24.113 回答