Kara Algorithmen [KSR Wiki]

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.
## Kara Algorithmen

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

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>