faecher:informatik:oberstufe:algorithmen:rekursion:teile_und_herrsche:feldquadrate:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
====== Feldquadrate ======
{{ .:farmer.png?120|}}
Stell dir vor du bist ein Landwirt mit einem rechteckigen Feld: 

{{ .:feld.drawio.png?600 |}}

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

{{ .:versuche.drawio.png?600 |}}

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.

----
{{:aufgabe.png?nolink  |}}
=== (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.

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

{{ .:ggt.drawio.png?600 |}}

++++

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:

 {{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate:verkleinern.drawio.png?600 |}}

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

<WRAP center round tip 95%>
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.
</WRAP>

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''. ++++

----
{{:aufgabe.png?nolink  |}}
=== (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 beschriebenen Eigenschaft, ''80'' ist also die gesuchte Seitenlänge.
++++

----
{{:aufgabe.png?nolink  |}}
=== (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.