Als Reaktion auf diese Herausforderung möchten wir nun die Anzahl der Rechtecke im Raster mit r Zeilen und c Spalten zählen, wobei sich eine Linie durch jede Diagonale eines Quadrats im Raster kreuzt. Jetzt zählen wir immer noch die gleichen Rechtecke wie zuvor, aber dieses Mal müssen wir auch Rechtecke einbeziehen, die um 45 Grad geneigt sind.
Ihr Ziel ist es, eine Funktion oder ein Programm zu erstellen, die bzw. das bei gegebener Anzahl von Zeilen r und Spalten c die Anzahl von Rechtecken in einem diagonalen Raster mit den Abmessungen ( r , c ) ausgibt .
Als Demonstration ist dies eine Animation, die alle 37 Rechtecke durchläuft, die durch ein (2 x 3) Diagonalgitter gebildet werden.
Testfälle
Each case is [rows, columns] = # of rectangles
[0, 0] = 0
[0, 1] = 0
[1, 0] = 0
[1, 1] = 1
[3, 2] = 37
[2, 3] = 37
[6, 8] = 2183
[7, 11] = 5257
[18, 12] = 40932
[42, 42] = 2889558
[51, 72] = 11708274
Regeln
- Das ist Code-Golf, also gewinnt der kürzeste Code.
- Builtins, die dies lösen, sind nicht erlaubt.
Antworten:
Ruby, 58 Bytes
Dies ist eine einfache Implementierung des Algorithmus in der C-Antwort von Releasing Helium Nuclei .
Ich habe mit begrenztem Erfolg untersucht, warum diese Formel funktioniert. Es ist leicht zu bestätigen, dass die Anzahl der aufrechten Rechtecke gleich ist
(m+1)*m/2 * (n+1)*n/2
, die Anzahl der diagonalen Rechtecke ist etwas schwerer zu bestimmen.Neil hat bestätigt , für
m==n
dass die Anzahl der geneigten Rechtecken in einemn*n
Quadrat ist(4*n**4-n*n-3*n)/6
und dass , wennm>n
Sie eine zusätzliche hinzufügen müssen(m-n)(n*(4*n*n-1)/3)
(bezogen auf OEIS A000447 ), obwohl dies nicht erklären , wo diese beiden Formeln herkam. Ich habe einen Teil der Antwort gefunden.Denn
m==n
die Form innerhalb des Gitters ist ein aztekischer Diamant .Die Anzahl der Rechtecken in einem Aztec Diamanten ist die Summe der Anzahl von großen Rechtecken überlagerte zu machen (zum vierten Diamanten, der in einem gefunden wird
5x5
Gitter,2x8
,4x6
,6x4
, und8x2
) minus der Anzahl der Rechtecken zweimal gezählt (die Anzahl der Rechtecke im vorherigen aztekischen Diamanten).Die Formel lautet hier (TeX wird später hinzugefügt):
Laut Wolfram Alpha, die geschlossene Form für
f
IS1/30*(n-1)*n*(4*n**3+14*n**2+19*n+9)
und die geschlossene Form füraztec_rect
ist, wie Neil entdeckt1/6*n*(n-1)*(4*n**2+4*n+3) == 1/6*(4*n**4-n**2-3*n)
.Ich habe noch warum entdecken
(m-n)(n*(4*n*n-1)/3)
Werke, obwohl ich vermute , dass es ist , weil eine Definition von A000447 istbinomial(2*n+1, 3)
. Ich halte dich auf dem laufenden.Update: Ich habe Grund zu der Annahme, dass die Funktion der Anzahl der Rechtecke in einem erweiterten Azteken-Diamanten
m>n
mit der Anzahl der übereinanderliegenden2k*2(n-k)
Rechtecke im Diamanten-Minus zusammenhängtF(m-1,n-1)
. Mehr Ergebnisse, wenn ich sie habe.Update: Ich habe eine andere Route ausprobiert und eine andere Formel für erweiterte aztekische Diamanten gefunden, die größtenteils erklärbar ist, aber einen Begriff hat, den ich noch nicht verstehe. Huzzah! : D
Eine kurze Aufschlüsselung dieser letzten Formel:
(m-n+1)*(4*n**4-n*n-3*n)/6
ist die Anzahl der überlagerten aztekischen Diamanten der Größen
in der Struktur, wief(n,n) = (4*n**4-n*n-3*n)/6
.f(7,3)
hat 5 überlagerte aztekische Diamanten3
, währendf(3,3)
nur 1 Diamant hat.-f(m-1,n-1)
Entfernt einige der duplizierten Rechtecke aus der Mitte der überlagerten Diamanten.+(m-n)*2
Konten für 2 zusätzliche2
-by-(2n-1)
Rechtecke für jede zusätzliche Diamanten.+(m-n)*(n-2)
Für jeden zusätzlichen Diamanten wird ein zusätzliches Quadratn
berechnetn
.-(m-n-1)*f(n-1,n-1)
Dies ist der neue rätselhafte Begriff. Anscheinend habe ich einige zusätzliche Quadrate bei meiner Zählung nicht berücksichtigt, aber ich habe nicht herausgefunden, wo sie sich in dem erweiterten Diamanten befinden.Hinweis: when
m==n
,m-n-1 = -1
bedeutet, dass dieser letzte Term der Zählung Quadrate hinzufügt . In meiner regulären Formel fehlt mir möglicherweise etwas. Vollständige Offenlegung, dies sollte nur ein Patch für einen früheren Entwurf dieser Formel sein, der gerade funktioniert hat. Klar, ich muss noch nachdenken, was los ist, und es kann sein, dass meine Formel einige Fehler enthält. Ich werde euch auf dem Laufenden halten.Russell, Gary und Weisstein, Eric W. "Aztec Diamond". Aus MathWorld - Eine Wolfram-Webressource. http://mathworld.wolfram.com/AztecDiamond.html
quelle
C,
7164 BytesProbieren Sie es auf Ideone
quelle
m==n
: Die Anzahl der geneigten Rechtecke in einemn*n
Quadrat ist(4*n*n*n*n-n*n-3*n)/6
. Die Sequenz lautet 0, 9, 51, 166, 410, 855, 1589, 2716, 4356, 6645, wird jedoch in OEIS nicht angezeigt.m>n
Sie eine zusätzliche hinzufügen müssen(m-n)(n*(4*n*n-1)/3)
(letzter Teil der Formel aus OEIS A000447 entnommen). Das Umordnen und Hinzufügen ergibt die Formel von @ betseg.m==n
. Ich habe dann manuell die Anzahl der gekippten Rechtecke in kleinen Rechtecken berechnet und festgestellt, dass bei einer Vergrößerung der längeren Dimension immer die gleiche Anzahl von Rechtecken für eine bestimmte kürzere Dimension hinzugefügt wurde. Ich habe die Inkremente in OEIS eingespeist, was eine Übereinstimmung mit A000447 ergab.Python,
7368 BytesUnd während die folgende Version ein höheres bytecount (75) hat, war es eine schöne Übung, Orte zu finden, die man benutzen kann
~
:quelle
x=lambda m,n:m*~m*n*~n/4+n*((2*m-n)*(4*n*n-1)-3)/6if m>n else x(n,m)
def
. Vielen Dank! Aktualisiert.Konvex,
3736 BytesProbieren Sie es online!
Verwendet den Algorithmus von betseg, der für eine stapelbasierte Sprache modifiziert und optimiert wurde. Erklärung zu kommen, wenn ich etwas mehr Freizeit habe. Ich wette, das kann gekürzt werden, aber ich werde mich im Moment nicht darum kümmern.
quelle
Batch, 82 Bytes
quelle