Studienvorkurs Informatik · Java-Code dient primär dazu in strukturierter Weise als Mensch die gewünschten ... ohne einen übergebenen Text in Zeile 3 erzeugt also lediglich eine

Institut für Informatik

Skript

Studienvorkurs Informatik

Prof. Dr. Michael Brinkmeier

Dr. Nils Haldenwang

Wintersemester 2017

Inhaltsverzeichnis

1 Erste Schritte in der Programmierung 11.1 Hallo Welt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Zahl einlesen und wieder ausgeben . . . . . . . . . . . . . . . . . . . . 21.3 Einfache Rechenoperationen . . . . . . . . . . . . . . . . . . . . . . . 51.4 Bedingte Verzweigungen . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Schleifen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.6 Fehlermeldungen verstehen und beheben . . . . . . . . . . . . . . . . 8

2 Algorithmen nachvollziehen 152.1 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Struktogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3 Schildkrötengrafiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Algorithmen entwickeln 233.1 Maximum finden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Sortierte Suche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1 Erste Schritte in der Programmierung

In diesem Kapitel werden die technischen Grundlagen zur ProgrammierspracheJava1 dargestellt. Ziel dieser Lektion ist es, dass Sie in die Lage versetzt wer-den mit den grundlegenden Sprachelementen selbst kleine Java-Programme zuschreiben und auszuführen.

1.1 Hallo Welt

In Listing 1 ist das obligatorische HalloWelt-Programm dargestellt. Es gibt denText „Hallo Welt!” auf der Kommandozeile2 aus. Während in vielen Scriptspra-chen nur eine Zeile Code dafür erforderlich ist, wird in Java zusätzlich noch eingewisses Grundgerüst benötigt. Die Hintergründe werden erst später in der Vor-lesung ausführlich dargelegt, für den Moment muss man den Rahmen einfach alsnotwendig akzeptieren.

1 import AlgoTools.IO;2

3 public class HalloWelt {4 public static void main(String[] args){5

6 IO.println("Hallo Welt!");7

8 }9 }

Listing 1: HalloWelt.java

In Zeile 1 werden die sogenannten AlgoTools importiert. Die AlgoTools sind ei-ne vom Algorithmen-Team bereitgestellte Bibliothek, die Ihnen den Umgang mitEin- und Ausgaben ungemein erleichtert, sodass Sie sich auf das Wesentlichekonzentrieren können. Zeile 3 enthält die Klassendefinition. In der Sprache Javamuss jedweder Code in einer Klasse eingebettet werden. Wichtig ist dabei, dassder Klassenname konsistent mit dem Dateinamen ist. Die Klasse HalloWelt mussalso in einer Datei namens HalloWelt.java gespeichert werden. Weiterhin istfestzustellen, dass die Zeile mit einer öffnenden, geschweiften Klammer endet.

1https://docs.oracle.com/javase/8/docs/technotes/guides/language/index.html2https://www.informatik-cms.uni-osnabrueck.de/arbeitsgruppen/didaktik/lehre/studienvorkurs_informatik.html

https://docs.oracle.com/javase/8/docs/technotes/guides/language/index.html

https://www.informatik-cms.uni-osnabrueck.de/arbeitsgruppen/didaktik/lehre/studienvorkurs_informatik.html

https://www.informatik-cms.uni-osnabrueck.de/arbeitsgruppen/didaktik/lehre/studienvorkurs_informatik.html

2 1 Erste Schritte in der Programmierung

Die zugehörige schließende Klammer befindet sich in Zeile 9. Der „Inhalt” derKlasse muss zwischen diesen beiden geschweiften Klammern eingetragen wer-den. In diesem Beispiel - und auch in allen anderen in diesem Vorkurs - bestehtder Inhalt immer aus der in Zeile 4 deklarierten main-Methode. Diese stellt denEinstiegspunkt für das System dar, an dem beim Programmstart die Ausführungbeginnt. Der Eigentliche Programmcode des Programms findet sich schließlich inZeile 6. Mit dem Aufruf IO.println(...) erzeugt man die Ausgabe einer einzel-nen Zeile Text auf der Kommandozeile. Der auszugebende Text wird in doppeltenAnführungszeichen dem Befehl übergeben. Schließlich wird das Ende des Aus-druckes mit einem Semikolon markiert. Alles Ausdrücke im Programm werdenlinear von oben nach unten abgearbeitet.

Java-Code dient primär dazu in strukturierter Weise als Mensch die gewünschtenAlgorithmen für die Maschine verständlich zu formulieren. Damit das Programmvom Prozessor ausgeführt werden kann, muss es zunächst in Maschinensprache,den sogenannten „Bytecode” übersetzt werden. Dies können Sie für das obigeProgramm HalloWelt.java mit dem Befehl

javac HalloWelt.java

erreicht werden. Bei Erfolg entsteht die Datei HalloWelt.class, welche nun denfür den Computer ausführbaren Bytecode enthält. Mit dem Befehl

java HalloWelt

kann das Programm nun ausgeführt werden. Die Ausgabe erscheint dann als:

Hallo Welt!

1.2 Zahl einlesen und wieder ausgeben

Programme sollen oft von außen eingelesene Daten verarbeiten. In diesem Ab-schnitt lernen Sie, wie man auf der Kommandozeile Zahlen vom Nutzer zur wei-teren Verarbeitung einlesen und wieder ausgeben kann. Ein solches Programmist dargestellt in Listing 2.

