0
  • 我有一个尺寸为Mx的图表N。
  • 我也有两点 [ X, Y]
  • 和范围r

我们只能水平或垂直移动 1 个空格（我们总是必须移动）。我们的目标是找到我们可以达到的可能性总数。

在这个例子中，我们有M=5, N=4, [ X=2, Y=1] 和r=3。

在此处输入图像描述

我们可以看到，这r是一个奇数，所以我们正在寻找奇数。结果显然是（将所有奇数相加后）12

我首先尝试了蛮力，但它太慢了（O(n^2)）。

所以我在数学上尝试了更多。我尝试了冯诺依曼邻域算法，但我完全被困在那里。最后，我通过计算对应于xand的行中的垂直和水平计数来尝试它y（count in xis 3, count in yis 3）。

在此处输入图像描述

我的下一步是找到拐角并使用出租车几何r计算到达那里需要多少s。

然后我将图像分成 4 个部分（象限）。当从[X, Y]给定象限的角点的路径小于r时，只需将正方形的数量除以 2。当路径较大时，我创建r_，这由路径到角点与r →的差异决定r_ = taxicab - r。然后只需从矩形的内容中减去r_并再次除以 2。

在此处输入图像描述

正如我们所看到的，结果也是正确的，3 + 3 + 1 + 1 + 2 + 2 = 12.

但

在这里我问：

在此处输入图像描述

  1. 我们仍在使用偶数和奇数，因此在将奇数除以 2 后经常会出现舍入错误。（例如M=2, N=4, X=0, Y=0, r=4- 见图片。有 8 个字段 - 3 个空白。但 5/2 是 2.5 => 为什么取 3而不是 2？我尝试添加不同的规则，但它因示例而异。）

  2. 对于这样的计算，是否有更有效的算法，同样快速且不易出错？

4

1 回答 1

1

我们可以计算位于我们网格之外的方格，然后从范围内的奇数/偶数方格总数中减去这些方格（不管边界内/外）。

这实际上比我们想象的要容易。首先，我们希望能够计算范围内奇数/偶数方格的数量，而不考虑边界。使用自然数之和的公式N-S = N * (N + 1) / 2我们可以为此推导出几个简单的方程：

def count_all(size):
    if size % 2:  # odd size
        return (size + 1) ** 2
    return size * (size + 2) + 1

尝试自己推导这些可能是一个很好的练习，或者至少用一些例子来验证它们实际上是正确的。

继续前进——我们可以通过“缩小”我们的半径来消除从上方超出边界的点。这是非常直观的，所以让我给你一个图表。只想象范围是某个固定数字的点，例如range=13，而我们的中心位于右下象限，例如(17, 5)。如果我们绘制这些点，用线将它们连接起来，它会创建一个菱形：

 |    /\
 |   /  \
 |  /    \
-+-----------
 | /      \
 | \      /
 |  \    /
 |   \  /
 |    \/

如果我们只关心计算轴上方的点，我们可以等效地只计算相应向上移动的较小钻石的轴上方的点。例子：

 |    /\
 |   /  \
 |  /    \
-+-----------
 |  \    /
 |   \  /
 |    \/

现在，使用起来非常方便，因为钻石的一半在上面，一半在下面。尽管我们做了一半要小心——有些点落在轴上，两者都需要同等地考虑在界内或界外，但我们可以很容易地解释这一点。

使用这种洞察力，我们可以通过缩小范围和移动中心点来计算跨轴超出范围的点数，并在这个新图的一半上计算点数。计数代码：

def count_side(size):
    if size % 2:
        return (size + 1) // 2
    return size // 2 + 1

def count_half(size):
    if size < 0:
        return 0
    return count_all(size) // 2 + count_side(size)

请注意，我们必须注意偶数范围，因为我们需要只计算中心（范围 0）一次。

我们还没有完成——如果我们只是减去超出边界的点数，然后独立地向左移动，我们就会多算要删除的点数，因为我们计算的是左上角的点象限两次。为了解决这个问题，我们使用相同的技巧。我们将首先在 x 轴上缩小 + 移动钻石，然后我们将在这个新钻石上再次执行此操作，但在 y 轴上。请注意，这颗新钻石最终将以原点为中心。我建议您在这一点上暂停片刻以想象这一点并说服自己这很好，实际上会为我们提供任何特定范围的新菱形，包含 4 倍落在左上角的点数象限。

使用它，我们计算左上象限中的点数，将它们重新添加到总数中。然后我们对右侧、底部和其他三个角重复相同的过程，以获得总体总数。整个解决方案如下：

from itertools import product


def count_all(size):
    if size % 2:
        return (size + 1) ** 2
    return size * (size + 2) + 1

def count_side(size):
    if size % 2:
        return (size + 1) // 2
    return size // 2 + 1

def count_half(size):
    if size < 0:
        return 0
    return count_all(size) // 2 + count_side(size)

def count_quarter(size):
    if size < 0:
        return 0
    return count_all(size) // 4 + count_side(size)

def get_deltas(pos, limit):
    return -(pos + 1), pos - (limit + 1)

def count_inside(c, r, x, y, s):
    total = count_all(s)

    vertical_deltas   = get_deltas(x, c)
    horizontal_deltas = get_deltas(y, r)

    out_sides = sum(count_half(s + delta) 
        for delta in horizontal_deltas + vertical_deltas)

    out_corners = sum(count_quarter(s + delta_vert + delta_horiz)
        for delta_vert, delta_horiz in product(vertical_deltas, horizontal_deltas))
    
    inside = total - out_sides + out_corners
    return inside

几个例子：

>>> print(count_inside(5, 4, 2, 1, 3))
12
>>> print(count_inside(5, 4, 2, 1, 4))
14
>>> print(count_inside(5, 4, 2, 1, 5))
15
>>> print(count_inside(10, 6, 3, 2, 8))
36
于 2022-01-21T21:38:35.720 回答