Feldquadrate

Stell dir vor du bist ein Landwirt mit einem rechteckigen Feld:

Aus Gründen, die du nicht wirklich nachvollziehen kannst, wohnt dir der Zwang inne, dieses Feld in gleich große quadratische Parzellen aufzuteilen. Eine Möglichkeit, dies zu tun, wären Parzellen der Größe 1x1 Meter.

Weil du aber nicht so viele Parzellen verwalten möchtest, reicht dir diese Möglichkeit der Aufteilung nicht aus - du suchst die größten Quadrate, die eine Aufteilung in quadratische Parzellen möglich macht.1) Man kann das Ganze auch mathematisch einfacher ausdrücken: Du suchst den größten gemeinsamen Teiler der beiden Seitenlängen deines Felds…

Du probierst ein wenig rum:

Das wird aber alles nichts, mal sind es keine Quadrate, mal sind die nicht gleich groß, mal sind sie zu klein. Es muss eine Strategie her.

Teile und herrsche...

Finde den Basisfall heraus - ein Fall, bei dem die Lösung einfach zu ermitteln ist.

Zerlege die Aufgabe in Teilaufgaben, die sich diesem Basisfall annähern.

(A1)

Wann wäre die Aufteilung klar? Überlege dir, was für die Seitenlängen deines Felds gelten müsste, so dass du kein Problem hast, das größte Quadrat zu ermitteln, welches dein Feld wie gewünscht teilt.

Lösung

Wenn die lange Seite deines Feldes ein Vielfaches der kurzen Seite ist, ist das Problem schnell gelöst: Das größte Quadrat, dass dein Feld teilt, hat die Seitenlänge der kurzen Feldseite:

O.k. - allerdings hat dein Feld nun mal leider nicht die geforderte Eigenschaft. Für den Rekursionsfall muss man sich nun ein Vorgehen überlegen, welches dazu führt, dass man sich dem Basisfall "annähert".

Dazu könntest du z.B. zwei Quadrate mit der kurzen Kantenlänge einpassen - dann bleibt ein kleineres Rechteck übrig, das noch aufgeteilt werden muss:

Die lange Seite des neuen Rechtecks, ist die bisherige kurze Seite und die Seitenlänge der bereits "abgeschnittenen" Quadrate. Wenn du nun für das rote, kleine Rechteck eine Aufteilung findest, passt diese auf jeden Fall auch in die großen Quadrate, denn deren Seiten sind ja so lang wie deine "neue lange Seite".