Wie viele subrectangle existiert ein m x n raster

Gegeben m x n raster, wie viele verschiedene sub-Rechtecke vorhanden ist, auf ein solches raster?

Beispielsweise

1 x 1 grid hat 1 sub-Rechteck.

1 x 2 Gitter hat 3 sub-Rechtecke.

Ich bin auf der Suche nach einer Allgemeinen Formel, die verwendet werden können, direkt zu berechnen, die Anzahl vorhandener sub-Rechteck.

Wie viele Dreiecke der Größe a x b gibt es auf ein m x n raster? Jetzt Summe, dass für alle a und b.
Ich bin auf der Suche nach einer einzigen Formel.
Und ich bin versucht, Ihnen zu helfen, es zu finden.
Dynamische Programmierung wäre perfekt für diese.
Nein, es ist eine einfache Formel
Gegeben eine m x n Netz und einem Ankerpunkt i, j, die Gesamtzahl der sub-Rechtecke, verwenden Sie das Ankerpunkt als Obere linke Ecke (m-i+1)*(n-j+1).
Gut, ich hatte eine Antwort getippt für dich, aber ich mag @ChrisTaylor Idee führt Sie zu es. Also, Fragen, Ihnen zu helfen: Woher weißt du, eine 1x2-3 sub-rects? Wie viele sub-rects, wäre 1x5? Wenn Sie verstehen, eine dimension, finden die Kombinationen für 2 ist einfach.
Richtig! So erhalten Sie die Antwort durch die Summe, die über alle i=1...m und j=1...n. Es wird helfen, erweitern Sie die Klammern einige. Kennen Sie die Formel für die Summe der ganzen zahlen zwischen 1 und N?
Ich denke, Thomash hat mir die perfekte Lösung wie folgt. Danke an Euch alle.
Diese Frage scheint off-topic, weil es um Mathematik.

InformationsquelleAutor q0987 | 2013-07-29

algorithm

17

Die Antwort ist m(m+1)n(n+1)/4.

wird ein Rechteck definiert sich durch Ihre beiden Projektionen auf die x-Achse und auf der y-Achse.

Projektion auf x-Achse : Anzahl der Paare (a,b), so dass 1 <= a <= b <= m = m(m+1)/2

idem für die y-Achse
- Dude, Cooooool.
InformationsquelleAutor Thomash
16

Gleiche Antwort wie @Thomash, aber mit ein bisschen mehr Erklärung, posting für die Nachwelt:

Wenn Sie dieses heraus in einer dimension, es ist leicht zu bewegen in zwei Dimensionen.

Schauen wir uns eine 1x5:
```
 5 1x1 squares
+4 1x2 squares
+3 1x3 squares
+2 1x4 squares
+1 1x5 squares = 15 squares.
```
Die Formel dafür ist einfach: sum = n(1 + n)/2. In dem Fall 5, die Sie wollen 5(1+5)/2 = 15.

So, um Ihre Antwort, nur tun Sie dies für n und m, und multiplizieren Sie Sie:
```
sumN = n(1+n)/2
sumM = m(1+m)/2
totalRectangles = nm(1+n)(1+m)/4
```
InformationsquelleAutor Scott Mermelstein
3

Für dieses lets nehme an, Sie haben m Spalten und n Zeilen:
```
. . . .
. . . .
. . . .
```
In der obigen raster m 4 und die n ist 3. Lassen Sie sagen, Sie müssen wissen, wie viele Rechteck, das Sie bilden können, wenn Sie wählen Sie top-Links zeigen. Wenn Sie wählen Sie die linke Obere Ecke, D. H.
```
* . . .
. . . .
. . . .
```
Haben Sie 3 Punkt zu wählen, in die Rechte und 2 Punkte zu wählen, an der Unterseite, daher total Kombinationen sind: 3*2 = 6.

Deshalb die Gesamtzahl Rechteck, das Sie bilden können, entspricht der Gesamtzahl der Rechtecke in jedem Punkt ab (0, 0) (top left ausgehen 0, 0) bis (m-1, n-1).

