Upload
hoangcong
View
216
Download
0
Embed Size (px)
Citation preview
Einstieg in die Informatik mit JavaAlgorithmen
Gerd Bohlender
Institut fur Angewandte und Numerische Mathematik
1 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
2 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
3 / 28
Uberblick
In diesem Kapitel werden Algorithmen und die Umsetzungeinfacher Algorithmen in Java beschrieben.
AlgorithmusGenaue Vorschrift zur Berechnung / Bearbeitung einesProblems, z.B. Java-Programm
Umsetzung in JavaDarstellung des Algorithmus durch Befehle in Java
4 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
5 / 28
Algorithmus
Prazise Beschreibung einer Berechnung oder allgemein einesVerfahrens. Benannt nach Muhammad al-Chwarizmi, ca.780-850 in Persien.Deterministischer Algorithmus: ein Verfahren mit folgendenEigenschaften
• Das Verfahren muss durch einen endlichen Text oder eineendliche Grafik beschrieben werden (Finitheit)
• Jeder Schritt des Verfahrens muss eindeutig ausfuhrbarsein (Ausfuhrbarkeit)
• Der nachste anzuwendende Schritt des Verfahrens musszu jedem Zeitpunkt eindeutig definiert sein(Determinismus)
• Das Verfahren darf zu jedem Zeitpunkt nur endlich vielSpeicherplatz benotigen (Dynamische Finitheit)
• Das Verfahren muss nach endlich vielen Schritten enden(Terminierung)
6 / 28
Algorithmus: spezielle Varianten
In manchen Fallen sind Ausnahmen sinnvoll:• Keine Terminierung: Mathematisches Iterationsverfahren:
konvergiert gegen Losung• Keine Terminierung: Betriebssystem eines Rechners• Keine Terminierung: Steuersoftware eines Gerats (z.B.
Handy, Auto) oder Fertigungsprozess (z.B. in Chemiewerk)sollen dauerhaft laufen
• Kein Determinismus: Verwendung einer (echten)Zufallszahl, unvorhersehbare zeitliche Ablaufe inParallelrechner
7 / 28
Beispiel zu Algorithmus: Euklidischer Algorithmus
Berechne den großten gemeinsamen Teiler von zweinaturlichen Zahlen a und b.Euklid, ca. 360 v. Chr. (Athen) - 280 v. Chr. (Alexandria, heuteAgypten)
1 Solange b 6= 0 ist, wiederhole folgende Schritte2 Berechne h = a mod b (Rest bei der Division)3 Setze a = b4 Setze b = h
Dann ist a der ggT der ursprunglichen Zahlen.Ablauf am Beispiel a = 20, b = 24:
a b h20 24 2024 20 420 4 04 0 –
Der ggT von 20 und 24 ist 4.8 / 28
Beispiel zu Algorithmus: Sieb des EratosthenesBerechne alle Primzahlen bis zu einer gegebenen Zahl N > 1.Eratosthenes, ca. 276 v. Chr. (Kyrene, heute Libyen) bis 194 v. Chr.(Alexandria, heute Agypten)
1 Erstelle Liste KANDIDATEN aller ganzen Zahlen von 2 bis N2 Erstelle leere Liste PRIM der bereits erkannten Primzahlen3 Wiederhole folgende Schritte, bis die Liste KANDIDATEN leer
ist4 Bestimme die kleinste Zahl X in der Liste der KANDIDATEN
5 Fuge X zur Liste PRIM hinzu6 Streiche X und alle seine ganzzahligen Vielfachen aus der
Liste der KANDIDATEN
Ablauf am Beispiel N = 10:
X KANDIDATEN PRIM
2, 3, 4, 5, 6, 7, 8, 9, 10 (leer)2 3, 5, 7, 9 23 5, 7 2, 35 7 2, 3, 57 (leer) 2, 3, 5, 7
9 / 28
Beispiel Roulette: Kein Algorithmus
Fahre nach Baden-Baden und gewinne im Roulette1 Beginne mit 1 Euro Einsatz2 Wiederhole die folgenden Schritte bis Du eine Million Euro
gewonnen hast3 Setze den Einsatz auf rot oder schwarz4 Falls Du gewinnst, kassiere den Gewinn und beginne
wieder mit 1 Euro Einsatz5 Falls Du verlierst, verdopple den Einsatz
Kein Algorithmus: nicht determiniert, unbeschrankteZwischenergebnisse.
10 / 28
Beispiel Roulette: Kein Algorithmus
Ablauf, Anfangsguthaben 100 Euro:
Einsatz Gewinn Guthaben1 1 1011 0 1002 0 984 0 948 0 8616 16 102...
Theoretisch steigt das Guthaben nach jederVerdoppelungsphase um 1 EuroPraktisch funktioniert dies so nicht, da zwischenzeitlicheVerluste beliebig groß werden konnen.Auftreten von Zero und weitere Regeln der Spielbank (z.B.Mindest- und Hochsteinsatz) sind zu beachten.
11 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
12 / 28
Grundalgorithmen in Java
Die wichtgsten Anweisungen in Java:• Wertzuweisung: Variable erhalt den Wert der rechten Seite
x = 27;y = 3∗x + 2;
• Eingabeanweisung: Variable erhalt einen eingelesenenWert
i = sc . n e x t I n t ( ) ;x = sc . nextDouble ( ) ;
• Ausgabeanweisung: der Wert wird ausgegeben
System . out . p r i n t l n ( ” B i t t e x eingeben : ” ) ;System . out . p r i n t l n ( y ) ;System . out . p r i n t l n ( ” Ergebnis = ” + y ) ;
Alle verwendeten Variablen mussen zuvor definiert werden, z.B
i n t i , j , k ;double x , y ;
13 / 28
Grundstruktur eines Java-Programms
Der typische Aufbau eines Java-Programms
import java . u t i l . ∗ ;
public class ProgrammName {public s t a t i c void main ( S t r i n g [ ] args ) {
Locale . se tDe fau l t ( Locale .US) ;Scanner sc = new Scanner ( System . i n ) ;
/ / h i e r werden d ie beno t ig ten/ / Var iab len d e f i n i e r t
/ / h i e r s t eh t der Algor i thmus des Programms/ / ( Folge von Anweisungen )
}}
14 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
15 / 28
Flussdiagramme
Kompliziertere Algorithmen mussen formal beschriebenwerden.
• Flussdiagramme / Programmablaufplane• Anweisungen in Rechtecken / Rauten / Parallelogrammen• Reihenfolge der Anweisungen wird mit Pfeilen angezeigt• in DIN 66001 genormt• kann unubersichtlich werden• schwierig zu bearbeiten
16 / 28
Flussdiagramm: Gib 1 bis 39 und 61 bis 100 aus
Quelle: de.wikipedia.org/wiki/Programmablaufplan17 / 28
Gliederung
1 Uberblick
2 Algorithmus
3 Grundalgorithmen in Java
4 Flussdiagramme
5 Struktogramme
18 / 28
Struktogramme
Kompliziertere Algorithmen mussen formal beschriebenwerden.
• Flussdiagramme oft unubersichtlich und unstrukturiert• Alternative: Struktogramme /
Nassi-Shneiderman-Diagramme• Rechteckige Kasten enthalten elementare Anweisungen• Die Kasten konnen aneinander gereiht und geschachtelt
werden• von Isaac Nassi und Ben Shneiderman entwickelt (1972/73,
USA)• in DIN 66261 genormt
• Weitere Alternative: UML (Unified Modeling Language)
Quelle der folgenden Grafiken:de.wikipedia.org/wiki/Nassi-Shneiderman-Diagramm
19 / 28
Folge von Anweisungen
Mehrere Anweisungen sollen in der angegebenen Reihenfolgeausgefuhrt
Darstellung in Java:
{Anweisung1Anweisung2Anweisungn
}
20 / 28
Einfache Auswahl von Anweisungen
Abhangig von einer Bedingung sollen Anweisungen ausgefuhrtwerden oder nicht
Darstellung in Java:
i f ( Bedingung ) {Anweisung1Anweisung2Anweisungn
}
21 / 28
Zweiseitige Auswahl von AnweisungenAbhangig von einer Bedingung sollen Anweisungen ausgefuhrtwerden oder andere Anweisungen
Darstellung in Java:
i f ( Bedingung ) {Anweisung1 .1Anweisung1 .2Anweisung1 . n
}else {
Anweisung2 .1Anweisung2 .2Anweisung2 . n
}
22 / 28
Wiederholung von Anweisungen
Anweisungen soll mehrfach ausgefuhrt werden
Darstellung in Java:
for ( i n t i = S t a r tw e r t ; i <=Endwert ; i ++) {Anweisung1Anweisung2Anweisungn
}
23 / 28
Wiederholung von Anweisungen
Solange eine Bedingung erfullt ist, sollen Anweisungenwiederholt werden; die Bedingung soll zuerst gepruft werden
Darstellung in Java:
while ( Bedingung ) {Anweisung1Anweisung2Anweisungn
}
24 / 28
Wiederholung von Anweisungen
Solange eine Bedingung erfullt ist, sollen Anweisungenwiederholt werden; die Bedingung soll erst nachtraglich gepruftwerden
Darstellung in Java:
do {Anweisung1Anweisung2Anweisungn
} while ( Bedingung ) ;
25 / 28
Auswahl von Anweisungen
Je nach Wert eines Ausdrucks sollen unterschiedlicheAnweisungen ausgefuhrt werden
Darstellung in Java:
switch ( Ausdruck ) {Wert1 : Anweisungen1Wert2 : Anweisungen2Wert3 : Anweisungen3Wertn : Anweisungenndefaul t : A l ternat ivAnweisungen
}
26 / 28
Aufruf einer Methode
Rufe eine Methode auf (berechne Funktion, fuhreZwischenrechnung aus)
Darstellung in Java:
nameDerMethode ( Parameter )
27 / 28