一个正方形网格上有多少个倾斜的正方形和矩形？
给定一个正方形网格，这样的网格上有多少个独特的倾斜正方形和矩形？
例如,
2 x 2网格有1个倾斜的正方形。
3 x 3网格有4个倾斜正方形和4个倾斜矩形，即答案是8
倾斜表示它们只能使用栅格的顶点来形成。
我正在寻找一个通用的公式，可以用来直接计算现有的倾斜正方形和矩形的数量。
回答 2
Stack Overflow用户
发布于 2017-08-11 21:34:24
让我们遍历所有可能的顶部顶点位置(row, col)和左侧顶点位置(leftcol, leftrow)。
我们可以看到左上角的部分定义了矩形的方向。但是这个片段属于多少有效的矩形呢？我们可以移动这个线段，直到它的末端达到整数点。因此，将行和列的差除以它们最大的公约数(6/4=>3/2，我不确定这个操作的英文术语-- reduce fraction?)并从水平和垂直移位数中选择最小值。请注意，线段垂直于其方向移动，这就是为什么在最后一行中，y距离除以x移位，反之亦然
Delphi代码和结果：
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编辑：
有了这个序列，搜索它就可以了：http://oeis.org/A113751
对于这个序列，BTW没有已知的公式。
一些变量的含义：
Stack Overflow用户
发布于 2017-08-11 20:13:40
嗯，这是一个正方形的部分:单个2x2只能有一个正方形，所以你需要检查，2x2可以适合你的NxN网格的次数：
(n - 2 + 1)² = n² - 2n + 1现在，3x3或4x4可以有3-1 / 4-1个唯一的方块，因此我们将k设置为单个方块变量：
(k - 1)(n - k + 1)² = ...现在我们需要在k上建立一个从2到N的和：
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个矩形吗？我只能看到其中的两个...
https://stackoverflow.com/questions/45633541
复制相似问题
腾讯云开发者
