33
Algorithmen Folie 1 Uwe Lämmel Einführung in die Programmierung Algorithmen Uwe Lämmel Fakultät für Wirtschaftswissenscha ften www.wi.hs-wismar.de/ ~laemmel [email protected]
Algorithmen Folie 1Uwe Lämmel
Einführung in die ProgrammierungAlgorithmen
Uwe Lämmel
Fakultät für Wirtschaftswissenschaften
www.wi.hs-wismar.de/~laemmel
Algorithmen Folie 2Uwe Lämmel
Inhalt
Suchen– lineare Suche– binäre Suche
Sortieren– Sortieren durch Auswahl– Sortieren durch
Vertauschen– (Quicksort)
dabei benutzte Konzepte– Bibliotheksklasse– ausführbare Klasse– statische Methoden– Array
Programmierungstechnik– Rekursion– Try-catch-Anweisung
Algorithmen Folie 3Uwe Lämmel
Such-Methoden
Parameter– Folge von Elementen, in der gesucht wird: int, String,
…– Index, ab dem zu suchen ist: int– Index, bis wo gesucht wird: int– Das gesuchte Element: wie oben
Ergebnis– Index des gesuchten Elementes oder -1 (nicht
enthalten)
public static int suche(int[] f, int anf, int ende, int gesucht)
Algorithmen Folie 4Uwe Lämmel
Sortier-Methoden
Parameter– Folge von Elementen, in der sortiert wird: int, String,
…– Index, ab dem zu sortieren ist: int– Index, bis wo sortiert wird: int
Ergebnis– Folge von Elementen, jetzt sortiert: int, String, …
public static int[] sort(int[] f, int anf, int ende)
Algorithmen Folie 5Uwe Lämmel
Suche in einer beliebigen Folge
Lineare Suche Alle Elemente, vom 1. bis zum letzten, durchsuchen Folge kann unsortiert sein! Ergebnis ist der Index
unten=anf; oben=ende–1;int next= anf;while (next<=oben && folge[next]!=gesucht) {
next++;}if ( next<=oben ) return next; else return –1;
pittom bea mae mia lea tim kai
anf ende
Algorithmen Folie 6Uwe Lämmel
Suche in einer sortierten Folge
binäre Suche Folge muss sortiert sein! Halbieren des Suchraumes, durch Vergleich mit gesuchtem Element
unten = anf; oben = ende – 1;int next = (unten+oben)/2;while ( unten<oben && folge[next]!=gesucht ) { if ( gesucht<folge[next] ) oben=next –1; else unten=next+1; next = ( unten+oben ) / 2;} //whileif (folge[next]==gesucht) return next; else return –1 ;
leabea kai mae mia pit tim tom
anf ende
Algorithmen Folie 7Uwe Lämmel
Inhalt
Suchen
Sortieren– Sortieren durch Auswahl– Sortieren durch
Vertauschen– (Quicksort)
dabei benutzte Konzepte– Bibliotheksklasse– ausführbare Klasse– statische Methoden– Array
Programmierungstechnik– Rekursion– Try-catch-Anweisung
Algorithmen Folie 8Uwe Lämmel
Sortieren
Definition Assoziative Sortierverfahren:
– durch Auswahl: Select-Sort– durch Vertauschen:
– Bubble Sort– Quicksort– Heap-sort
– durch Einfügen: Insert-Sort– durch Mischen: Merge-Sort– …
Adressenorientiertes Sortieren
Algorithmen Folie 9Uwe Lämmel
Definition einer sortierten Folge?
Eine Folge von n Elementen ist sortiert,wenn an der 1.-ten Position das Minimum der Folge steht,und die Folge vom 2. bis zum (n)-ten Element sortiert ist !Eine Folge aus einem Element ist sortiert.
Select-Sort
Eine Folge von n Elementen ai ist sortiert,
falls für alle i: 1<in gilt: ai>ai-1
Bubble-Sort
Algorithmen Folie 10Uwe Lämmel
Select-Sort: Beispiel
50 77 3 43 1 27 278
5077 3 431 27 278
50 773 431 272 78
50 773 431 272 78
1
2
0
3
50 773 431 272 78
50 773 431 272 78
50 773 431 272 78
50 773 431 272 78
3
4
5
6
Algorithmen Folie 11Uwe Lämmel
Select-Sort: rekursiv
Folge ist von Position anf bis ende–1 belegt Noch 2 Elemente in Folge (anf<ende-1), dann
– Bestimme Position des Minimums– Tausche Minimum mit erstem Element– Sortiere die Restfolge (ab anf+1)
Algorithmen Folie 12Uwe Lämmel
Select–Sort: iterativ
Folge ist von Position anf bis ende–1 belegt Von der ersten (anf.) bis zur vorletzten Position
wiederhole in dieser Teilfolge:– Setze erstes Element als temporäres Minimum– Wiederhole bis zur letzten Position
– Falls temporäres Minimum> als aktuelles Element, dann setze neuen Minimum
– Setze Erstes Element an Stelle des Minimums– Setze Minimum an erste Position
Algorithmen Folie 13Uwe Lämmel
Bubble–Sort
Folge von Position anf bis (ende–1) belegt
Wiederhole von erster bis vorletzter Position
– Falls Element < als Nachfolger danntausche beide Elemente
Bis nicht mehr getauscht wurde
Algorithmen Folie 14Uwe Lämmel
Quicksort
Wähle ein Pivot-Element
– Erstes, mittleres, zufälliges…
Teile die Folge in die …
– … Teilfolge der kleineren Elemente
– … Teilfolge der größeren Elemente (als Pivot-Element)
Quicksort für die Folge der kleineren Elemente
Quicksort für die Folge der größeren Elemente
Algorithmen Folie 15Uwe Lämmel
Quicksort – Implementierung
Pivot-Element festlegen:– erstes, mittleres, Median
wiederhole:– Zeiger von links bis El > Pivot– Zeiger von rechts bis El < Pivot– Falls Zeiger: links<rechts dann El tauschen
und Zeiger weitersetzenbis Zeiger aneinander vorbei
sortiere den Abschnitt der kleineren Zahlen sortiere den Abschnitt der größeren Zahlen
Algorithmen Folie 16Uwe Lämmel
Quicksort static int[ ] quicksort(int[ ] folge, int anf, int ende) {int pivot; // Element zum Vergleichint hilf;int gk, gg; // GrenzeKleinere,GrenzeGroessereif (anf<ende) { // noch mind. zwei Elemente?
pivot=folge[anf];gk=anf; gg=ende;do { // Solange noch nicht alles verteilt
while (folge[gk]<pivot) gk++;while (folge[gg]>pivot) gg--;if (gk<=gg) { // Vertausche gg-te mit gk-te Position
hilf=folge[gg]; folge[gg]=folge[gk]; folge[gk]=hilf;gk++; gg--;
} // if}while (gk<=gg);
if (anf<gg) folge = quicksort(folge,anf,gg); // kleinereif (gk<ende) folge = quicksort(folge,gk,ende); // groessere
} // if return folge;
} //sort
Algorithmen Folie 17Uwe Lämmel
Inhalt
Suchen
Sortieren
Konzepte– Bibliotheksklasse– ausführbare Klasse– statische Methoden– Array
Programmierungstechnik– Rekursion– Try-catch-Anweisung
Algorithmen Folie 18Uwe Lämmel
Klasse – Bibliothek
keine Beschreibung von Objekten Menge von Methoden
– siehe z.B. java.lang.Math Methoden sind statisch – static
public static int ggT(int a, int b) {if(a==b) return a;else if(a>b) return ggT(a-b,b);else return ggT(a,b-a);
} //ggT
Algorithmen Folie 19Uwe Lämmel
Klasse – Bibliothek
class Algorithmen {
public static int[ ] bubbleSort(int[ ] folge, int anf, int ende) { … }public static int[ ] selectSort(int[ ] folge, int anf, int ende) { … }
public static int getMax(int[ ] folge, int anf, int ende) { … }public static int finde(int[ ] folge, int anf, int ende, int el) { … }…public static void ausgeben(int[ ] folge, int anf, int ende) { … }
public static int[ ] testfolge = {76,23,12,54,78,22,45,33,90,51,52,41};
} //Algorithmen
Algorithmen Folie 20Uwe Lämmel
Methode statisch oder nicht?Objekt oder nicht Objekt?
statisch (static): definiert in Bibliotheks- oder ausführbarer Klasse!
public static int finde(int[ ] folge, int anf, int ende, int el) { … };
Aufruf: Methode wird nicht an Objekt gesendet!! index = finde(testfolge,0,8,51);eventuell Angabe der Klasse nötig:a = Math.sqrt(z); index =Algorithmen.finde(testfolge,0,8,51);
dynamisch: definiert Objekt-Verhalten in Bauplan-Klasse
public int finde(int el) { … };
Aufruf: Methode wird an Objekt gesendet!index = telefonbuch.finde(110);
Algorithmen Folie 21Uwe Lämmel
Aufgaben für statische Funktionen
Such-, und Sortiermethoden Einlesen von Zahlen auf ein Array Ausgabe eines Arrays Methoden für natürliche Zahlen:
– Test, ob Zahl ideal ist:Zahl = Summe aller echten Teiler
– Test, ob eingegeben Zahl eine Primzahl ist– Berechnung aller Primzahlen bis zu einer
vorgegebenen Zahl – Collatz-Funktion für alle Zahlen bis zu einer
einzugebenden Grenze …
!Üben!
Algorithmen Folie 22Uwe Lämmel
Ungewöhnliches Beispiel: Collatz-Funktion
Collatz-Wert einer natürlichen Zahl n:
= Anzahl der folgenden Schritte bis eine 1 erreicht wird: Ist n gerade, dann wird durch 2 dividiert: n:=n div 2 Ist n ungerade, dann: n:= 3n+1
Collatz-Funktion
0
20
40
60
80
100
120
1 11 21 31 41 51 61 71 81 91 N
Co
lla
tz(N
)collatz(6)?1. 32. 103. 54. 165. 86. 47. 28. 1collatz(6)=8
Algorithmen Folie 23Uwe Lämmel
Inhalt
Suchen
Sortieren
benutzte Konzepte
Programmierungstechnik– Rekursion– Try-catch-Anweisung
Algorithmen Folie 24Uwe Lämmel
Rekursion
Definition einer Methode, wobei die Methode selbst hierzu benutzt wird
Rekursionsabbruch vor rekursivem Aufrufif ( Bedingung) rekursiver Aufrufelse kein rekursiver Aufruf (Rekursionsabbruch)
Problem muss beim rekursiven Aufruf kleiner werden:
public static long fak(int n) { if (n > 0) return n*fak(n-1); else return 1;}//fak
Algorithmen Folie 25Uwe Lämmel
Rekursion, ein einfaches Beispiel: Fakultät
public static long fak(int n) { if (n > 0) return n*fak(n-1); else return 1; } //fak
fak(3) 3 * fak(2)
fak(2)
2 * fak(1)
fak(1) 1 * fak(0)
6
2
1
fak(0)
1
1
Algorithmen Folie 26Uwe Lämmel
Rekursion: Fibonacci(5) - Aufrufstruktur
fibonacci(5)
fibonacci(4) fibonacci(3)
fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)
fibonacci(2) fibonacci(1)
fibo(n) = 1, falls n=1 oder n=2= fibo(n-1)+fibo(n-2)
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Algorithmen Folie 27Uwe Lämmel
Rekursion: Turm von Hanoi
Turm vom Ausgangs- zum Zielort bewegen Immer nur eine Etage Es darf keine größere Etage auf eine kleinere gesetzt werden Es steht nur ein Hilfsort zum Zwischenstapeln zur Verfügung
Ausgangsort HilfsortZielort
Algorithmen Folie 28Uwe Lämmel
Rekursion: Aufgaben
Bestimmen der Quersumme einer Zahl (rekursiv!) Berechnen der Ackermann-Funktion ackermann(x,y)
– Bis zu welchen Parametern x,y erhält man Ergebnisse?
Algorithmen Folie 29Uwe Lämmel
Strukturierte Anweisung: try-catch
Anweisungen1 werden ausgeführt:– falls Fehler (Ausnahme, Exception) und– Fehler ist vom Typ ExceptionTyp:
– Anweisungen2 werden ausgeführt
try { Anweisungen1 // geschützte Ausführung}catch ( ExceptionTyp e) { Anweisungen2 // Fehlerbehandlung und Information}
Algorithmen Folie 30Uwe Lämmel
Strukturierte Anweisung: try-catch-Beispiel
…do { try { int zahl = ea.readInt("Bitte Zahl eingeben: "); ende = (zahl== –1); // true, falls Zahl gleich –1 } catch (NumberFormatException ex){ ea.writeln(ex.getMessage()+ " Das war falsch!"); ende = false; } catch( IOException io) { }}while(!ende);
wiederholte Eingabe-Aufforderung:
Algorithmen Folie 31Uwe Lämmel
Nur zum Testen
import java.io.*;/** * * Veranschaulichung der Wirkung der try-catch-Anweisung: * Wiederholte Eingabe-Aufforderung bis eine gültige Zahl eingegeben wurde. * Es werden zwei Ausnahmen behandelt: * - Die Ein-Aussgabe-Ausnahme (IOException) MUSS formuliert werden, * da jede Ein-, Ausgabe fehlerhaft sein kann: Datei nicht vorhanden ... * - Zahlenformat-Ausnahme KANN formuliert werden. Diese tritt in Kraft, wenn * der Nutzer eine ungültige Zahl eingibt. * * @version 1.0 vom 25.06.2010 * @author Uwe Lämmel */
public class TryCatch {
public static void main(String[] args) { LineIO ea = new LineIO(); boolean ende = false; do{ try{ int zahl=ea.readInt("Bitte Zahl eingeben: "); ende = (zahl== -1); } catch(NumberFormatException ex){ ea.writeln(ex.getMessage()+ " Das wahr falsch!"); ende=false; } catch( IOException io){} } while(!ende); ea.writeln("Ende"); }//main
}//TryCatch
Algorithmen Folie 32Uwe Lämmel
Zusammenfassung Suchen
– lineare S. in unsortierten Folgen– binäre S. in sortierten Folgen – Maximum
Sortieren– durch Auswahl, – durch Vertauschen: Bubble, Quicksort
Klasse– Bauplan-, Bibliotheks-, ausführbare Klasse
statische Methoden, statische Methode main
rekursives Programmieren
try-catch-Anweisung
Algorithmen Folie 33Uwe Lämmel
Aufgabe zum Suchen und Sortieren:Das Firmen-Telefonbuch
Für jeden Mitarbeiter wird verwaltet:– Name, Vorname, ZimmerNummer, ApparatNummer
Die Firma wird nicht mehr als 50 Mitarbeiter in den nächsten Jahren haben.
Funktionalität:– Erfassen eines neuen Mitarbeiters– Ändern der Daten eines Mitarbeiters– Suche nach ZimmerNummer eines Mitarbeiters– Suche nach TelefonNummer eines Mitarbeiters– Anzeige aller Mitarbeiter in einem Zimmer– Anzeige aller Mitarbeiter mit einer bestimmten
Apparatnummer– Ausgabe aller Informationen als Liste –sortiert nach:
Namen oder Zimmernummer
Implementieren Sie das
Telefonbuch mittels eines
Array von Mitarbeiter-
Objekten
