正方形網格上存在多少個傾斜正方形和矩形？

Question

給定一個正方形網格，這樣的網格上存在多少個獨特的傾斜正方形和矩形？

例如，

2 x 2網格有1個傾斜的正方形。

3×3格已經4傾斜正方形和4米傾斜的矩形即答案是8

斜意味着它們可以僅使用網格的頂點而形成。

我尋找可用於直接計算現有傾斜正方形和長方形的數量的通式。

Answer 1

嗯，這裏是一個方形部分： 一個2x2的只能有1平方，所以你需要檢查，多少次的2x2可滿足您的N×N個網格：

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

現在，3×3或4×4可以具有3-1/4-1獨特正方形，所以我們設置K作爲單個正方形變量：

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

現在我們需要從2建立用K的總和爲N：

sum_{k from 2 to n} (k - 1)(n - k + 1)² = ... 

矩形： 相同的邏輯：3x3的可以有2個矩形，所以我們要算的3x3多少次適合您的N×N：

2*(n - 3 + 1)² = 2n² - 8n + 8 

現在用k代替3，建設和：

sum_{k from 3 to n} 2*(n - k + 1)² = ... 

它有什麼意義？

btw。你確定3x3可以有4個矩形嗎？我只能看到其中的兩個...

Answer 2

讓我們遍歷所有可能的頂點頂點位置（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 

編輯：
有這個序列，搜索它和賓果：http://oeis.org/A113751
這個序列沒有已知的公式，BTW。

一些變量的含義：