Bis auf den Klassennamen ist der äußere Rahmen des Programms identisch zudem in Abschnitt 1.1 erläuterten Code. Die relevanten Zeilen sind hier die Zei-len 6 und 7. Ein neues Konzept ist hier zunächst die Variable zahl in Zeile 6.Variablen dienen dazu während des Verlaufs des Programms gewisse Werte zwi-schenzuspeichern. Variablen müssen mit einem Datentyp - in diesem Falle int- deklariert werden, der angibt was für eine Art von Daten sie speichern kön-nen. Der Datentyp int dient zur Repräsentation positiver und negativer ganzer

1.2 Zahl einlesen und wieder ausgeben 3


3 public class LiesZahl {4 public static void main(String[] args){5

6 int zahl = IO.readInt("Bitte eine ganze Zahl: ");7 IO.println(zahl);8

9 }10 }

Listing 2: LiesZahl.java

Zahlen. Mit einem Gleichheitszeichen kann man der Variablen einen Wert zuwei-sen. Der Wert ist in diesem Beispiel das Ergebnis des Aufrufs IO.readInt(...).Dieser Befehl gibt auf der Kommandozeile den übergebenen Text als Frage aus,nimmt vom Benutzer daraufhin eine Zahl entgegen und liefert diese als Ergebnis.Nach Abarbeitung der Zeile 6 ist in der Variablen zahl also die vom Nutzer ein-gegebene Zahl abgespeichert. Der von vorher bekannte Befehl IO.println(...)in Zeile 7 kann nicht nur wie beim Programm HalloWelt.java Text ausgeben,sondern auch die Werte von Variablen, hier den von zahl. Die Ausführung aufder Kommandozeile würde bei der Eingabe der Zahl 42 den folgenden Verlaufhaben:

Bitte eine ganze Zahl: 4242

Zusätzlich zur bloßen Ausgabe der Zahl lässt sich diese auch noch mit Text er-gänzen. Angenommen statt nur 42 auszugeben wolle man „Die Zahl war: 42” aus-geben, dann kann man die Ausgabe in Zeile 7 von Listing 2 mit dem folgendenCode ersetzen:

1 IO.print("Die Zahl war: ");2 IO.print(zahl);3 IO.println();

Beachten Sie, dass in Zeile 1 statt println der Befehl print verwendet wird. DasSuffix ln steht dabei für „line”. Der Unterschied der Befehle liegt also darin, dassnach println eine neue Zeile begonnen wird, nach print nicht. Zeile eins gibtalso ohne Zeilenumbruch den Text „Die Zahl war: ” aus. In Zeile 2 wird wiederumohne Zeilenumbruch die eingegebene Zahl angehängt. Der Befehl IO.println()ohne einen übergebenen Text in Zeile 3 erzeugt also lediglich eine neue Zeile,sodass insgesamt die gewünschte Ausgabe entsteht. Der Effekt lässt sich auchmit dem folgenden, verkürzten Ausdruck erzielen:


1 IO.println("Die Zahl war: " + zahl);

Der Operator + verhält sich je nach Kontext nicht nur wie Sie es aus der Mathe-matik gewohnt sind. Neben der Addition von Zahlen lässt sich damit auch Textmit anderen Daten zur Ausgabe verbinden. Die Ausgabe lautet damit dann also:

Bitte eine ganze Zahl: 42Die Zahl war: 42

1.3 Einfache Rechenoperationen 5

1.3 Einfache Rechenoperationen

Ein Programm, welches zwei Zahlen vom Benutzer einliest, diese addiert undwieder ausgibt ist in Listing 3 dargestellt. Die Zeilen 6 und 7 beinhalten die vonvorher bekannten Befehle zum Einlesen von Daten und abspeichern der Eingabenin Variablen.


3 public class Addieren {4 public static void main(String[] args){5

6 int zahl1 = IO.readInt("Bitte den ersten Summanden: ");7 int zahl2 = IO.readInt("Bitte den zweiten Summanden: ");8

9 int ergebnis = zahl1 + zahl2;10

11 IO.println("Die Summe ist: " + ergebnis);12

13 }14 }

Listing 3: Addieren.java

In Zeile 9 wird eine neue Variable ergebnis angelegt und ihr die Summe derbeiden Eingaben abgespeichert. Beachten Sie, dass Variablen immer möglichstsprechend benannt werden sollten. Man hätte die Variable auch a, b oder x nen-nen können. Für den Leser ist der Zweck der Variablen besser verständlich, wennihr Name diesen bereits andeutet. Da Programmcode immer öfter gelesen als ge-schrieben wird, lohnt es sich immer sprechende Namen zu verwenden. Schließ-lich erfolgt in Zeile 11 die Ausgabe von ergebnis mit einem vorangestellten, be-schreibenden Text. Andere Rechenoperationen wie Multiplikation, Subtraktionund Division lassen sich analog anwenden.

1.4 Bedingte Verzweigungen

Oftmals müssen in Programmen Entscheidungen getroffen werden und in Ab-hängigkeit von Eingaben oder anderen Werten verschiedene Aktionen ausgeführtwerden. Die dafür verwendeten Syntaxelemente nennt man bedingte Verzweigun-gen. Ein Beispielprogramm mit einer einfachen, bedingten Verzweigung findetsich in Listing 4.

