Wie kann ein Rechteck in möglichst wenige Quadrate zerlegt werden?
Ich habe ein Rechteck mit ganzzahligen Seitenlängen. Dieses Rechteck möchte ich nun in Quadrate zerlegen, die eine Zweierpotenz als Seitenlänge haben. Dabei sollen so wenige Quadrate wie möglich entstehen.
Als Beispiel betrachten wir ein 9 x 6-Rechteck. Ein solches Rechteck lässt sich wie folgt in zwei Quadrate der Seitenlänge 4, vier Quadrate der Seitenlänge 2 und sechs Quadrate der Seitenlänge 1 zerlegen:
Nun suche ich nach einer Möglichkeit, dies nicht zeichnerisch, sondern durch eine Formel oder einen Algorithmus (gerne in Pseudocode) zu bestimmen. Hat jemand eine Idee, wie man da vorgehen könnte? Meine bisherigen Ansätze waren nicht wirklich zielführend und sicherlich auch zu kompliziert gedacht...
1 Antwort
Ich vermute, dass der folgende rekursive Algorithmus stets die minimale Anzahl an Quadraten in einem a×b-Rechteck produziert:
- Wenn a=0 oder b=0: fertig.
- Lege ein möglichst großes Quadrat mit Kantenlänge q≤min(a,b) in eine Ecke.
- Zerlege (rekursiv) die beiden Rest-Rechtecke (q-a)×q und a×(b-q).
Wahrscheinlich kann man in Schritt 2 sogar drei Rest-Rechtecke weiter zerlegen: (q-a)×q, q×(b-q) und (q-a)×(b-q).
_____________________________________________________
Meine Vermutung beruht auf folgender Beobachtung:
Man kann in Deinem Beispiel die Quadrate so anordnen, dass links zwei gleiche 4×6-Blöcke aus je einem 4×4- und zwei 2×2-Quadraten liegt, und am rechten Rand noch 6 1×1-Quadrate kleben.
Es sieht so aus, als ob so eine Anordnung, bei der das Rechteck durch gerade Schnitte zerlegt wird, immer möglich ist.
