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