In Abhängigkeit der in Zeile 6 eingelesenen Zahl prüft das Programm, ob dieZahl 42 war oder nicht und macht eine entsprechende Ausgabe. Der Ausdruck



3 public class VergleicheZahl {4 public static void main(String[] args){5

6 int zahl = IO.readInt("Bitte eine ganze Zahl: ");7

8 if(zahl == 42){9 IO.println("Die Zahl war 42!");

10 } else {11 IO.println("Die Zahl war NICHT 42!");12 }13

14 }15 }

Listing 4: VergleicheZahl.java

if(zahl == 42) führt den dahinter in geschweiften Klammern stehenden Codenur dann aus, wenn die Bedingung innerhalb der runden Klammern hinter dem iferfüllt ist. Mit dem Operator == wird in diesem Fall der Wert der Variablen zahlmit dem Wert 42 verglichen. Beachten Sie, dass ein einfaches Gleichheitszeichenhier nicht verwendet werden kann, da es in Java der Operator für Zuweisungenist. Für den Fall, dass die Zahl verschieden von 42 ist, soll dies ebenfalls ausgege-ben werden. Mit dem Schlüsselwort else in Zeile 10 lässt sich ein weiterer Falleingeben, der genau dann ausgeführt wird, falls die Bedingung des if-Ausdrucksnicht erfüllt ist.

In vielen Fällen ist es zur Lösung komplexer Verzweigungen mit mehr als zweimöglichen Pfaden zu haben. Ein Beispielprogramm ist in Listing 5 dargestellt.Das Programm ist ähnlich zu dem vorherigen Programm, kann nicht nur ausge-ben, ob die eingelesene Zahl 42 war, sondern auch, ob diese andernfalls größeroder kleiner ist.

Dazu verwendet man den sogenannten else-if-Audruck, bei dem nach dem vonvorher bekannten else direkt ein if mit der zusätzlichen Bedingung folgt. DieAusgabe in Zeile 11 erfolgt also nur dann, wenn die Eingabe nicht 42 war, abersie vom Wert größer als 42 ist. Sollte das auch nicht der Fall sein, dann wirddie Bedingung in Zeile 12 geprüft. Tatsächlich könnte man in Zeile 12 hier dasif auch weglassen, denn wenn eine Zahl weder gleich 42, noch größer 42, dannmuss sie kleiner sein. Dennoch macht es für die Verständlichkeit des ProgrammsSinn explizit die Bedingung auszuformulieren.

1.5 Schleifen 7


3 public class MehrereVergleiche {4 public static void main(String[] args){5

6 int zahl = IO.readInt("Bitte eine ganze Zahl: ");7

8 if(zahl == 42){9 IO.println("Die Zahl war 42!");

10 } else if(zahl > 42){11 IO.println("Die Zahl war groesser als 42.");12 } else if(zahl < 42){13 IO.println("Die Zahl war kleiner als 42.");14 }15

16 }17 }

Listing 5: MehrereVergleiche.java

1.5 Schleifen

Schleifen sind ein Konstrukt, welches für komplexere Algorithmen unabdinglichist. Sie erlauben es Aktionen in Abhängigkeit einer Schleifenbedingung wieder-holt auszuführen. Ein Beispielprogramm ist in Listing 6 dargestellt.

Das Programm liest eine positive Zahl ein, verringert den Wert der Zahl Schritt-weise immer um eins, bis die Zahl 0 ist und gibt alle Zwischenwerte aus. DieAusgabe für die Eingabe 4 würde also lauten:

Bitte eine Zahl > 0: 4321

Der für die Schleife relevante Code findet sich in den Zeilen 9. . . 14. Zunächstwird in Zeile 9 eine Zählvariable angelegt, die zu Beginn auf den Wert der gele-senen Zahl gesetzt wird, also eine Kopie von zahl ist, und im Verlauf der Schleifedann immer um eins verringert wird. Es macht oftmals Sinn nicht direkt mit dereingegebenen Zahl zu arbeiten und diese nicht zu verändern, falls sie im späte-ren Programmverlauf noch verwendet werden soll. Zeile 11 enthält den Schlei-fenkopf der sogenannten while-Schleife. Der Rumpf der Schleife (Code in dengeschweiften Klammern) wird solange ausgeführt, wie die Bedingung im Schlei-fenkopf Gültigkeit hat, also solange der zaehler noch nicht 0 erreicht hat. Die



3 public class Schleifen {4 public static void main(String[] args){5

6 int zahl = IO.readInt("Bitte eine Zahl > 0: ");7

8 int zaehler = zahl;9

10 while(zaehler > 0){11 IO.println(zaehler);12 zaehler = zaehler - 1;13 }14

15 }16 }

Listing 6: Schleifen.java

Bedingung wird vor jedem neuerlichen Durchlauf neu geprüft unter Berücksich-tigung des jeweils aktuellen Wertes von zaehler. Im Schleifenrumpf wird in Zeile10 zunächst der Aktuelle Wert von zaehler ausgegeben. Schließlich muss nochder Wert der Zählervariablen verringert wird, dies geschieht in Zeile 13, indemzaehler ein neuer Wert zugewiesen wird, nämlich zaehler - 1.

1.6 Fehlermeldungen verstehen und beheben

