给定一个正方形网格,有多少个唯一的倾斜正方形和矩形存在于这样的网格上?
例如,
2×2的网格有1个倾斜正方形。
3×3的网格有4个倾斜正方形和4个倾斜矩形,即答案为8。
倾斜的意思是它们只能由网格的顶点形成。
我正在寻找一个通用公式,可以直接计算出现的倾斜正方形和矩形的数量。
例如,
2×2的网格有1个倾斜正方形。
3×3的网格有4个倾斜正方形和4个倾斜矩形,即答案为8。
倾斜的意思是它们只能由网格的顶点形成。
我正在寻找一个通用公式,可以直接计算出现的倾斜正方形和矩形的数量。
row,col
)和左侧顶点位置(leftcol,leftrow
)。我们可以看到左上角段定义了矩形的方向。但是,这个段属于多少个有效的矩形呢?我们可以将该段移动,直到它的端点到达整数点。因此,将行和列差异除以它们的最大公约数(6/4=》3/2
,我不确定这个操作的英语术语是什么 - 约分?),并从水平和垂直位移数字中选择最小值。注意,该线段沿其方向正常移动,因此在最后一行中,y距离被x移位除,反之亦然。function gcd(m, n: integer): integer;
var modulo: integer;
begin
modulo := m mod n;
if modulo = 0 then
Result := n
else
Result := gcd(n, modulo)
end;
function DiagRectsInGrid(n: Integer): Int64;
var
row, col, leftcol, leftrow, dr, dc, dcc, gc, dsx, dsy: Integer;
begin
Result := 0;
for row := 0 to n - 2 do
for col := 1 to n - 1 do
for leftcol := 0 to col - 1 do begin
dc := col - leftcol;
for leftrow := row + 1 to n - 1 do begin
dr := leftrow - row;
gc := gcd(dc, dr); //Greatest common divisor function
dr := dr div gc; //integer division
dcc := dc div gc;
dsx := n - col;
dsy := n - leftrow;
Result := Result + Min(dsx div dr, dsy div dcc);
end;
end;
end;
2 1
3 8
4 30
5 88
6 199
7 408
8 748
9 1280
10 2053
gcd
? - Kiran Saxena嗯,这里是一个方块部分: 一个2x2的单元格只能拥有1个正方形,所以你需要检查2x2可以适合你的NxN网格的次数:
(n - 2 + 1)² = n² - 2n + 1
现在,3x3或4x4的方格可以拥有3-1/4-1个独特的正方形,因此我们将k设置为单个正方形变量:
(k - 1)(n - k + 1)² = ...
sum_{k from 2 to n} (k - 1)(n - k + 1)² = ...
矩形: 同样的逻辑:3x3可以有2个矩形,因此我们需要计算3x3适合您的NxN的次数:
2*(n - 3 + 1)² = 2n² - 8n + 8
现在将3替换为k并求和:
sum_{k from 3 to n} 2*(n - k + 1)² = ...
这有任何意义吗???
顺便问一下,你确定3x3的正方形可以有4个矩形吗?我只能看到其中的2个...