Wie viele gekippte Quadrate und Rechtecke existieren auf einem quadratischen Gitter? - Algorithmus

Wie viele eindeutige gekippte Quadrate und Rechtecke gibt es bei einem quadratischen Gitter auf einem solchen Gitter?

Beispielsweise,

2 x 2 Raster hat 1 geneigtes Quadrat.

3 x 3 Gitter hat 4 gekippte quadratische und 4 gekippte Rechtecke, d.h. die Antwort ist 8

Gekippt bedeutet, dass sie nur mit Scheitelpunkten des Gitters gebildet werden können.

Ich suche nach einer allgemeinen Formel, die verwendet werden kann, um die Anzahl existierender geneigter Quadrate und Rechtecke direkt zu berechnen.

Antworten:

5 für die Antwort № 1

Lassen Sie uns alle möglichen oberen Eckenpositionen (row, col) und linke Eckpunktposition (leftcol, leftrow).

Wir können sehen, dass oben links Segment definiertAusrichtung von Rechtecken. Aber wie viele gültige Rechtecke gehört dieses Segment? Wir können dieses Segment verschieben, bis seine Enden zu ganzzahligen Punkten kommen. So unterteilen Sie die Unterschiede zwischen Zeilen und Spalten nach ihrem größten gemeinsamen Teiler (6/4=>3/2Ich bin mir nicht sicher in englischer Sprache dafürOperation - Bruch reduzieren?) und wählen Sie Minimum aus horizontalen und vertikalen Verschiebezahlen. Beachten Sie, dass sich das Segment normal zu seiner Richtung verschoben hat, deshalb wird in der letzten Zeile der y-Abstand durch x-shift und umgekehrt geteilt

Delphi-Code und Ergebnisse:

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

Bearbeiten:
Mit dieser Sequenz suchen Sie nach und Bingo: http://oeis.org/A113751
Es gibt keine bekannte Formel für diese Sequenz, BTW.

Bedeutung einiger Variablen:

---

1 für die Antwort № 2

hmm, hier ist ein quadratischer Teil: ein einzelnes 2x2 kann nur 1 Quadrat haben, also müssen Sie überprüfen, wie oft 2x2 Ihr NxN-Gitter passen kann:

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

jetzt können 3x3 oder 4x4 3-1 / 4-1 eindeutige Quadrate haben, also setzen wir k als die einzige quadratische Variable:

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

jetzt müssen wir eine Summe über k von 2 bis N aufbauen:

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

Rechteck: gleiche Logik: 3x3 kann 2 Rechtecke haben, also müssen wir zählen wie oft 3x3 zu deinem NxN passt:

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

Ersetzen Sie nun 3 durch k und bauen Sie eine Summe auf:

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

Macht es irgendeinen Sinn???

übrigens. Bist du sicher, dass 3x3 4 Rechtecke haben kann? Ich kann nur 2 von ihnen sehen ...

---