Selbst Erfahrene Programmieren bauen versehentlich verschiedene Fehler in ih-re Programme ein. Syntaktische Fehler kann schon der Compiler erkennen unddiese sind leicht zu beheben. Logische Fehler im Programm kann die Maschinenicht automatisch erkennen, da sie ja nie wissen kann was der Programmierermit seinem Code erreichen wollte. Ein Beispiel für einen syntaktischen Fehler istin Listing 7 dargestellt.

Versucht man die Datei mit javac Fehler1.java zu übersetzen, dann erscheintdie folgende Meldung:

Fehler1.java:8: error: cannot find symbolIO.println(zhal);

^symbol: variable zhallocation: class Fehler11 error

1.6 Fehlermeldungen verstehen und beheben 9


3 public class Fehler1 {4 public static void main(String[] args){5

6 int zahl = IO.readInt("Bitte eine Zahl: ");7

8 IO.println(zhal);9

10 }11 }

Listing 7: Fehler1.java

Die Fehlermeldung verrät zu Beginn der ersten Zeile in welcher Datei der Fehlersich befindet3, gefolgt von der Zeilennummer mit der Zeile, die den Fehler aus-gelöst hat, in diesem Beispiel die Zeile 8. Darauf folgt eine kurze Fehlerbeschrei-bung, „cannot find symbol”, ein Symbol kann nicht gefunden werden. Der Com-piler versucht im folgenden den relevanten Codeabschnitt zu extrahieren undanzuzeigen wo darin der Fehler liegt. Das Symbol „∧” zeigt dabei die FehlerhafteStelle an. Ursache des Fehlers ist in diesm Fall also ein Schreibfehler, in Zeile 8wurde statt zahl versucht die Variable zhal auszugeben, die nicht existiert. Javakann also kein Symbol mit diesem Namen finden.

Ein weiterer häufiger Fehler, der auf den ersten Blick nicht unbedingt zu erken-nen ist, ist in Listing 8 dargestellt.



6 int zahl = IO.readInt("Bitte eine Zahl: ");7

8 if(zahl != 42){9 IO.println("Zahl war nicht 42!");

10

11 }12 }


Beim Versuch den Code zu kompilieren wird der Compiler die folgende Fehler-

3Auch wenn hier immer nur eine Datei gleichzeitig kompiliert wird, ist es auch möglich mehrereDateien gleichzeitig zu kompilieren, daher wird der Dateiname mit angegeben.


meldung ausgeben:

Fehler2.java:12: error: reached end of file while parsing}^1 error

Diese Meldung ist leider nicht ganz so leicht verständlich, wie die des vorherigenFehlers. Der Compiler meldet den Fehler bei der geschweiften Klammer in Zeile12 von Fehler2.java. Diese Zeile enthält jedoch lediglich eine schließende, ge-schweifte Klammer. Die Fehlernachricht lautet „reached end of file while parsing”und impliziert, dass der Compiler noch weiteren Code erwartet hätte und für ihndie Datei überraschend geendet hat. Das eigentliche Problem liegt darin, dassdie schließende Klammer der if-Bedingung in Zeile 10 vergessen worden ist.Der Compiler interpretiert die schließende Klammer in Zeile 11 als schließendeKlammer der if-Abfrage und die Klammer in Zeile 12 als schließende Klammerzu der öffnenden Klammer der main in Zeile 4. Folglich gibt es keine schließendeKlammer mehr für die öffnende Klammer der Klasse aus Zeile 3 und der Compilergelangt ans Ende der Datei, bevor alle Klammern korrekt geschlossen wurden.

Der Fehler im in Listing 9 dargestellten Code ist nun wieder etwas einfacherzu finden, auch wenn er vielleicht auf den ersten Blick nicht offensichtlich zuerkennen ist.



6 int zahl = IO.readInt("Bitte eine Zahl: ")7

8 IO.println(zahl);9

10 }11 }


Das Kompilieren des Code führt nun zu folgender Fehlermeldung:

Fehler3.java:6: error: ’;’ expectedint zahl = IO.readInt("Bitte eine Zahl: ")

^1 error


Die Fehlermeldung verrät dem aufmerksamen Leser in diesem Fall ziemlich di-rekt wo das Problem liegt und wie es zu beheben ist. Der Ausdruck in Zeile 6des Programms Fehler3.java wird nicht wie erforderlich mit einem Semikolonbeendet.

In Listing 10 ist ein Programm dargestellt, dessen eigentlicher Code nur aus zweiZeilen besteht.



6 int zahl = IO.readInt("Bitte eine Zahl: );7

8 IO.println(zahl);9

10 }11 }


Umso verwunderlicher ist es, dass ein Fehler in diesen beiden relativ einfachenund kurzen Zeilen eine lange Folge von Fehlermeldungen erzeugt, die auf denersten Blick teilweise keinen wirklichen Sinn zu ergeben scheinen:

