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".

Mit dem Schritt "Schneide soviele Qudrate 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?

Lösung

Nö, die neue kurze Seite ist 1680-2*640=400, die neue lange Seite ist 640, das passt nicht.

Was geschieht im nächsten Schritt? Rechne und mache eine Skizze! Entscheide ob der Basisfall erreicht ist.

Lösung

man schneidet Quadrate der Seitenlänge 400 ab (eines) und erhält ein neues, kleineres Rest-Rechteck mit den Seitenlängen 400 und 240. Der Basisfall ist nicht erreicht, 400 ist kein Vielfaches von 240.

(A2)

Verfolge das Verfahren weiter bis zum Basisfall. Welche "Rest-Rechtecke" treten dabei noch auf?

Lösung

Weitere Rest-Rechtecke sind: 240x160 und 160x80. damit ist der Basisfalll erreicht: Beim Rechteck 160x80 ist die lange Seite ein Vielfaches der kurzen Seite, es kann in zwei Quadrate mit der Seitenlänge 80 geteilt werden.

Quadrate mit der Seitenlänge 80 teilen auch alle bisherigen Rechtecke, wegen der oben beschrtiebenen Eigenschaft, 80 ist also die gesuchte Seitenlänge.

(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.