v04 (Kontrollstruktu..

Vorlesung
4
Kontrollstrukturen und
Schleifen
Inhalt
1 Verzweigungen
1.1 Bedingte Verzweigungen in Python: if-elif-else
1.2 Verzweigungen und Blöcke in anderen Programmiersprachen
2 Visualisierung von Kontrollstrukturen
2.1 Kontrollstrukturen
2.2 Graphische Repräsentationen
2.2.1 Programmablaufpläne
2.2.2 Nassi-Shneiderman-Diagramme
2.2.3 Jackson-Diagramme
2.2.4 Unified Modeling Language
3 Iterative Grundstrukturen
3.1 Schleifen in Python: for und while
3.2 break – continue - else
3.3 Realisierungsformen der Iteration
3.4 Schleifen in anderen Programmiersprachen
3.5 Iteration als Lösungsmethode
3.6 Beispiel für iterative Approximation: die Regula Falsi
4 Reading
5 Hinweise zu Programmierkursen
1
2
2
4
4
5
5
6
7
8
9
9
13
14
17
18
19
21
21
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
V 4 Kontrollstrukturen
Vorlesung
4
6
Lernziele:
In diesem Kapitel werden wir die Verzweigung, und Iteration als grundlegende
mathematische und informatische Lösungsmethoden kennen lernen sowie deren
Realisierungen in Programmiersprachen. Hierzu gehören insbesondere die verschiedenen Ausprägungen von Schleifen zur Iteration.
Alle diese Konzepte finden in Python eine konkrete Ausprägung. Es soll gelernt
werden, diese grundsätzlich einzuordnen und anzuwenden.
1 Verzweigungen
In vielen Fällen reicht eine einfache lineare Abfolge von Anweisungen nicht aus, sondern wir
benötigen Fallunterscheidungen. Je nach Ergebnis der Berechnungen müssen unterschiedliche
Dinge getan werden, es muss zwischen den möglichen Aktionen verzweigt werden. Bedingte
Verzweigungen bilden zusammen mit den Schleifen die Kontrollstrukturen moderner Programmiersprachen. In allen imperativen und objektorientierten Sprachen sind sie in unterschiedlichen Ausprägungen vorhanden. Leistungsfähige Schleifenkonstrukte zusammen mit Unterprogrammmethoden sind essenzielle Konstituenten der strukturierten Programmierung
(dritte Programmiersprachen-Generation) aber auch der Objektorientierten Programmierung.
Diese Vorlesung beschreibt Kontrollfluss-Anweisungen eines Python Programms: Bedingungen
und Schleifen. Ausnahmeereignisse (exeptions), die auftreten können, führen zwar ebenfalls zu
einer Verzeigung und gehörten damit prinzipiell auch in dieses Vorlesungskapitel, werden allerdings später behandelt.
1
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
1.1 Bedingte Verzweigungen in Python: if-elif-else
In Python steuern die Anweisungen if, else und elif die bedingte Ausführung des Programmcodes und implementieren so Verzweigungen. In einem Programm sieht das dann so aus:
if expression:
suite
elif expression:
suite
elif expression:
suite
...
else:
suite
Für die Formulierung von Bedingungen gilt somit folgende Syntax:
if_stmt
::=
suite
::= stmt_list NEWLINE
| NEWLINE INDENT statement+ DEDENT
::= stmt_list NEWLINE | compound_stmt
::= simple_stmt (";" simple_stmt)* [";"]
statement
stmt_list
"if" expression ":" suite
( "elif" expression ":" suite )*
["else" ":" suite]
„Expression“ ist hierbei ein Ausdruck, der sich zu einem logischen (booleschen) Wert auswerten lässt, und das ist fast jeder. Der Bezeichner „suite“ kennzeichnet eine beliebige Anweisungsfolge auf gleicher Einrückungsebene. In anderen Programmiersprachen nennt man eine „suite“
auch einen Block. Hiermit ist dann auch der Gültigkeitsbereich einer Variablen nur innerhalb
des Blocks festgelegt. Falls keine Aktion ausgeführt werden muss, kann man sowohl die elseals auch die elif-Klausel einer Bedingung weglassen. Man verwendet dann die passAnweisung, wenn eine bestimmte Klausel keine Anweisungen braucht.
Ein konkretes kleines Beispiel:
a = 3
b = 2
if a < b:
pass
elif a == b:
a = a + 1
else: a = a - 1
print a
Und das Ergebnis beim Durchlauf:
>>> ================================ RESTART ================================
>>>
2
1.2 Verzweigungen und Blöcke in anderen Programmiersprachen
Neben den syntaktischen Unterschieden gibt es subtile semantische Unterschiede, die man für
jede Sprache sehr differenziert betrachten muss. Das würde jedoch weit über unser Lernziel
herausreichen. Hier geht es zuerst darum, die prinzipiellen Varianten zu erkennen und zusammenfassendes Verständnis (Sprach-Komprehension) für die Konzepte zu erlangen!
2
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
Die auffälligsten Unterschiede zwischen den verschiedenen Programmiersprachen findet man
bei der Kennzeichnung von „Blöcken“ oder „Suiten“ in Programmiersprachen. Beide Konstrukte kennzeichnen Folgen von Anweisungen, die zu einer Einheit zusammengefasst sind.
Blöcke markieren in Sprachen mit statischer Typprüfung (also solchen Sprachen in denen eine
Variablendefinition und –deklaration erfolgen muss) den Gültigkeitsbereich der entsprechenden Definition oder Deklaration: Die Variable ist nur in dem Block bekannt, in dem sie definiert
respektive deklariert wird. In unserer Auflistung kennzeichnet die Klammerung „[ ... ]“ optionale
Konstrukte.
Sprache
Blöcke / Suiten
Python
C, C++
Java
Fortran90/95 (2003)
Einrückung (indent)
Pascal
Anmerkungen
{ … }
{ … }
program … end program
if … then … [else if … ]end if
select case … end select
do … if … exit … end do
do while … end do
begin … end
Um die Lesbarkeit des
Quellcodes zu verbessern
werden oft in Programmierrichtlinien zusätzlich zur
Klammerung Einrückungen
empfohlen. Diese haben
aber für den Compiler keine
Aussage!
Für die Verzweigung, die in jeder Programmiersprache vertreten ist, finden wir auch verschiedene Varianten:
Sprache
Verzweigungen
Anmerkungen
Python
if expression:
suite
[elif expression:
suite
elif expression:
suite
...]
[else:
suite]
als einseitige, zweiseitige und mehrseitige Auswahl genutzt
if(expression)
…;
[else if(expression)
…;
else if(expression)
…;
…
else
Einrückungen sind „nur“ Programmierkonvention
C, C++
Einrückungen sind zwingend!
...;];
exp1 ? exp2 : exp3;
Bedingter Ausdruck:
Wenn exp1 ungleich 0 und somit
true, dann ist der Ausdruck exp2
das Resultat der bedingten Anweisung, andernfalls ist exp3 das
Resultat.
3
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
switch(expression)
{
case const-expr: …;
case const-expr: …;
…
default: …;
};
Java
mehrseitige Auswahl:
const-expr sind Konstanten
if (<log.Ausdruck> )
…
else {
…
}
switch (myIntWert) {
case 0 :
…;
break;
case 1 :
…;
default : …;
}
mehrseitige Auswahl
if (<log.Ausdruck>) then
…
Fortran
[else
if
(<log.Ausdruck>)
90/95 (2003)
then
[else
end if
…]
…]
select case (<case-Ausdruck>)
case (<case-Fall 1>) …
case (<case-Fall 2>) …
…
case default …
end select
Pascal
if <Bedingung>
then …
[else …];
einseitige und zweiseitige Auswahl
case <Variable>
1:
… ;
2:
… ;
…
else …
end;
mehrseitige Auswahl
2 Visualisierung von Kontrollstrukturen
Nachdem wir Verzweigungen bei Python kennen gelernt haben und sie mit denen anderer Programmiersprachen verglichen haben, können wir das Ganze verallgemeinern. Eine Verzweigung, also wertabhängige Fallunterscheidung, ist sowohl in der Mathematik, als auch in der Informatik elementar für fast jede Art von Verfahren (Algorithmen).
2.1 Kontrollstrukturen
Aufgrund einer Bedingung wird der Programmfluss (die Abfolge der Ausführung der Befehle)
verzweigt. Wir unterscheiden die einfache (bedingte) Verzweigung, die den Programmfluss
in zwei Pfade auftrennt und eine mehrfache Verzweigung.
4
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
Realisiert ist dies in den meisten Programmiersprachen sehr ähnlich, ungefähr folgendermaßen:
if <Bedingung>
then
Aktionsfolge
else
<AlternativeAktionsfolge>
endif
und die mehrfache Verzweigung mit
case <aVariable>
aValue1: <AktionsfolgeA>
aValue2: <AktionsfolgeB>
...
otherwise: <Aktionsfolge>
endcase
In (fast) allen modernen Programmiersprachen werden Verzweigungsstrukturen durch
if … then … else realisiert. Unterschiede finden sich allenfalls in Details der Syntax, z.B.
der Art der Klammerung der Anweisungsblöcke. Größere Unterschiede in Syntax und Semantik
finden wir allerdings bei Mehrfachverzweigungen: Hier sind üblich: CASE … SWITCH … oder
if … then … elif … elif …else Strukturen gebräuchlich.
2.2 Graphische Repräsentationen
Zur Darstellung von Verzweigungen und allgemeinen Programmstrukturen wurden schon sehr
früh graphische Repräsentationen (visuelle Sprachen) eingesetzt, die später auch genormt wurden:
•
Programmablaufpläne (und Datenflusspläne) nach DIN 66001
•
Nassi-Shneiderman Diagramme nach DIN 66261
•
Jackson-Diagramme
•
UML Diagramme (hier allein 14 verschiedene Diagrammarten)
Betrachten wir dies näher.
2.2.1
Programmablaufpläne
Ein Programmablaufplan ist ein Ablaufdiagramm für ein Computerprogramm, das auch als
Flussdiagramm (engl. flowchart) oder Programmstrukturplan bezeichnet wird. Das Konzept der Programmablaufpläne stammt aus den 60er-Jahren. Es besteht aus graphischen Einheiten (Rechtecke für Befehlsfolgen, Rauten für Entscheidungen, etc.) und Pfeilen dazwischen, die den Befehlsfluss symbolisieren.
Hauptkritikpunkt an Programmablaufplänen ist, dass
•
sie schon bei mittelgroßen Algorithmen schnell unübersichtlich. werden und
•
sie zur Verwendung von expliziten Sprunganweisungen (GOTO's) verführen und damit die Produktion von "Spaghetti-Code" fördern und
5
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
•
gut strukturierter Programmcode (ggf. als Pseudocode oder in einer Skriptsprache wie
Python) relativ einfach direkt zu schreiben und zu verändern ist und dabei auch übersichtlich strukturiert werden kann.
•
Wenn man zwei Repräsentationen des Programms benutzt (Quellcode) und einen
Programmablaufplan, so ist es aufwendig, diese konsitent zu halten: Korrigiert man einen Fehler oder macht eine Ergänzung im Programm selbst, müsste dies natürlich im
Ablaufplan „nachgezogen“ werden.
Tatsächlich werden Programmablaufpläne heute in der Softwareentwicklung kaum noch eingesetzt. Sie erleben allerdings in etwas modifizierter Form eine Renaissance in MultimediaEntwicklungsprozessen und sind eben gut geeignet, elementare Strukturen der Programmierung
zu verdeutlichen.
2.2.2
Nassi-Shneiderman-Diagramme
Ein Nassi-Shneiderman-Diagramm (auch Struktogramme genannt) ist ein SoftwareEntwurfshilfsmittel (auch Methode) für die strukturierte Programmierung. Es ist genormt nach
DIN 66261. Benannt wurde es nach seinen Vätern Ike Nassi1 und Ben Shneiderman2.
Die Methode zerlegt ein Gesamtproblem, das man mit dem gewünschten Algorithmus lösen
will, in immer kleinere Teilprobleme bis schließlich nur noch elementare Grundstrukturen wie
Sequenzen und Kontrollstrukturen zur Lösung des Problems übrig bleiben. Die beiden Autoren
konnten mit ihren Diagrammen nachweisen, dass in keinem Algorithmus ein unbedingter
Sprung (GOTO) benötigt wird.
In dieser Vorlesung werden wir Programmablaufpläne und Nassi-Shneiderman-Diagramme nur
dazu benutzen, elementare Grundstrukturen zu visualisieren, weil diese hoffentlich so einprägsamer sind.3
Verzweigungen werden folgendermaßen visualisiert:
1
Homepage von Ike Nassi (http://www.nassi.com/ike.htm)
2
Homepage von Ben Shneiderman (http://www.cs.umd.edu/~ben/)
Wer trotzdem einmal versuchen will, verschiedene Diagrammarten auszuprobieren, der sei auf das Web verwiesen. Hier gibt es zahlreiche hilfreiche Freeware oder Public Domain Programme:
Hus Struktogrammer (http://www.lunabits.net/nette-freeware-tools/index.html#hus)
StruktEd ()
Nassi-Shneiderman Diagram-Editor (http://www.strukted.de/)
Struktogrammeditor (http://www.learn2prog.de/)
Software für Struktogramme und Ablaufdiagramme (http://www.tinohempel.de/info/info/infocd/index2.htm#Klasse%2012/II)
Struktogramme erzeugen (Macros und Symbolleiste für MS Word)
( http://www.dsw2.de/Randprodukte.html)
3
6
V O R L E S U N G 4 :
Verzweigungsart
K O N T R O L L S T R U K T U R E N
Programmablaufplan
Nassi-Shneiderman
einfach-einseitig
if <Bedingung>
then
<Block 1>
endif
wahr
wahr
Bedingung
Bedingung
falsch
leer
Block 1
Block 1
einfach-zweiseitig
if <Bedingung>
then
<Block 1>
else
<Block 2>
endif
wahr
Bedingung
falsch
wahr
Bedingung
falsch
Block 2
Block 1
Block 1
Block 2
mehrfach
case <Variable>
Wert 1: <B1>
Wert 2: <B2>
...
otherwise: <Bn>
endcase
Wert 1
B1
Variable
=
Wert 2
sonst
Bn
B2
Wert1
1
Wert2
B1
B2
Variable =
sonst
Bn
Sie können jetzt selbst entscheiden, wie hilfreich diese Art der Darstellung sein kann. Die meisten Programmierer bevorzugen heute so genannten „Pseudocode“ oder formulieren zum Prototyping direkt in Skriptsprachen wie z.B. Python.
2.2.3
Jackson-Diagramme
Jackson-Diagramme sind eine Alternative zu Nassi-Shneiderman. Sie sind Bestandteil einer
Methode, die der Theoretiker Michael A. Jackson in den Jahren 1975 bis 1979 entwickelt hat.
Das Jackson-Diagramm stellt den Programmentwurf in hierarchischer Form dar, ähnlich einem
Organigramm. Das Gesamtprogramm wird in schrittweiser Verfeinerung bis zu den Einzelfunktionen heruntergebrochen. Die Komponenten des Diagramms sind einfache Rechtecke, die
durch Pfeile verbunden sind. Es gibt nur drei Arten von graphischen Symbolen (alles Rechtecke):
•
Ein Rechteck ohne weitere Markierung kennzeichnet einen einfachen Funktionsblock,
der einmal durchgeführt wird.
7
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
•
Ein Rechteck mit einem Stern (*) in der rechten oberen Ecke kennzeichnet eine Funktion, die wiederholt durchlaufen wird.
•
Ein Rechteck mit einem Kreis (o) in der rechten oberen Ecke kennzeichnet eine von
mehreren Alternativen.
Zur Darstellung des Programmablaufs ist das Jackson-Diagramm funktionell äquivalent zum
Nassi-Shneiderman-Diagramm. Das Nassi-Shneiderman-Diagramm wächst mit der Verfeinerung nach innen, das Jackson-Diagramm wächst nach unten und außen. Es ist lediglich eine
Geschmacksfrage, welche der beiden Methoden man bevorzugt.
Beide Methoden hatten ihre Blütezeit in den 1970er und 1980er-Jahren, als die strukturierte
prozedurale Programmierung die Technik der Wahl war. Mit dem Aufkommen objektorientierter Programmiersprachen in den 1990er Jahren verloren beide Methoden an Bedeutung, weil
sie die erweiterten Möglichkeiten, die diese Sprachen bieten, nicht adäquat abbilden können.
2.2.4
Unified Modeling Language
UML: In der heutigen Zeit ist als graphische Beschreibungssprache die Unified Modeling
Language ("vereinheitlichte Modellierungssprache", häufig mit UML abgekürzt) aktuell. Sie ist
eine von der Object Management Group (OMG, siehe http://www.omg.org/ ) entwickelte und
standardisierte Beschreibungssprache, um Strukturen und Abläufe in objektorientierten Softwaresystemen darzustellen und unterstützt deshalb vorwiegend die objektorientierte Programmierung.. OMG™ ist eine internationale, frei zugängliches gemeinnütziges (not-for-profit) Computer Industrie-Konsortium. Im Sinne einer Sprache definiert die UML dabei Bezeichner für die
meisten Begriffe, die im Rahmen der Objektorientierung entstanden sind, und legt mögliche
Beziehungen zwischen diesen Begriffen fest. UML definiert des Weiteren grafische Notationsweisen für diese Begriffe und für Modelle von Software oder anderen Abläufen, die man in diesen Begriffen formulieren kann. Damit wurde die UML zur de-Facto-Norm für "technische
Zeichnungen" von Programmen und Abläufen. Sie standardisiert jedoch nicht nur die technische Zeichnung selbst, sondern auch das Datenformat, in dem diese Zeichnung in EDVSystemen abgelegt wird (sog. XMI, eine XML-Variante). Dadurch ermöglicht es die UML im
Prinzip, Modellierungsdaten zwischen Modellierungswerkzeugen unterschiedlicher Softwarehersteller auszutauschen.
Die Väter der UML sind Grady Booch, Ivar Jacobson und James Rumbaugh (auch "die drei
Amigos" genannt). UML wurde am 1997 von der OMG (Object Management Group) als Standard akzeptiert, nachfolgend von ISO Standard akzeptiert (ISO/IEC 19501, in der Version
1.4.2) und wird seit dem von der OMG weiterentwickelt. Die aktuelle Version ist UML 2.0
(noch nicht vollständig abgestimmt). UML 2.0 hat 4 Teile:
Superstructure,
Infrastructure,
Object Constraint Language (OCL) und
Diagram Interchange.
Zur Darstellung von Strukturen unterstützt die Unified Modeling Language 2.0 insgesamt 13 +1
Diagrammtypen:
•
Strukturdiagramme
o
o
o
Klassendiagramm (engl. class diagram)
Objektdiagramm (engl. object diagram)
Komponentendiagramm (engl. component diagram)
8
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
•
Kompositionsstrukturdiagramm (auch: Montagediagramm, engl. composite structure diagram)
o Verteilungsdiagramm (engl. deployment diagram)
o Paketdiagramm (engl. package diagram)
•
Verhaltensdiagramme
o
o
o
o
o
o
o
•
Anwendungsfalldiagramm und Anwendungsfalldiagramm (UML2) (auch: Nutzfalldiagramm, engl. use case diagram)
Zustandsdiagramm (engl. statechart)
Aktivitätsdiagramm (engl. activity diagram)
Sequenzdiagramm (UML2) (engl. sequence diagram)
Interaktionsübersichtsdiagramm (engl. interaction overview diagram)
Kommunikationsdiagramm (engl. communication diagram)
Zeitverlaufsdiagramm (engl. timing diagram)
Kollaborationsdiagramme (nicht zu verwechseln mit den gleichnamigen Diagrammen in
UML 1.x, die in UML 2.0 Kommunikationsdiagramme heißen). Sie stellen einen abstrakten
strukturellen Zusammenhang dar (z.B. zur Dokumentation von Entwurfsmustern) und ähneln den "Collaborations" der Catalysis-Methode.
Es würde hier viel zu weit führen, diese verschiedenen Diagramme zu behandeln, zumal sie in
vielerlei Hinsicht mit den objektorientierten Entwurfsmethoden direkt verknüpft sind. In PRG2 werden Sie einige Diagrammarten kennen lernen.
Alle Diagrammarten sind „Kinder Ihrer Zeit“; spiegeln also direkt die verschiedenen Programmiersprachen-Generationen und Programmierparadigmen wider:
Programmablaufpläne
Generation 1 und 2 (Formular Translation)
mit GOTO, siehe unten.
Nassi-Shneiderman Diagramme
Jackson Diagramme
Strukturiertes Programmieren – Generation 3
Vermeidung von GOTO
UML Diagramme
Objektorientierte Programmierung
3 Iterative Grundstrukturen
Die fallbasierte Verzweigung reicht nicht aus, alle Anwendungen zu implementieren. Man muss
auch sehr viele sehr ähnliche Befehle im linearen Befehlsfluss durchführen, die man leichter als
eine wiederholte Sequenz beschreibt als sie wiederholt hinzuschreiben.
3.1 Schleifen in Python: for und while
Wiederholte Aktionen, also Schleifen, werden in Python mit Hilfe der while- und forAnweisungen implementiert. Für while ist dies in der Form
while expression:
suite
[else:
suite]
Die while-Anweisung wird solange ausgeführt, bis die dazugehörige Bedingung zu „false“
ausgewertet wird. Die Syntax dazu lautet:
9
V O R L E S U N G 4 :
while_stmt
K O N T R O L L S T R U K T U R E N
::=
"while" expression ":" suite
["else" ":" suite]
Die for-Anweisung ist von der Form:
for target in sequenz:
suite
[else:
suite]
Die for-Anweisung ist eine Schleife über Sequenzen einer expression_list. Sie weist die
Elemente in expression_list nacheinander der target_list zu und führt dann jedes Mal
die erste suite aus. Optional kann zum normalen Abschluss der Schleife die else : suite
ausgeführt werden.
for_stmt
::=
expression_list ::=
"for" target_list "in" expression_list ":" suite
["else" ":" suite]
expression ( "," expression )* [","]
target darf alles sein darf, was links von einem Zuweisungsoperator stehen darf, also einfache
Variablen, Tupel (x,y,z), etc.
target_list
target
::=
::=
target ("," target)* [","]
identifier
| "(" target_list ")"
| "[" target_list "]"
| attributeref
| subscription
| slicing
Die Mächtigkeit der Python for-Schleife rührt daher, dass die Sequenz S durch einen beliebigen
Sequenzdatentyp (insbesondere dann macht die for-Schleife Sinn) repräsentiert wird, also entweder ein String, eine Liste, ein Tupel oder eine Menge (set). Man kann als expression also
eine beliebige Variable eines solchen Typs angeben, dann wird über alle Elemente iteriert. Es
können aber auch Teilbereiche angegeben werden, durch Indizierung oder wichtiger durch
Teilbereichsbildung (Slicing), die zusammenhängende Bereiche einer Sequenz extrahiert: Die
Bereichsgrenzen sind mit 0 und der Sequenzlänge vorbelegt:
•
S[1:3] geht von Index 1 bis ausschließlich 3 (also 2)
•
S[1:]
•
S[:-1] nimmt alles bis auf das letzte Element (negative Indizes zählen vom Ende)
geht vom Index 1 bis zum Ende
Auch erweiterte Teilbereichsbildung S[i:j:k] ist zulässig: Das dritte Element k ist die Schrittweite:
•
S[::2] ergibt jedes zweite Element der Sequenz S von 0 bis zum Ende
•
S[::-1] ergibt die Umkehrung der Sequenz
•
S[4:1:-1] holt Elemente von rechts nach links ab Position 4 (inklusive) bis Position 1
(exklusive) ab.
Insbesondere sind als Sequenz natürlich auch Literale zulässig:
10
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
"Ein Text"
"Ein" "zusammengesetzter" "Text"
u"Ein Unicode Text"
[1,2,3,4] eine Liste
["spam", 42, 1.35] eine andere Liste
(1,2,3,4) ein Tupel mit vier Elementen
Einige wenige Beispiele mögen das verdeutlichen:
>>> for x in "Ein Text":
print x
E
i
n
T
e
x
t
>>> for x in "Ein Text"[::-1]:
print x
t
x
e
T
n
i
E
Im Zusammenhang mit Listen sind gerade für for-Schleifen sogenannte
•
Generator-Ausdrücke (und List-Comprehension-Ausdrücke)
und die eingebaute Funktion
•
range ([start,]stop [,step]
interessant.
range liefert eine Liste von aufeinander folgenden Integern zwischen start und stop. Mit nur einem Parameter (stop) ergeben sich die Zahlen 0...stop-1. step ist optional und ist die Schrittweite:
range (0,20,2) ist eine Liste von geraden Zahlen von 0 bis 18.
Beispiel für einen Parameter:
>>> for x in range (4):
print x
0
1
2
3
Beispiel für drei Parameter:
11
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
>>> for x in range (2,10,2):
print x
2
4
6
8
Ein Generator-Ausdruck erzeugt die Elemente in Iterationen einzeln.
(x ** 2 for x in range (4))
Ein List-Comprehension-Ausdruck (list_display) ist eine Listenabstraktion und sammelt
alle Werte eines Ausdrucks für jede Iteration über for Schleifen für die die (optionale) Bedingung wahr ist. Im Gegensatz zum Generator werden die Elemente nicht nur einzeln in der Iteration generiert, sondern als „physikalische“ Liste in ihrer Gesamtheit.
[x ** 2 for x in range (4)]
Beide Formen sind sehr ähnlich, bis auf die äußeren Klammern und liefern in diesem Fall die
gleichen Ergebnisse. Die vollständige Syntax erlaubt noch einiges mehr. Wir besprechen dies in
einer der folgenden Vorlesungen.
Als Beispiel für solche Ausdrücke betrachten wir die Folge der Quadratzahlen:
>>> for x in (x ** 2 for x in range (4)):
print x
0
1
4
9
>>> for x in [x ** 2 for x in range (4)]:
print x
0
1
4
9
Ab Python Version 2.2 versucht der Interpreter mit iter(expression_list)ein IteratorObjekt zu bekommen und dann deren Methode next() wiederholt aufzurufen, bis eine Exeption (StopIteration) ausgelöst wird. Wenn kein Iterator-Objekt existiert (die Methode __iter__
nicht definiert ist), wird stattdessen expression_list mit steigenden Positionen indiziert, bis
ein IndexError ausgelöst wird.
Die for-Anweisung iteriert solange über alle Elemente einer Sequenz, bis keine Elemente mehr
verfügbar sind.
Man darf auch über Sequenzen von Tupeln (auch ggf. verschieden langen) iterieren. Beachten
Sie, dass in target alles stehen darf, was auf der linken Seite des Zuweisungsoperators stehen
darf. Wenn alle Elemente der Sequenz aus Tupeln gleicher Länge bestehen, kann folgende Variante der for-Anweisung benutzt werden:
12
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
for x, y, z in s:
In diesem Fall muss s eine Sequenz von dreistelligen Tupeln sein. In jeder Iteration wird den
Variablen x, y und z der Inhalt des entsprechenden Tupels zugewiesen.
3.2 break – continue - else
Um eine Schleife (while oder for) abzubrechen, verwendet man die break-Anweisung. Die
Funktion im folgenden Beispiel gezeigt werden. Im Beispiel werden solange Eingabezeilen vom
Benutzer gelesen, bis eine leere Zeile eingegeben wird:
>>> while 1:
cmd = raw_input('Befehl eingeben > ')
if not cmd:
break
else:
print cmd
Befehl eingeben > bla bla bla
bla bla bla
Befehl eingeben >
Anmerkung zum obigen Beispiel: raw_input ([prompt]) ist eine weitere eingebaute Funktion,
die Folgendes leistet:
1. Sie druckt den String prompt aus, wenn angegeben,
2. liest dann eine Zeile von sys.stdin und gibt sie als String zurück..
Mit diesem kleinen Codestück können wir also Eingaben vom Benutzer erfragen.
Um in die nächste Schleifeniteration zu springen (wobei der Rest des Schleifenrumpfes übersprungen wird) verwendet man die continue-Anweisung. Diese Anweisung wird weniger häufig verwendet, ist aber nützlich, wenn die Umkehr des Testes und die Einrückung um eine weitere Stufe das Programm zu sehr verschachteln oder verkomplizieren würden. Als Beispiel gibt
die folgende Schleife nur die nicht-negativen Elemente einer Liste aus:
>>> s = [-1,7,0,-2]
>>> for a in s:
if a < 0:
continue # Überspringe negative Elemente
print a
7
0
Die break- und continue-Anweisungen gelten nur in der innersten Schleife, die gerade ausgeführt wird. Falls es notwendig ist, aus einer tief verschachtelten Schleife „auszubrechen“, kann
man eine Ausnahme verwenden. Python stellt keine goto-Anweisung zur Verfügung.
Die else-Anweisung kann auch an Schleifen angefügt werden:
while i < 4:
print i
i = i + 1
13
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
else:
print 'Erledigt'
s = [-1,7,0,-2]
for a in s:
if a == 1:
break
else:
print 'Nicht gefunden!'
>>>
Erledigt
Nicht gefunden!
Die else-Klausel einer Schleife wird nur dann ausgeführt, wenn die Schleife bis zum Ende
ausgeführt wird. Das passiert entweder sofort (wenn die Schleife überhaupt nicht ausgeführt
wird) oder nach der letzten Iteration. Falls die Schleife jedoch frühzeitig mit der breakAnweisung beendet wird, wird auch die else-Klausel übersprungen.
3.3 Realisierungsformen der Iteration
In Programmiersprachen werden iterative Lösungen aller Art allgemein durch Schleifen realisiert: Eine Schleife ist eine Kontrollstruktur in imperativen Programmiersprachen. Sie wiederholt einen Teil des Codes – den so genannten Schleifenrumpf oder Schleifenkörper – so lange, bis eine Abbruchbedingung eintritt. Schleifen, die ihre Abbruchbedingung niemals erreichen oder Schleifen, die keine Abbruchbedingungen haben, nennen wir Endlosschleifen.
Eine Endlosschleife kann nur von „außen“ unterbrochen werden, etwa durch ein Zurücksetzen
(engl. reset), durch eine Unterbrechung (engl. interrupt), in Programmiersprachen durch Ausnahmen (engl. exeptions), Abschalten des Gerätes oder ähnliches. Oft, aber nicht immer, ist eine
Endlosschleife ein Programmierfehler, weil das Programm nicht normal beendet werden kann.
Ist die Aufgabe des Programms jedoch z.B. eine Überwachung Prozessen und Reaktion auf
einen externen (gemeldet durch einen Interrupt) oder internen Fehlerzustand (gemeldet durch
eine Exeption), oder die dauernde Regelung von Echtzeitprozessen in der Industrie, so kann dieses Verhalten gewollt sein. Grundsätzlich ist aber bei Endlosschleifen VORSICHT geboten!
Prinzipiell unterschieden wir
•
die kopfgesteuerte oder vorprüfende Schleife, bei der erst die Abbruchbedingung
geprüft wird, bevor der Schleifenrumpf durchlaufen wird. Meist durch das Schlüsselwort WHILE (= solange-bis) angezeigt.
•
die fußgesteuerte oder nachprüfende Schleife, bei der nach dem Durchlauf des
Schleifenrumpfes die Abbruchbedingung überprüft wird, z.B. durch ein Konstrukt
REPEAT-UNTIL (= wiederholen-bis).
•
die Zählschleife, eine Sonderform der kopfgesteuerten Schleife, meist als FOR
(= für ) -Schleife implementiert.
Die Abbruchbedingung wird meist durch Vergleichsoperatoren und/oder logische Ausdrücke
gesteuert. Bei der letzten Gruppe, der Zählschleifen, unterscheiden wir drei verschiedene Arten:
14
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
(1) Die „Algol-artige“ For-Schleife: Diese Art der For-Schleife dient in erster Linie dazu, eine
Anweisung wiederholt auszuführen. Sie hat folgende Eigenschaften:
Die Anzahl der Wiederholungen stehen schon beim Eintritt in die Schleife fest.
Es gibt eine so genannte Schleifenvariable, die am Anfang auf den Startwert gesetzt wird
und dann jeweils um die Schrittweite verändert wird, bis der Zielwert erreicht ist. Die
Schleifenvariable, der Startwert, die Schrittweite und der Endwert müssen numerisch
sein.
Bei jedem Schritt wird die Anweisung ausgeführt.
(2)
In „C-artigen“ Programmiersprachen hat eine For-Schleife die Form:
for (Initialisierung; Test; Fortsetzung) Anweisung
Hier kann man während der Abarbeitung die Werte der Variablen in dem Test verändern,
so dass die Anzahl der Wiederholungen dynamisch sein können.
(3) Einige Programmiersprachen (zum Beispiel Perl, Python, PHP) bieten ein Konstrukt an,
um einer Variablen nacheinander alle Elemente einer Liste zuzuweisen.
Eine Variante der for-Schleife ist die Foreach-Schleife und hat die Form:
foreach Variable (Werte) { Anweisungen }
Bis auf die rein funktionalen und logischen Programmiersprachen (diese brauchen keine Schleifen) realisieren alle modernen Programmiersprachen eine Auswahl der hier dargestellten Grundstrukturen. Sie unterscheiden sich in den benutzten Schlüsselwörtern, der Art der Klammerung
der Programmblöcke, z.B. ( ), { }, begin ... end, etc. und des Typs der Laufvariablen sowie deren „Inkrementierung“. Mit Python haben wir hier eine sehr leistungsfähige Variante kennen
gelernt.
Schleifenkonstrukte können ähnlich wie Verzweigungskonstrukte gut visualisiert werden.
Schleifenart
Programmablaufplan
Nassi-Shneiderman
vorprüfend
while (B) do
Block
B
falsch
B
Block
wahr
Block
15
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
nachprüfend
repeat Block
Block
Block
until (B)
B
falsch
wahr
B
Zählschleife
C=1
C=1
for(C=1;B;C++)do
Block
falsch
B
B
wahr
C++
Block
Block
C++
Ein kleine historische Notiz zum Befehl GOTO: Noch in den 60er-Jahren waren Sprunganweisungen der Form GOTO <Sprungziel> in Programmen üblich, was bei größeren Programmen nahezu zur Unwartbarkeit führte, da sie schnell kaum noch überschaubar wurden. Das GOTO <Sprungziel>
ist eine direkte Abbildung des Maschinenbefehls JUMP <Sprungziel>. Lediglich musste nun das
Sprungziel keine Programmadresse mehr sein, sondern konnte symbolisch als Zahl oder Name angegeben werden.
Ein Beispiel für so genannten Spaghetti-Code mit GOTO-Anweisungen ist folgendes kleine Programm zur Rettung einer Jungfrau:
20
40
60
70
GOTO 40
UmgeheDasProblem
GOTO 70
if (Durcheinander > TödlicheDosis) then GOTO 60
GOTO 20
RetteJungfrau
...
Ist jetzt klar , was man tun soll? Besser dafür ist allerdings die strukturierte Fassung:
IF ((Durcheinander > TödlicheDosis)
THEN RetteJungfrau
ELSE UmgeheDasProblem
Beurteilen Sie selbst, was leichter verständlich und damit wahrscheinlich weniger fehlerhaft, auf jeden
Fall aber besser wartbar ist.
Schon im Mai 1966 publizierten Böhm und Jacopini in der Zeitschrift Communications of the ACM einen
Artikel, in dem sie zeigten, dass jedes Programm, das GOTO-Anweisungen enthält, in ein GOTO -
16
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
freies Programm umgeschrieben werden kann, das nur mit Verzweigung (IF <Bedingung> THEN ...
ELSE ... ) und einer Schleife (WHILE <Bedingung> DO xxx) arbeitet, gegebenenfalls unter Zuhilfenahme von etwas Kodeduplikation und der Einführung von booleschen Variablen (true/false). In der
gleichen Zeitschrift veröffentlichte im März 1968 Edsger W. Dijkstra seinen legendären Aufsatz
„Go To Statement Considered Harmful“ (Dieser Aufsatz ist das READING dieser Woche!)
Anfang der 70er Jahre wurde damit begonnen, diesen Ansatz zur Selbstbeschränkung auf wenige, typische Elemente umzusetzen. Wegweisend war die Arbeit von Niklaus Wirth mit seiner Programmiersprache Pascal. Die so genannte strukturierte Programmierung etablierte sich und war bis Anfang der
90er Jahre der State-of-the-Art.
Jede Kontrollstruktur besteht wenigstens aus einem Anfangs- und meistens einem Endschlüsselwort. Sprachen wie Pascal, C, Modula-2 (und auch neuere Varianten der Sprache BASIC)
verfügen über Kontrollstrukuren für Wiederholungen. Die Anweisungsblöcke werden durch
Klammern ( ), {} oder Schlüsselwörter begin ... end zusammengefasst.
Das Programm erhält dadurch eine einfach zu überschauende Struktur. Meist wird diese durch
Einrückungen noch verdeutlicht oder man auf die Klammerung und arbeitet nur mit Einrückungen, wie in Python. Die Schlüsselwörter, die Klammerung und die Formatierung erleichtern das Verständnis des Programmcodes.
3.4 Schleifen in anderen Programmiersprachen
In allen Programmiersprachen existiert die Möglichkeit, Befehle iterativ auszuführen.
Sprache
Schleifen
Python
for ziel in sequenz:
…
[else:
…]
Anmerkungen
while ziel in sequenz:
…
[else:
…]
C, C++
continue
beendet die Schleife
break
geht zum Anfang der Schleife
und setzt fort
pass
Platzhalter
for (expression; expression;
expression)
...;
while (expression)
...;
do
...
while (expression);
continue;
break;
Auch C hat das noch!
17
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
goto label;
Java
for (Startwert;Endbedingung;
Anweisung) {
...
};
Zählschleife
while (Bedingung) {
...
};
Vorprüfung
do {
...
} while (Bedingung);
Nachprüfung
do [schleifenvariable anfangsFortran
90/95 (2003) wert, endwert, schrittweite]
...
[if (<log.Ausdruck> )cycle]
[if (<log.Ausdruck> )exit]
...
end do
geht zum Anfang der Schleife
und setzt fort
Schleife verlassen
do while (<log.Ausdruck>)
...
end do
Pascal
GOTO <label>
for Variable := Startwert
[to|downto] Endwert do … ;
Gibt es tatsächlich immer noch!
while <log.Ausdruck> do
begin
…
end;
repeat
…
until <log.Ausdruck>;
goto <label>.
3.5 Iteration als Lösungsmethode
Die Iteration (von lateinisch iterare, "wiederholen"; engl. iteration) ist ein grundlegender Lösungsansatz sowohl in der Mathematik als auch der Informatik mit zwei verschiedenen Ausprägungen:
1. Iteration (in Mathematik und Informatik) ist eine Methode, sich der Lösung eines Rechenproblems schrittweise, aber zielgerichtet anzunähern. Sie besteht in der wiederholten Anwendung des selben Rechenverfahrens. Meistens iteriert man mit Rückkopplung: Die Ergebnisse
eines Iterationsschrittes werden als Ausgangswerte des jeweils nächsten Schrittes genommen bis das Ergebnis (beziehungsweise Veränderung einer Bestandsgröße) zufrieden stellt. Manch-
18
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
mal setzt man auch den nächsten Schritt aus den Ergebnissen der vorherigen zwei Schritten
(oder von noch mehr Schritten) an, zum Beispiel bei der Regula Falsi, siehe unten.
2. In der Informatik wird auch von Iteration gesprochen, wenn ein wiederholter Zugriff auf
Einzelelemente eines zusammengesetzten (aggregierten) Datentyps, etwa Sammlungen (engl.
collections) erfolgt. Beispiel: In einem String “otto“ sollen alle Kleinbuchstaben durch Großbuchstaben ersetzt werden zu “OTTO“. Dazu wird wiederholt auf den String mit veränderten Indexwert zugegriffen, er wird „iteriert“. Eine besondere Bedeutung hat dieses Vorgehen bei
Sammlungen und Strukturen wie Felder (engl. arrays), Listen, Schlüssel-Wert-Paaren (engl. Maps,
Hashes, Dictionaries) oder Mengen (engl. Sets), die wir allerdings detailliert erst demnächst kennen
lernen werden.
Zu 1. Wenn man ein Rechenproblem iterativ lösen will, so muss man sicher sein (beweisen!),
dass die Iterationsfolge konvergiert und dass der Grenzwert mit der gesuchten Lösung übereinstimmt. Die Geschwindigkeit der Konvergenz ist ein Maß dafür, wie brauchbar die Iterationsmethode ist. Grundsätzlich wird ein iteratives Lösungsverfahren dann eingesetzt, wenn das
Ergebnis nicht geschlossen berechenbar ist (zum Beispiel Gleichungen mit transzendenten
Funktionen: sin x + cos x = x, Bestimmung der Nullstellen ab dem Polynomgrad 5, etc.).
Häufig ist eine gute Näherung schon befriedigend. Speziell bei Anwendungsproblemen können
z.B. die Eingabedaten prinzipiell ungenau sein (Messfehler) oder die Parameter der analytischen
Lösung nicht direkt messbar. Dann ist die exakte Lösung des gegebenen Problems nicht notwendigerweise besser als ihre Approximation oder sogar überhaupt nicht verfügbar. Das Iterationsverfahren ist also dann attraktiv, wenn es eine gute Näherung schneller liefert, als die Berechnung der „exakten“ Lösung brauchen würde oder die exakte Lösung nicht existiert.
Denken Sie in diesem Zusammenhang z.B. auch an die prinzipielle Ungenauigkeit von Gleitkommazahlen: Genauer muss und kann man eben nicht rechnen, und so kann die Lösung durchaus mit einer geeigneten iterativen Approximation erfolgen.
3.6 Beispiel für iterative Approximation: die Regula Falsi
Betrachten wir zur Illustration der Notwendigkeit von Approximationen als klassisches Beispiel
die Regula Falsi, genannt die „Regel des falschen Ansatzes“. Hierbei handelt es sich um das
Problem, die Nullstelle (Wurzel) eines Polynoms zu bestimmen. Dies ist iterativ oft rascher gefunden als mit exakten, geschlossenen Formeln.
Dazu wählen wir folgendes Vorgehen:
1. Schritt: Durch Schätzen oder Probieren ermittelt man ein Intervall (a0, b0) wo eine Nullstelle
von y = f(x) ungefähr liegen könnte, z.B. dadurch, dass f(a0)>0, f(b0)<0
2. Schritt: Einen besseren Wert c0 berechnen wir mit der Regula Falsi, die als Näherung ein gerades Kurvenstück annimmt:
c k = a k −1 + ∆ = a k −1 + f (a k −1 ) ⋅
b k −1 − a k −1
f (b k −1 ) − f (a k −1 )
Nun setzte man
a k = c k , b k = b k −1
wenn f (a k −1 ) und f(c k ) gleiches Vorzeichen haben oder
a k = c k −1 , b k = b k
wenn f (b k −1 ) und f(c k ) gleiches Vorzeichen haben.
19
V O R L E S U N G 4 :
K O N T R O L L S T R U K T U R E N
Diese Schritte wiederholen wir mit ansteigenden Index k, bis uns das Ergebnis „genügend genau“ ist und haben mit ck eine Näherung für eine Nullstelle gefunden.
Zur Herleitung dieser Formel beachte den Strahlensatz. Es gilt:
∆
f (ak −1)
=
und damit
bk −1 − ak −1 f (bk −1) − f (ak −1)
ck = ak −1 + ∆ = ak −1 + f (ak −1 ) ⋅
bk −1 − ak −1
f (bk −1 ) − f (ak −1)
∆
f ( bk −1 ) − f (ak −1 )
bk −1 − ak −1
Start a0, b0
1. Iteration: Berechne c1, f(c1)>ε
Berechne a1, b1
2. Iteration: Berechne c2, f(c2)>ε
Berechne a2, b2
3. Iteration: Berechne c3, f(c3)>ε
20
V O R L E S U N G 4 :
Berechne a3, b3
K O N T R O L L S T R U K T U R E N
3. Iteration: Berechne c4, f(c4)<ε: Ende.
Abbildung 1 Veranschaulichung der Regula Falsi
Es liegt auf der Hand, dass es mit einem derartigen Vorgehen diverse grundsätzliche Probleme
gibt, wie die schon angesprochene Konvergenz, die Vollständigkeit der Lösungsmenge, Fortpflanzung von Rundungsfehlern, etc. Diese Problembereiche werden insbesondere in der Numerischen Mathematik behandelt (siehe dort). In der Praxis sind aber iterative Lösungsmethoden trotzdem grundsätzlich sehr, sehr wichtig!
4 Reading
Edsger W. Dijkstras legendärer Aufsatz „Go To Statement Considered Harmful“ aus dem
Jahre 1968, der den Grundstein für die Strukturierte Programmierung legte.
5 Hinweise zu Programmierkursen
Im Internet finden Sie unzählige Angebote. Wenn Sie sich mit anderen Programmiersprachen vertiefend auseinandersetzen wollen (das gehört allerdings nicht zum Inhalt von
PRG-1) empfehle ich folgende Kurse, was nicht heißen soll, dass diese die Besten sind:
Fortran 90/95 siehe Heidrun Kolinsky: Programmieren in Fortran 90/95
http://www.rz.uni-bayreuth.de/lehre//fortran90/index.html
C/C++ siehe Knut Reinert: Programmierkurs C/C++ http://www.inf.fu- berlin.de/inst/agbio/file.php?p=ROOT/Teaching/Lectures/WS0506/05,programmierung.lecture.htm
Java siehe Dietrich Boles: Programmierkurs Java http://www.programmierkurs-java.de/
21