Fehler4.java:6: error: unclosed string literalint zahl = IO.readInt("Bitte eine Zahl: );

^Fehler4.java:6: error: ’;’ expected

int zahl = IO.readInt("Bitte eine Zahl: );^

Fehler4.java:8: error: illegal start of expressionIO.println(zahl);


IO.println(zahl);^

Fehler4.java:8: error: not a statementIO.println(zahl);


IO.println(zahl);^

6 errors


Man darf sich hier nun nicht zu sehr beirren lassen und sollte die Liste systema-tisch von oben nach unten abarbeiten. Der erste Fehler bezieht sich auf Zeile 6von Fehler4.java und die Meldung lautet „unclosed string literal” und deutet aufdie doppelten Anführungszeichen des auszugebenden Textes. Was bisher als Textbezeichnet wurde heißt in der Fachsprache eigentlich String. Ein String wirddurch sogenannte Literale eingeschlossen, die doppelten Anführungszeichen. InZeile 6 fehlen die schließenden Anführungszeichen. Dies führt beim Compiler zuvielen Folgefehlern, die aber alle verschwinden, sobald man die doppelten Anfüh-rungszeichen in Zeile 6 korrekt setzt.



6 int i = -1;7

8 while(i < 0){9 i = i - 1;

10 IO.println(i);11 }12

13 }14 }


Das in Listing 11 dargestellte Programm enthält nun keinen syntaktischen, son-dern einen logischen Fehler. Ein logischer Fehler liegt vor, wenn das Programmkompiliert und ausgeführt werden kann, aber nicht den ursprünglich angedach-ten Zweckt erfüllt und sich anders verhält als es vom Programmierer gewünschtwar.

Eine Variable i wird in Zeile 6 mit dem Wert -1 initialisiert. Eine while-Schleifeläuft solange i < 0 gilt, also garantiert mindestens ein mal bei dem Anfangswert-1 für i. Im Schleifenrumpf wird die Zahl um eins verringert (Zeile 9) und danndie neue Zahl ausgegeben (Zeile 10). Bei der Ausführung erhält man die folgendeAusgabe auf der Kommandozeile:

-1-2-3-4-5-6...


Tatsächlich wird die negative Zahl immer kleiner und kleiner und das Programmfindet niemals ein Ende. Das Problem ist hier, dass die Abbruchbedingung derSchleife - i wird 0 - niemals erreicht werden kann und folglich das Programmniemals enden wird4. Sogenannte Endlosschleifen sind ein häufiger Fehler, derbei der Arbeit mit Schleifen auftritt. Um das Programm manuell zum Abbruch zuzwingen, können Sie die Tastenkombination CTRL + C bzw. STRG + C verwenden.Es sei darauf hingewiesen, dass Endlosschleifen in gewissen Kontexten auch ofterwünscht sind. Wenn Sie z.B. eine Website aufrufen, dann läuft auf dem aus-führenden Server eine Schleife, die immerzu neue Anfragen bearbeitet. Für diemeisten in dieser Veranstaltung entwickelten Algorithmen ist ein solches Verhal-ten allerdings nicht erstrebenswert.

4Aus technischen Gründen, die im Vorkurs nicht behandelt werden, endet dieses konkrete Pro-gramm irgendwann, dass muss aber nicht immer so sein.

2 Algorithmen nachvollziehen

Eine aus sehr konkreten, strukturierten Einzelanweisungen bestehende Hand-lungsvorschrift bezeichnet man gemeinhin als Algorithmus. Aus dem Alltag be-kannte Beispiele sind Kochrezepte. Dort wird meist in natürlicher Sprache be-schrieben wie das jeweilige Gericht Schritt für Schritt zu kochen ist. Ein weiteresBeispiel ist die Aufbauanleitung von Möbelstücken aus einem bekannten, schwe-dischen Einrichtungshaus. Dort wir der Algorithmus meist in Form von Bildse-quenzen dargestellt, die genau zeigen wann welche Schraube in welches Teilhinein gedreht werden muss, um den lang ersehnten Kleiderschrank endlich imSchlafzimmer stehen zu haben. Im Kapitel 1 haben Sie als weitere Darstellungs-form für Algorithmen die Sprache Java kennengelernt. Geht es um den Entwurfvon Algorithmen, so kann es jedoch oft sinnvoll sein das algorithmische Denkenvon der Umsetzung in einer Programmiersprache zu trennen und diese Schrit-te zur Vereinfachung unabhängig voneinander zu betrachten. In diesem Kapitellernen Sie zwei weitere Darstellungsarten für Algorithmen kennen und üben dasVerständnis und die Abarbeitung von in diesen Formen dargestellten Algorith-men.

2.1 Pseudocode

Eine Möglichkeit Algorithmen relativ abstrakt und von einer Programmierspra-che unabhängig, aber gleichzeitig strukturiert zu beschreiben ist der sogenanntePseudocode. Ein Beispielalgorithmus zur Zubereitung einer Tiefkühlpizza ist inlisting 12 dargestellt.

1 öffne verpackung2

3 WENN die Pizza in Folie eingepackt ist4 Entferne Folie5

6 schalte Ofen ein7 gib Pizza auf Blech in Ofen8 warte die auf der Packung angegebene Zeit9 entnimm Pizza aus dem Ofen

Listing 12: Pizza backen

16 2 Algorithmen nachvollziehen

