Python 3 - Lernen und professionell anwenden

193

6.16

Lösungen

Aufgabe 5

Die Abbildungen zeigen zwei Baumstrukturen. Ändern Sie die Zahlenwerte im Baum-Pro-

gramm aus Abschnitt 6.9 so ab, dass es Strukturen wie auf dem Bild erzeugt. Hinweis: Ach-

ten Sie auf die Winkel.

Abb. 6.13: Zwei Bäume

6.16 Lösungen

Lösung 1

Erläuterung:

Dem Parameter

worte in der Parameterliste im Funktionskopf wird ein Stern vorangestellt.

Damit ist

worte als Tupel ungewisser Länge definiert. Die Länge des Tupels hängt davon ab,

wie viele Argumente beim Funktionsaufruf übergeben worden sind. In der

for-Schleife

nimmt die Variable

wort nacheinander die Werte der Elemente des Tupels worte an.

Lösung 2

def konkat(*worte):

ergebnis = ''

for wort in worte:

ergebnis += wort

return ergebnis

def zufallsbuchstabe():

buchstaben = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

import random

return buchstaben[random.randint(0, 25)]

def verstecke(s, n=1):

textGross = s.upper()

versteckt = ''

for c in textGross:

Kapitel 6

Funktionen

194

Erläuterung:

Die Funktion

zufallsbuchstabe() liefert einen zufälligen Großbuchstaben, der aus dem

String

buchstaben mithilfe einer Zufallszahl zwischen 0 und 25 ausgewählt wird. In der

Funktion

verstecke() wird zunächst das Argument in einen String aus Großbuchstaben

überführt. In der äußeren

for-Schleife wird der Ergebnis-String versteckt schrittweise

aufgebaut. An

versteckt werden bei jedem Schleifendurchlauf das nächste Zeichen aus

textGross und dann n Zufallszeichen angehängt.

Lösung 3

Erläuterung:

Der optionale Parameter wird durch die Anweisung

n=10 in der Parameterliste auf den Wert

10 voreingestellt. Mit float(x) wird erzwungen, dass der folgende Divisionsoperator / die

exakte Division durchführt. Anderenfalls würde eine ganzzahlige Division stattfinden,

wenn das Argument

x eine ganze Zahl ist.

Zum Ausprobieren:

Diese Implementierung folgt strikt der angegebenen Definition des Heron-Verfahrens.

Wenn Sie die Funktion mit einem großen Wert für das zweite Argument testen, z.B.

wur-

zel(2,

20), werden Sie eine sehr lange Laufzeit beobachten. Das liegt an der großen Rekur-

sionstiefe. Diese wird dadurch verursacht, dass im Anweisungsblock der Funktion zwei

rekursive Aufrufe enthalten sind. In der folgenden Variante gibt es nur einen rekursiven

Aufruf. Das bewirkt eine erheblich geringere Rekursionstiefe und bessere Laufzeit:

Lösung 4

Um einen rekursiven Algorithmus zu finden, muss man sich zu folgenden zwei Fragen

Gedanken machen:

versteckt += c

for i in range(n):

versteckt += zufallsbuchstabe()

return versteckt

def wurzel(x, n =10):

ifn==1:

return 1

else:

return 0.5*(wurzel(x, n-1)+float(x)/wurzel(x,n-1))

def wurzel(x, n=20):

ifn==1:

return 1

else:

vorigeNaeherung = wurzel(x, n-1)

return 0.5*(vorigeNaeherung + float(x)/vorigeNaeherung)

195

6.16

Lösungen

쐽 Wie kann das Problem direkt gelöst werden?

쐽 Wie kann man einen Turm mit n Scheiben bewegen, wenn man schon weiß, wie man

einen Turm mit

n-1 Scheiben bewegen kann?

Der einfache Fall tritt auf, wenn der Turm nur aus einer Scheibe besteht. Beim Aufruf

bewege (1, 1, 2, 3) gibt die Funktion die Anweisung aus: »Lege eine Scheibe von 1 nach 2.«

Aber was ist im allgemeinen Fall zu tun, wenn der Turm aus

n Scheiben besteht und n grö-

ßer als

1 ist? Wir zerlegen in Gedanken den Turm in zwei Teile: Ein Turm mit n-1 Scheiben

steht auf einer großen Scheibe. Die Bewegung des gesamten Turms kann nun in drei Schrit-

ten vollzogen werden (vgl. Abbildung 6.14):

쐽 Bewege den oberen Turm mit n-1 Scheiben auf die freie Zwischenposition ueber.

쐽 Lege die einzelne große Scheibe auf die Zielposition nach.

쐽 Bewege den Turm mit n-1 Scheiben von der Position ueber zur Position nach (auf die

große Scheibe) und verwende die Position

von als Zwischenposition (ueber).

Abb. 6.14: Rekursives Bewegen eines Hanoi-Turms mit n Scheiben

von

nach

über

n-1

von

nach

über

n-1

von

nach

über

n-1

Kapitel 6

Funktionen

196

Die folgende kleine Python-Funktion implementiert diese Idee:

Lösung 5

Bei der Funktion zum ersten Bild wurden die Winkel für die Drehung und der Verkleine-

rungsfaktor beim rekursiven Aufruf geändert.

Bei der Funktion zum zweiten Bild wurden allein die Winkel geändert.

def bewege(n, von, nach, ueber):

if n == 1:

print('Lege eine Scheibe von',

von, 'nach', nach,'.')

else:

bewege(n-1, von, ueber, nach)

bewege(1, von, nach, ueber)

bewege (n-1, ueber, nach, von)

def baum(x):

ifx<5:return

else:

forward(x)

left(30)

baum(x*0.7)

right(90)

baum(x/2)

left(60)

backward(x)

return

def baum(x):

ifx<5:return

else:

forward(x)

left(90)

baum(x*0.5)

right(180)

baum(x*0.5)

left(90)

back(x)

return