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)
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, sodass du kein Problem hast, das größte Quadrat zu ermitteln, welches dein Feld wie gewünscht teilt.
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".
Mit dem Schritt "Schneide so viele Quadrate mit der Seitenlänge der kurzen Feldseite vom Feld ab, wie ins Feld passen" hast du das Problem also in ein kleineres, einfacheres Problem verwandelt.
Nun kannst du überprüfen, ob der Basisfall eingetreten ist: Ist die neue lange Seite ein Vielfaches der neuen kurzen Seite?
Was geschieht im nächsten Schritt? Rechne und mache eine Skizze! Entscheide ob der Basisfall erreicht ist.
(A2)
Verfolge das Verfahren weiter bis zum Basisfall. Welche "Rest-Rechtecke" treten dabei noch auf?
(A3)
Implementiere anhand der Überlegungen auf dieser Wiki-Seite eine rekursive Methode feldQuadrate(seite1: integer, seite2: integer): integer, die die Seitenlänge des größten Quadrats zurückgibt, die das gegebene Feld mit den Seitenlängen seite1 und seite2 teilt.