Schlüsselworte, wie z.B. die bedingte Verzweigung1 in Zeile 3 werden in Pseudo-code oft fett gedruckt, um die Lesbarkeit zu erhöhen und Unterscheidung zwi-schen Schlüsselworten und Anweisungen zu vereinfachen. Anweisungen, die zuder bedingten Verzweigung gehören werden einfach um vier Leerzeichen einge-rückt dargestellt. Im Beispiel soll nur dann eine Folie von der Pizza entfernt wer-den, wenn auch wirklich eine Folie vorhanden ist. Die Anweisungen kann manjetzt in der benötigten Granularität in natürlicher Sprache verfassen. Dabei mussman stets im Hinterkopf behalten, für wen man den Algorithmus formuliert. EinComputer könnte den obigen Pseudocode nicht ausführen, ein Mensch hingegenschon. Alle Anweisungen werden in der gegebenen Reihenfolge nacheinander vonoben nach unten abgearbeitet.

Angenommen die Backzeit der Pizza wäre nicht bekannt, weil jemand sie auf derPackung durchgestrichen hat. Man müsste dann den Algorithmus wie in listing 13dargestellt anpassen.

1 öffne verpackung2

3 WENN die Pizza in Folie eingepackt ist4 Entferne Folie5

6 schalte Ofen ein7 gib Pizza auf Blech in Ofen8

9 SOLANGE Pizza noch nicht fertig10 warte eine Minute11

12 entnimm Pizza aus dem Ofen

Listing 13: Pizza backen

Da die Backzeit nicht bekannt ist, muss jede Minute geprüft werden, ob die Pizzafertig ist. Man benötigt also eine Struktur zur Wiederholung, eine Schleife. DieSchritte in der SOLANGE-Schleife werden also solange wiederholt, bis die Ab-bruchbedingung „Pizza ist noch nicht fertig“ ihre Gültigkeit verliert. Man prüftalso jede Minute, ob die Pizza fertig ist. Ist sie irgendwann fertig wird die Schleifeverlassen und der nächste Schritt kann durchgeführt werden.

2.2 Struktogramme

Struktogramme2 sind eine weitere Möglichkeit Algorithmen darzustellen. Die Struk-tur des Ablaufs wird dabei durch graphische Elemente symbolisiert. Verglichen

1vergleichbar mit der if -Bedingung aus Kapitel 12auch bekannt als Nassi-Schneidermann Diagramme

2.2 Struktogramme 17

Figure 2.1: Struktogramm für Pizza backen

mit dem Pseudocode lässt sich so in vielen Fällen die Struktur schneller erfassen.Die Anweisungen werden weiterhin in gewünschter Granularität in natürlicherSprache formuliert. Der Pizza-Algorithmus ohne bekannte Backzeit aus listing 13ist als Struktogramm in Bild 2.1 dargestellt.

Der äußere Rahmen fasst alle Anweisungen zusammen und bezeichnet gleich-zeitig den Algorithmus, in diesem Fall mit „Tiefkühlpizza backen”. Anweisungenwerden in rechteckigen Kästchen dargestellt, z.B. die Anweisung „öffne Verpa-ckung”. Bedingte Verzweigungen werden durch ein in Dreiecke geteiltes Recht-eck dargestellt, wie bei der Entscheidung „die Pizza ist in Folie eingepackt”. DieBedingung wird dabei ins obere Dreieck geschrieben, und die Verzweigungen für„WAHR” und „FALSCH” in die unteren Beiden. Anweisungskästchen unterhalbder jeweiligen Entscheidung werden nur dann ausgeführt, wenn die Bedingungentsprechend gilt oder nicht. Die Schleife mit der Bedingung „Pizza noch nichtfertig” wird durch ein größeres Kästchen dargestellt, in das weitere Anweisungs-kästchen eingebettet sind, hier „warte eine Minute”. Auch Struktogramme wer-den von oben nach unten abgearbeitet.


2.3 Schildkrötengrafiken

Im folgenden werden sogenannte Schildkrötengrafiken eingesetzt, um Sie lang-sam an die Algorithmik heranzuführen. Schildkrötengrafiken verwenden einenrelativen Cursor um Bilder in der 2D Ebene zu zeichnen. Die Zeichenanweisun-gen werden dabei immer relativ zur aktuellen Position gegeben. Die Schildkröte(=Cursor) hat immer eine Position und eine Orientierung, also eine Richtung, indie sie schaut. Die Schildkröte kann mit Anweisungen der Art „gehe 10 Einheitenvorwärts” oder „drehe dich um 90 Grad nach links” gesteuert werden. Im fol-genden gehen wir davon aus, dass die Schildkröte zu Beginn immer nach rechtsschaut. Ein einfaches Beispiel ist als Pseudocode in Listing 14 dargestellt.

1 WIEDERHOLE 4 MAL2 gehe 10 Einheiten vorwärts3 drehe dich 90 Grad nach rechts

Listing 14: Quadrat

Können Sie anhand des Pseudocode feststellen, welches Bild die Schildkröte zeich-nen wird? Das Ergebnis ist in Bild 2.2 dargestellt.

Figure 2.2: Ergebnis für Code aus Listing 14.

Die Schildkröte ist in diesem Beispiel der grüne Kreis, der kleine Pfeil zeigt dieOrientierung an. Die Schildkröte geht 10 Einheiten vorwärts und dreht sich dannum einen rechten Winkel nach rechts. Das ganze wird vier mal wiederholt undführt damit dazu, dass ein Quadrat gezeichnet wird. Die Schildkröte steht amEnde wieder an ihrer Ausgangsposition.

