在一个正方形网格上有多少个倾斜的正方形和矩形？

Question

给定一个正方形网格，有多少个唯一的倾斜正方形和矩形存在于这样的网格上？

例如，

2×2的网格有1个倾斜正方形。

3×3的网格有4个倾斜正方形和4个倾斜矩形，即答案为8。

倾斜的意思是它们只能由网格的顶点形成。

我正在寻找一个通用公式，可以直接计算出现的倾斜正方形和矩形的数量。

- Kiran Saxena

---

迭代网格并计数？顺便问一下，“quare”是什么？ - Tim Biegeleisen

什么是倾斜的正方形？你有正式的定义吗？ - Ivaylo Strandjev

问题不清楚，请您提供更好的测试案例。同时，您能否分享一下您尝试过的方法？ - marvel308

为什么2×2的方格中只有一个“倾斜”的正方形，而3×3的方格中却有4个呢？看起来好像可以有无限多个独特的正方形...顺便问一下，在这种情况下，“unique”是什么意思？ - JohnnyAW

你的意思不是六个带标题的正方形和两个三角形吗？你的第二张图片是一个正方形（4个小正方形像3D图像，2个正方形像第二张图片，还有两个矩形像第一张图片）。 - Treziac

Answer 1

让我们遍历所有可能的顶点位置（row，col）和左侧顶点位置（leftcol，leftrow）。我们可以看到左上角段定义了矩形的方向。但是，这个段属于多少个有效的矩形呢？我们可以将该段移动，直到它的端点到达整数点。因此，将行和列差异除以它们的最大公约数（6/4=》3/2，我不确定这个操作的英语术语是什么 - 约分？），并从水平和垂直位移数字中选择最小值。注意，该线段沿其方向正常移动，因此在最后一行中，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

编辑：
有了这个序列，搜索它并且 bingo：http://oeis.org/A113751
顺便提一下，这个序列目前没有已知的公式。
一些变量的含义：

- MBo

---

哦，哇！但是如果没有公式，我们如何在编程中实现它呢？ - Kiran Saxena

@KiranSaxena 他已经为您实现了它，答案中有代码。 - JohnnyAW

什么是 gcd？ - Kiran Saxena

gcd - 最大公约数函数。我已经添加了它的代码。 - MBo

Answer 2

嗯，这里是一个方块部分： 一个2x2的单元格只能拥有1个正方形，所以你需要检查2x2可以适合你的NxN网格的次数：

(n - 2 + 1)² = n² - 2n + 1

现在，3x3或4x4的方格可以拥有3-1/4-1个独特的正方形，因此我们将k设置为单个正方形变量：

(k - 1)(n - k + 1)² = ...

现在我们需要从2到N构建一个k的总和：

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个...

- JohnnyAW

---

你是对的，3x3 - 4个小正方形，2个大正方形，2个细长矩形。 - MBo