- 我有一個尺寸為
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）。
我的下一步是找到拐角并使用
正如我們所看到的，結果也是正確的，3 3 1 1 2 2 = 12.
但
在這里我問：
我們仍在處理偶數和奇數，因此在將奇數除以 2 后經常會出現舍入錯誤。（例如
M=2, N=4, X=0, Y=0, r=4- 見圖片。有 8 個欄位 - 3 個空白。但 5/2 是 2.5 => 為什么取 3而不是 2？我嘗試添加不同的規則，但它因示例而異。）對于這樣的計算，是否有更有效的演算法，同樣快速且不易出錯？
uj5u.com熱心網友回復：
我們可以計算位于我們網格之外的方格，然后從范圍內的奇數/偶數方格總數中減去這些方格（不管邊界內/外）。
這實際上比我們想象的要容易。首先，我們希望能夠計算范圍內奇數/偶數方格的數量，而不考慮邊界。使用自然數之和的公式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
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/420539.html
標籤：
上一篇：腳本的復雜性