Ein etwas komplexeres Beispiel ist in Bild 2.3 als Struktogramm dargestellt. Neh-men Sie sich einen Moment Zeit und versuchen mit Stift und Papier den Algorith-mus nachzuvollziehen. Auf den ersten Blick ist es schwer abzuschätzen welchesBild entstehen wird. Ein Algorithmus lässt sich aber Schritt für Schritt von obennach unten abarbeiten, um an das gewünschte Ergebnis zu gelangen. Das Ergeb-nis der Ausführung finden Sie in Bild 2.4.

Der Algorithmus besteht im Wesentlichen aus einer Schleife, die drei mal diein ihr enthaltenen Anweisungen wiederholt. Die Anweisungen sind eine Sequenz

2.3 Schildkrötengrafiken 19

der rudimentären Schildkrötenbefehle zur Bewegung nach vorn und der Drehungnach links oder rechts.

Figure 2.3: Zeichnen 1

Figure 2.4: Zeichnen 1 Ergebnis

Ein etwas komplexerer Algorithmus ist als Pseudocode in Listing 15 dargestellt.Der dargestellte Algorithmus beinhaltet gegenüber den vorherigen Beispiele einneues Konzept, welches die Komplexität der Abarbeitung erhöht. Vor Beginn derSchleife wird eine Schrittweite festgelegt, die sich im Laufe der Abarbeitung derAnweisungen in der Schleife ändert. Derartig strukturierte Algorithmen lassensich noch schwieriger auf den ersten Blick durchschauen, als die bisherigen Bei-spiele. Nehmen Sie abermals Papier und Stift zur Hand und versuchen Sie denAlgorithmus nachzuvollziehen.

Dem aufmerksamen Leser sollte auffallen, dass der Algorithmus sehr ähnlich zudem in Bild 2.3 dargestellten Algorithmus ist. Lediglich die Schrittweite ist ver-


1 Setze Schrittweite auf 52 WIEDERHOLE 3 MAL3 gehe Schrittweite vorwärts4 erhöhe Schrittweite um 55 drehe dich 90 Grad nach rechts6 gehe 3 vorwärts7 drehe dich 90 Grad nach rechts8 gehe Schrittweite vorwärts9 erhöhe Schrittweite um 5

10 drehe dich 90 Grad nach links11 gehe 3 vorwärts12 drehe dich 90 Grad nach links

Listing 15: Zeichnen 2

ändert, sie ist nicht mehr konstant, sondern ändert sich im Laufe der Abarbei-tung. Das Ergebnis ist in Bild 2.5 dargestellt. Es entsteht also eine Art Pyradmidedurch die Sukzessive Erhöhung der Länger der horizontalen Linien. Man solltehier feststellen, dass bereits verbal relativ einfach zu beschreibende Strukturenin algorithmischer Form schon recht komplex und anspruchsvoll werden.


Bislang haben Sie nur einfache Schleifen kennen gelernt. Für komplexere Algo-rithmen ist es oftmals erforderlich Schleifen ineinander zu schachteln. Innerhalbeiner Schleife dürfen sich also weitere Schleifen befinden. Ein Beispiel in Pseu-docode dazu findet sich in Listing 16. Wenn Algorithmen komplizierter werden,dann macht es oft Sinn - sowohl in Pseudocode, als auch in konkreten Program-miersprachen - wie auch in Prosa Abschnitte zu verwenden, um die Lesbarkeitzu erhöhen. Das Endergebnis würde man auch hier sicherlich nicht als besonderskomplex bezeichnen, aber mit steigender Komplexität steigt auch die Komplexitätder Algorithmendarstellung stark an. Vollziehen Sie auch hier den Algorithmuszunächst mit Papier und Stift nach. Die entstehende Zeichnung ist in Bild 2.6dargestellt.

Die Struktur ist wiederrum ähnlich zu den vorherigen Beispielen, zeichnet aber

2.3 Schildkrötengrafiken 21

1 WIEDERHOLE 2 MAL2 WIEDERHOLE 2 MAL3 gehe 4 vorwärts4 drehe dich 90 Grad nach links5

6 WIEDERHOLE 2 MAL7 gehe 4 vorwärts8 drehe dich 90 Grad nach rechts9

10 gehe 4 vorwärts11 drehe dich 90 Grad nach links12

13 gehe 4 vorwärts14 drehe dich 90 Grad nach links15 gehe 6 vorwärts16 drehe dich 90 Grad nach links17

18 WIEDERHOLE 2 MAL19 gehe 4 vorwärts20 drehe dich 90 Grad nach rechts21

22 WIEDERHOLE 2 MAL23 gehe 4 vorwärts24 drehe dich 90 Grad nach links25

26 gehe 4 vorwärts27 drehe dich 90 Grad nach rechts28

29 gehe 4 vorwärts30 drehe dich 90 Grad nach links31 gehe 6 vorwärts32 drehe dich 90 Grad nach links

Listing 16: Zeichnen 3

statt gerader Linien auf der Horizontalen nun eine Art Stufen. Schon diese mitWorten leicht zu beschreibende Änderung zieht umfangreiche Änderung im Al-gorithmus nach sich, da dort präzise und schrittweise Beschrieben muss, wiedie erforderlichen Handlungen auszuführen sind. Statt der Verwendung von ge-schachtelten Schleifen könnte man natürlich auch die Anweisungen mehrmalsnacheinander aufschreiben, hätte dadurch aber viele Dopplungen und eine nochviel unübersichtlichere Folge von Anweisungen.