Wenn Sie versuchen zu finden Summierung dieser:
```
[(m-1)*(n-1) + (m-2)*(n-1) + (m-3)*(n-1) ... + (n-1)] + 
[(m-1)*(n-2) + (m-2)*(n-2) ... + 1*(n-2)] +
[(m-1)*(n-3) + (m-2)*(n-3) ... + 1*(n-3)] +
... 
```
Gleich ist
```
(n-1)*(1 + 2 + .. + m-1)
+
(n-2)*(1 + 2 + .. + m-1)
+
.
.
+
1*(1 + 2 + ... + m-1)
```
So erhalten Sie
```
(1 + 2 + ... + n-1) * ( 1 + 2 + 3 ... + m-1)
= mn(n-1)(m-1)/4
```
Seit m und n ist dein Fall nicht der Punkt, sondern die Anzahl der Liniensegmente gebildet. Obigen Formel umgewandelt werden kann:
```
m = m + 1
&
n = n + 1
```
Und es wird
```
(n+1)(m+1)mn /4
```
- nehmen wir n=1 und m=2, dann [(m-1)*(n-1)(m+n)]/2=0 !!! Glaubst du nicht, es ist etwas falsch?
- Wenn ich verstehe es Recht, n=1 bedeutet, dass es eine einzige Zeile, so dass Sie machen sollte 0 Rechtecke.
- Du solltest die Frage nochmal Lesen: 1 x 2 Gitter hat 3 sub-Rechtecke.
- Danke! Ich habe korrigiert meine Lösung.
InformationsquelleAutor Shivam
3

Fand ich eine schöne Lösung,

Lässt Blick auf die Tabelle Grenzen des Rasters.

Und um ein Rechteck zu erstellen, benötigen wir vier Punkte an den Grenzen.

2 Punkte horizontaler und 2 vertikale

beispielsweise (n = 4, m = 5)

Beachten Sie, dass die Wahl für N + 1 und M + 1
Denn schauen wir uns die Grenzen und nicht die Rechtecke, die sich

Hier ist ein Beispiel für eine Auswahl:

Können wir berechnen, alle möglichen Optionen zu wählen, 2 horizontale Punkt und 2 vertikale zeigen Sie mit der binomischen Formel:

InformationsquelleAutor Meni Samet
1

Einer alternativen Lösung,

In eine m*n-Gitter ist, haben wir m+1 Zeilen und n+1 Linien schneiden.

Verwenden wir die Tatsache, ein Rechteck gebildet werden kann, indem ein Schnittpunkt zwischen den beiden Linien und ein weiterer Punkt, der nicht entweder in die horizontale oder vertikale Linie.

So, die Anzahl der Möglichkeiten zu wählen, ein Schnittpunkt ist (m+1)(n+1).
und anschließend die Anzahl der Möglichkeiten zu wählen, der zweite Punkt ist [die Anzahl von Möglichkeiten wählen, um einen Schnittpunkt mit Ausnahme der Punkte in der gleichen horizontalen und vertikalen Linie] ist ((m+1)(n+1)-n-m-1)

Betrachten wir nun ein 1x1-raster , verwenden wir die Tatsache dieses raster gezählt werden kann, 4 mal jeweils eindeutig durch die 4 Punkte.

Daher die Gesamtzahl der Rechtecke, die kann, gebildet ist [(m+1)(n+1)((m+1)(n+1)-n-m-1)]/4

kann weiter vereinfacht werden zu [(m+1)(n+1)(m)(n)]/4

InformationsquelleAutor Chaipau
-1

Sollte die richtige Antwort sein (m(m+1)n(n+1))/4 minus die Anzahl der Quadrate im Rechteck-raster.
- Hi Shashank. Sie sind der Beantwortung einer sehr alten Frage, die bereits über eine akzeptierte Antwort. Können Sie erklären in Ihrem Beitrag, warum es besser ist als die anderen Antworten?
InformationsquelleAutor Shashank

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.