Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate:start [26.01.2022 20:26] – [Teile und herrsche...] sbel
+++ faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Feldquadrate ======
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate:farmer.png?120|}}
-Stell dir vor du bist ein Landwirt mit einem rechteckigen Feld:
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate: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:
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate: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, 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:
-{{ :faecher:informatik:oberstufe:algorithmen:teile_und_herrsche:feldquadrate: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 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.
-</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. ++++