3 Algorithmen entwickeln

In diesem Kapitel soll nun basierend auf den bisherigen Inhalten der nächsteSchritt hin zur Entwicklung von Algorithmen gemacht werden. Algorithmen zuentwerfen gestaltet sich deutlich schwieriger, als Algorithmen abzuarbeiten. UmIhnen ein Gefühl dafür zu geben, was Sie in dieser Richtung in der Veranstaltungerwarten wird, sollen Sie sich nun mit einigen Beispielen vertraut machen.

3.1 Maximum finden

Eine in der Informatik häufig auftretende Problemstellung ist die Suche des Ma-ximums - der größten Zahl - in einer gegebenen Folge von Zahlen. Damit Siesich algorithmisch aus Sicht einer Maschine an das Problem herantasten können,wird im folgenden das Problem mit einem Modell veranschaulicht. Die Zahlenfol-ge wird dargestellt durch eine Reihe umgekehrt auf dem Tisch stehender Becher,auf deren Innenseite am Boden die Zahl notiert ist, die der jeweilige Becher reprä-sentiert. Dies symbolisiert die Situation, dass der Computer nicht einfach wie einMensch auf einen Blick aus einer Menge nebeneinander stehender Zahlen dasMaximum bestimmen kann, sondern schrittweise jede Zahl begutachten muss.Sie sollen nun einen Algorithmus angeben, der aus dieser Reihe von Bechern denBecher mit der größten Zahl auf der Innenseite ermittelt. Dabei einzuhaltendeNebenbedingungen sind, dass Sie nur Becher von unten betrachten dürfen, dieSie in der Hand haben. In jeder Ihrer Beiden Hände darf sich nur maximal einBecher gleichzeitig befinden.

Den Algorithmus als Struktogramm beschrieben finden Sie in Abbildung 3.1. DieHauptschwierigkeit besteht eigentlich darin die vorhandenen Ressourcen - in die-sem Fall die beiden Hände - korrekt einzusetzen. Sie müssen sich irgendwie mer-ken welche Zahl die bisher größte gefundene Zahl ist. Hier geschieht dies durchfesthalten des entsprechenden Bechers in der linken Hand. Mit der rechten Handwird der nächste zu prüfende Becher hochgehoben und sein Wert mit dem bishergrößten gefundenen Wert in der linken Hand verglichen. Ist der neue Wert grö-ßer als der bisher größte, dann nimmt dieser Becher seinen Platz in der linkenHand ein. Während Sie wahrscheinlich bei einigen wenigen auf einem Zettel ne-beneinander stehenden Zahlen sofort durch Hinsehen das Maximum bestimmenkönnten, ist ein Algorithmus zur Lösung dieses Problems schon nicht mehr sosimpel zu beschreiben.

24 3 Algorithmen entwickeln

Figure 3.1: Maximum finden

3.2 Sortierte Suche

Ein anderes häufig auftretendes Problem ist die effiziente Suche von Objekten insortierten Folgen. Wir wollen hier das Beispiel mit den Bechern und darin aufge-schriebenen Zahlen aus dem vorherigen Abschnitt beibehalten. Die Zusatzannah-me ist nun aber, dass die Zahlen in den Bechern von links nach rechts aufsteigendsortiert sind. Zusätzlich zu Ihren beiden Händen dürfen Sie zwei kleine Steinchenmit den Aufschriften „links” und „rechts” verwenden, um sich Positionen in derBecherreihe zu merken. Versuchen Sie die Eigenschaft der Sortiertheit möglichstgeschickt auszunutzen. Sie starten mit einem Zettel, auf dem die gesuchte Zahlsteht, in Ihrer linken Hand. Die zu beantwortende Frage lautet nun: „Ist die Zahlauf dem Zettel in einem der Becher zu finden?”.

Die Lösung ist in Abbildung 3.2 dargestellt. Die beiden Steine markieren immerden Bereich, in dem sich die gesuchte Zahl noch befinden kann. Zu Beginn istdas die Gesamtheit der Becher. Man prüft dann zunächst den Becher in der Mitteder beiden Suchgrenzen. Findet man dort die Zahl, dann kann man hier schonabbrechen; andernfalls muss noch weiter gesucht werden. Da die Zahlenfolgesortiert ist, kann man anhand des Wertes in der Mitte bestimmen auf welcherSeite der Mitte die gesuchte Zahl sich noch befinden kann. Ist die Mitte größerals die gesuchte Zahl, dann sind alle Zahlen weitere rechts ja nur noch größerund dort weiterzusuchen würde keinen Sinn machen. Folglich kann man nun dierechte Suchgrenze an die Stelle der Mitte setzen und nun wieder genau so fürden neuen Bereich vorgehen. In jedem Schritt kann man also sehr viele potentiell

3.2 Sortierte Suche 25

Figure 3.2: Sortierte Suche

zu prüfende Becher ausschließen und reduziert so drastisch den Prüfaufwand.Dieses Verfahren ist auch als „binäre Suche” bekannt und ist elementarer Be-standteil vieler weiterführender Algorithmen.

Documents

Studienvorkurs Informatik · Java-Code dient primär dazu in strukturierter Weise als Mensch die gewünschten ... ohne einen übergebenen Text in Zeile 3 erzeugt also lediglich eine