Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- gf_informatik:karatutorial:algorithmen [2026-09-06 20:33] – angelegt hof
+++ gf_informatik:karatutorial:algorithmen [2026-09-08 08:03] (aktuell) – [Aufgabe F2: Längster Tunnel] hof
@@ Zeile 1: / Zeile 1: @@
 ## Kara Algorithmen
-- (already covered):
+Ein _Algorithmus_ ist eine eindeutige Vorgehensweise zur Lösung eines Problems. Du hast bereits einige Algorithmen ausprobiert und sogar selber einige umgesetzt, z.B. zum [[verzweigungen#aufgabe_c2blaetter_verteilen|Verteilen von Blättern]], dem [[logik#aufgabe_d1tunnel_markieren|Markieren eines Tunnels]] oder dem [[variablen#aufgabe_e2blaetter_zaehlen|Zählen von Blättern]].
-   * leaf counting
-   * tunnel detection
-- wall following
-- longest tunnel finding
-- leaf ratio & comparisons (more / less)
-- distance between two leaves
-- filling a rectangle with leaves
-- Boustrophedon field sweep
-- alternating pattern sowing
+Zentral dabei ist, dass diese Algorithmen nicht nur in der vorgegebenen Kara-Welt funktionieren, sondern die richtige Lösung auch dann liefern, wenn die Welt anders aussieht - zum Beispiel wenn mehr oder weniger Blätter vorhanden sind. Ein Algorithmus, der für [[variablen#aufgabe_e2blaetter_zaehlen|Aufgabe E2]] einfach die korrekte Zahl `34` ausgibt, genügt diesem Kriterium kaum.
+In diesem Kapitel werden wir unsere Python-Kenntnisse vertiefen und auf algorithmische Probleme anwenden.
+#### Aufgabe F1: Wand folgen
+Kara wacht eifersüchtig über ihren Blättervorrat. Schreibe Python-Code, der Kara immerzu um die Bäume herumlaufen lässt.
+**Hinweis**: Das Programm hört von sich aus nie auf, muss also aktiv unterbrochen werden, um es zu stoppen.
+<kara-exercise id="wall-follower" step="100" timeout="inf">
+<kara-world>
+TTTTTTTTTTTTTTT
+T             T
+T    TTTTT    T
+T   TTLLLTT   T
+T   TTLLLLT>  T
+T    TLLLTT   T
+T    TLLLT    T
+T    TLLLT    T
+T  TTTLLLTT   T
+T  TLLLLLLT   T
+T  TLTTTLTT   T
+T  TLT TTT    T
+T  TTT        T
+T             T
+TTTTTTTTTTTTTTT
+</kara-world>
+<kara-solution>
+while True:  # endet nie!
+    if not kara.treeRight():
+        # der rechten Wand folgen
+        kara.turnRight()
+        kara.move()
+    else:
+        # rechts ist ein Baum
+        if not kara.treeFront():
+            kara.move()
+        else:
+            kara.turnLeft()
+</kara-solution>
+</kara-exercise>
+++++TOC|
+  * (already covered):
+    * leaf counting
+    * tunnel detection
+  * wall following
+  * longest tunnel finding
+  * leaf ratio & comparisons (more / less)
+  * distance between two leaves
+  * filling a rectangle with leaves
+  * Boustrophedon field sweep
+  * alternating pattern sowing
+++++
+#### Aufgabe F2: Längster Tunnel
+Schreibe Python-Code, um den Länge des längsten Tunnels auszugeben. Ein Tunnel ist definiert als eine gerade Strecke, bei der links **und** rechts ein Baum steht. Am Ende wird die Länge des längsten Tunnels auf der Konsole ausgegeben. Kara stoppt, wenn Sie auf einen Baum trifft.
+**Tipps:**
+  * Merke dir den bislang längsten Tunnel (Rekordhalter) in einer Variable (zu Beginn `0`).
+  * Merke dir die Länge des aktuellen Tunnels in einer Variable.
+    * am Ende jedes Tunnels vergleichst du den aktuellen Tunnel mit dem bisherigen Rekordhalter und setzt ev. diesen eventuell auf den neuen Höchstwert.
+    * Vergleiche kannst du mit dem Operator `>` oder `<` anstellen, also `if laenge > rekord:`
+    * danach wird die aktuelle Länge auf `0` gesetzt.
+<kara-exercise id="max_tunnel" step="200" showsolution>
+<kara-world>
+   TTTTTTTTTTTTTTTTTTTTTT
+   T                    T
+   T   TTTT   TTTTTT  T T
+   T>                   T
+   T      TTTTTTTT TT  TT
+   T                    T
+   TTTTTTTTTTTTTTTTTTTTTT
+</kara-world>
+<kara-solution>
+record = 0
+length = 0
+while not kara.treeFront():
+    if kara.treeLeft() and kara.treeRight():
+        length = length + 1
+        kara.putLeaf()  # optional
+    else:
+        if length > record:
+            record = length
+            print("Neuer Rekord:", record)
+        length = 0
+    kara.move()
+print("Rekord:", record)
+</kara-solution>
+<kara-tests>
+assert "4" in output_lines()[-1]
+</kara-tests>
+</kara-exercise>