Kara Algorithmen [KSR Wiki]

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 Verteilen von Blättern, dem Markieren eines Tunnels oder dem 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 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.

Tipp:

Verwende Kommentare mit #, um deine Programme zu strukturieren und offene Punkte zu notieren.

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.

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 while True: # Schleife endet nie! # Kara soll der Wand nach rechts folgen (nach links ginge auch...). # Was tut Kara, wenn rechts kein Baum ist? # Was andernfalls (else)? # Was, wenn geradeaus kein Baum ist? # .. was andernfalls? 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()

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

TTTTTTTTTTTTTTTTTTTTTT T T T TTTT TTTTTT T T T> T T TTTTTTTT TT TT T T TTTTTTTTTTTTTTTTTTTTTT

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)

assert "4" in output_lines()[-1]

Aufgabe F3: Golfplatz (schwierig)

Der Golf-Rasen ist voller Blätter - schreibe Code, um alle aufzusammeln! Anders als in der Aufgabe C6 können wir jetzt eine Variable verwenden, um uns zu merken, ob wir beim nächsten Baum nach links oder nach rechts wenden sollen und so den Platz in einer Schlangenlinie ablaufen. Die Variable könnte beispielsweise mit next_turn_right = True initialisiert werden.

Gib nach jeder Wende aus, wieviele Blätter Kara aufgesammelt hat.

TTTTTTTTTTT TeLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLLLT TLLLLLLLL M TTTTTTTTTTT

# Hin- und zurück laufen next_turn_right = True leaves = 0 while not kara.mushroomFront(): kara.removeLeaf() leaves = leaves + 1 # Wenden beim Baum. if kara.treeFront(): if next_turn_right: print("Turning right") kara.turnRight() kara.move() kara.turnRight() else: print("Turning left") kara.turnLeft() kara.move() kara.turnLeft() print("Collected ", leaves, "leaves") next_turn_right = not next_turn_right else: kara.move() print("Collected ", leaves, "leaves")

assert world_leaves() == 0

Aufgabe F4: Herbstwald

Kara läuft durch den herbstlichen Wald und sammelt schöne Blätter auf. Immer wenn sie auf einen Pilz trifft, biegt sie links ab. Sie stoppt, wenn sie auf einen Baum trifft und gibt aus, ob sie mehr Blätter oder mehr Pilze angetroffen hat.

TTTTTTTTTTT T LL M T T M LL LL T T MLLML T T M L T T LM MMT T v MLL LT T L M LT T M L T T L LL MT T M LMT TTTTTTTTTTT

leaves = 0 mushrooms = 0 while not kara.treeFront(): if kara.onLeaf(): kara.removeLeaf() leaves = leaves + 1 if kara.mushroomFront(): kara.turnLeft() mushrooms = mushrooms + 1 else: kara.move() if leaves > mushrooms: print("Es hat mehr Blätter als Pilze, nämlich", leaves) else: print("Es hat mehr oder gleichviel Pilze wie Blätter, nämlich", mushrooms)

assert "13" in output_lines()[-1]