411 Datenstrukturen, Algorithmen
- 18 Mär. 2018
-
10:05
Performance Testing Was ist eine Datenstruktur?
„In der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt zur Speicherung und Organisation von Daten. Es handelt sich um eine Struktur, weil die Daten in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen. Datenstrukturen sind nicht nur durch die enthaltenen Daten charakterisiert, sondern vor allem durch die Operationen auf diesen Daten, die Zugriff und Verwaltung ermöglichen und realisieren.“ Quelle: https://de.wikipedia.org/wiki/Datenstruktur Das Wort Datenstruktur verrät schon, dass es sich um Daten handelt, die in irgendeiner Weise in Strukturen, die spezielle Eigenschaften besitzen, zusammengefasst werden. Diese Eigenschaften können sich z.B. darin auswirken, dass ein bestimmtes Datum (an dieser Stelle ist nicht das zeitliche Datum, sondern der Singular von Daten gemeint) schneller gefunden oder eine große Datenmenge platzsparender gespeichert werden kann.Sortier-algorithmen
1. Einleitung
Ein Sortieralgorithmus dient dazu um Werte in einem Array zu sortieren (z.b nach ihrer Grösse)
2. Selection Sort
Ein Selection Sort geht ein Array durch und vergleicht jede Stelle mit der ersten unsortierten. Die kleinste gefundene Ziffer tauscht er dann mit der ersten unsortierten.
Zur Veranschaulichung betrachten wir folgendes Array:
int[] a = {11, 9, 17, 5, 12}; sortiert unsortiert
Vervollständigen Sie den Durchlauf mit Ihren Kommentaren.
11 9 17 5 12
Initial Array, kleinstes Element 5, kommt an die Position a[0], indem wir a[0] mit a[3] vertauschen
5 9 17 11 12
Im unsortierten Bereich ist die 9 die kleinste Zahl, welche bereits an richtiger Stelle steht.
5 9 17 11 12
Die 17 an 3 Stelle wird mit den verbleibenden unsortierten Stellen verglichen. Da die 11 die kleinste verbleibende ist wird sie mir der 17 getauscht.
5 9 11 17 12
Die vorhin gerade getauschte 17 wird noch mit der letten Ziffer verglichen. Da diese in diesem Fall kleiner ist, werden sie auch noch getauscht.
5 9 11 12 17
Der unsortierte Bereich besteht aus noch einem einzigen Element, also sind wir fertig.
5 9 11 12 17
3. Implementation des selection sort Algorithmus
Implementieren Sie den Selection Sort Algorithmus in einer eigenen Klasse und kopieren Sie den Source Code hier hin. Tun Sie das, indem Sie eine Klasse SelectionSorter erstellen nach folgenden Vorgaben:
public static int[] selectionsort(int[] sortieren) { for (int i = 0; i < sortieren.length - 1; i++) { for (int j = i + 1; j < sortieren.length; j++) { if (sortieren[i] > sortieren[j]) { int temp = sortieren[i]; sortieren[i] = sortieren[j]; sortieren[j] = temp; } } } return sortieren; }
4. SELECTION SORT TESTPROGRAMM
Damit wir unsere Klasse SelectionSorter testen können, implementieren Sie folgende Klasse:
public static void main(String[] args) { int[] sortiert = selectionsort(randomZahlen(100)); for (int i = 0; i < sortiert.length; i++) { System.out.print(sortiert[i] + ", "); } } public static int[] randomZahlen(int anzahl){ int[] unsortiert = new int[anzahl]; for(int i = 0; i < unsortiert.length; i++){ unsortiert[i] = (int)(Math.random()*100); } return unsortiert; }
5. PROFILING DES SELECTION SORT ALGORITHMUS
Analysieren Sie nun wie viel Zeit der Selection Sort Algorithmus beansprucht, um Arrays mit verschiedener Grösse zu sortieren. Ergänzen Sie dazu den SelectionSortTester mit einer Zeitmessung folgendermassen:
public static void main(String[] args) { long startTime = System.currentTimeMillis(); int[] sortiert = selectionsort(randomZahlen(100)); long endTime = System.currentTimeMillis(); long time = endTime - startTime; System.out.println(time); for (int i = 0; i < sortiert.length; i++) { System.out.print(sortiert[i] + ", "); } } public static int[] randomZahlen(int anzahl){ int[] unsortiert = new int[anzahl]; for(int i = 0; i < unsortiert.length; i++){ unsortiert[i] = (int)(Math.random()*100); } return unsortiert; }
Bubblesort: Informatik (deutsch)
- 18 Mär. 2018
-
10:05
Encrypt / Decrypt in Java Auftrag Kryptographie:
Als praktisches Beispiel machen wir einen kurzen Ausflug in die Kryptographie und werden ein Programm schreiben, dass Dateien mit einem Schlüssel codiert (verschlüsselt) und mit dem gleichen Schlüssel wieder decodiert (entschlüsselt). Wir wenden hierzu eine einfache Methode an und ersetzen Zeichen systematisch durch andere Zeichen. Man sagt dieser Methode auch monoalphabetische Substitution.XOR-Encrypter
Wir haben bereits genug Wissen, um diesen Verschlüsselungsalgorithmus korrekt zu programmieren.// @author: Ralph.Maurer@iet-gibb.ch // Compilation: javac AB411_03_XOR.java // Execution: java -jar AB411_03_XOR.jar package ab411_03_xor; import java.io.*; import java.util.Scanner; public class AB411_03_XOR { public static String encrypt(String text, int key) { // wir werden die Zeichen einzeln codieren char[] zeichen = text.toCharArray(); // bitweise XOR-Verschlüsselung for (int i=0; i
AB411_03_XOR.java
// @author: Ralph.Maurer@iet-gibb.ch // Compilation: javac AB411_03_XOR.java // Execution: java -jar AB411_03_XOR.jar package xor_crypt; import java.io.*; import java.util.Scanner; public class AB411_03_XOR { public static String encrypt(String text, int key) throws FileNotFoundException { // wir werden die Zeichen einzeln codieren char[] zeichen = text.toCharArray(); // bitweise XOR-Verschlüsselung for (int i = 0; i < zeichen.length; i++) { // Mit (char)int wandle int in einen char um zeichen[i] = (char) (zeichen[i] ^ key); } // wir erzeugen aus dem Array vom Typ char einen String return new String(zeichen); } }
XOR_Crypt.java
package xor_crypt; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.util.Scanner; /** * * @author vmadmin */ public class XOR_Crypt { /** * @param args the command line arguments */ // static String readDatei = "/home/vmadmin/Dokumente/Modul411/Gedicht.txt"; // static String writeDatei = "/home/vmadmin/Dokumente/Modul411/ausgabe.txt"; static String text = ""; public static void main(String[] args) throws FileNotFoundException, IOException { // TODO code application logic here String key = args[0]; String inputDatei = "/home/vmadmin/Dokumente/Modul411" + args[1]; String outputDatei = "/home/vmadmin/Dokumente/Modul411" + args[2]; readText(key, inputDatei); writeText(outputDatei); } static public void readText(String key, String inputDatei) throws FileNotFoundException { // Dateiverzeichnispfad zur auszulesenden Datei. try (Scanner scn = new Scanner(new File(inputDatei), "UTF-8")) { while (scn.hasNextLine()) { text += AB411_03_XOR.encrypt(scn.nextLine(), Integer.parseInt(key)); } System.out.println(text); scn.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } } static public void writeText(String outputDatei) throws IOException { try { BufferedWriter myWriter = new BufferedWriter(new FileWriter(outputDatei, false)); myWriter.write(text); myWriter.close(); } catch (IOException eIO) { System.out.println("Folgender Fehler trat auf : " + eIO); } } }
- 18 Mär. 2018
-
10:05
Kurzreferenz Java (Refresher) Java is easy
Eine Programmiersprache oder Methoden und Konzepte der Softwareentwicklung lernt man nur mit Übung und wenn man selbst Programme in der neuen Sprache schreibt und neue Methoden und Konzepte anwendet. Je mehr, desto besser.Output - Einfache Ausgaben
Für die ersten Schritte in einer neuen Sprache benötigt man immer auch I/O-Routinen, um einfache Ein- und Ausgaben vornehmen zu können. Glücklicherweise kann man in Java nicht nur grafikorientierte Programme schreiben, sondern auch auf die Standardein- und -ausgabe zugreifen. Damit stehen für kleine Programme einfache I/O-Routinen zur Verfügung, die wie in den meisten konventionellen Programmiersprachen verwendet werden können. Mit Hilfe des Kommandos System.out.println können einfache Ausgaben auf den Bildschirm geschrieben werden. Nach jedem Aufruf wird eine Zeilenschaltung ausgegeben. Mit System.out.print kann diese auch unterdrückt werden. Beide Methoden erwarten ein einziges Argument, das von beliebigem Typ sein kann. Mit Hilfe des Plus-Operators können Zeichenketten und numerische Argumente miteinander verknüpft werden, so dass man neben Text auch Zahlen ausgeben kann:// @author: Ralph Maurer iet-gibb //Compilation: javac AB411_02_Output.java //Execution: java -jar AB411_02_Output.jar package ab411_02_Output; public class AB411_02_Output { public static void main(String[] args) { System.out.println("1+2=" + (1+2)); } }
Input - Einfache Eingaben
Leider ist es etwas komplizierter, Daten zeichenweise von der Tastatur zu lesen. Zwar steht ein vordefinierter Eingabe-Stream System.in zur Verfügung. Er ist aber nicht in der Lage, die eingelesenen Zeichen in primitive Datentypen zu konvertieren. Statt dessen muss zunächst eine Instanz der Klasse InputStreamReader und daraus ein BufferedReader erzeugt werden. Dieser kann dann dazu verwendet werden, die Eingabe zeilenweise zu lesen und das Ergebnis in einen primitiven Typ umzuwandeln. Das folgende Listing zeigt ein Programm, das zwei Ganzzahlen a und b einliest, die zweite Zahl durch 2 dividiert und das Resultat mit ersten Ganzzahl addiert. Sollte das Resultat eine negative Zahl sein, wird diese mit Math.abs() in den positiven Zahlenbereich überführt (Absoluter Wert). Das Ergebnis wird auf dem Bildschirm ausgegeben:// @author: Ralph Maurer iet-gibb //Compilation: javac AB411_02_Input.java //Execution: java -jar AB411_02_Input.jar package ab411_02_input; import java.io.*; public class AB411_02_Input{ public static void main(String[] args) throws IOException{ double a, b, c; BufferedReader din = new BufferedReader( new InputStreamReader(System.in)); System.out.println("Bitte a eingeben: "); a = Double.parseDouble(din.readLine()); System.out.println("Bitte b eingeben: "); b = Double.parseDouble(din.readLine()); c = Math.abs(a + b/2); System.out.println("abs(a + b/2)="+c); } } }
Die import-Anweisung am Anfang des Listings dient dazu, die Klassen des Pakets java.io bekanntzumachen. Ohne diese Anweisung würden sowohl BufferedReader als auch InputStreamReader vom Compiler nicht gefunden und es gäbe eine entsprechende Fehlermeldung. Werden die Zahlen 33 und -45.5 eingegeben, so lautet die Ausgabe des Programms:Bitte a eingeben: 33 Bitte a eingeben: 33 Bitte b eingeben: -45.5 abs(a + b/2)=10.25
Das Ergebnis von din.readLine ist ein String, der den Inhalt der Eingabezeile enthält. Sollen keine numerischen Datenwerte, sondern Zeichenketten eingelesen werden, kann der Rückgabewert auch direkt verwendet werden.Primitive Datentypen von Java:
Typname Größe Wrapper-Klasse Wertebereich Beschreibung boolean undefiniert java.lang.Boolean true / false Boolescher Wahrheitswert, Boolescher Typ char 16 bit java.lang.Character 0 ... 65.535 (z. B. 'A') Unicode-Zeichen (UTF-16) byte 8 bit java.lang.Byte -128 ... 127 Zweierkomplement-Wert short 16 bit java.lang.Short -32.768 ... 32.767 Zweierkomplement-Wert int 32 bit java.lang.Integer -2.147.483.648 ... 2.147.483.647 Zweierkomplement-Wert long 64 bit java.lang.Long -263 bis 263-1, ab Java 8 auch 0 bis 264 -1 Zweierkomplement-Wert float 32 bit java.lang.Float +/-1,4E-45 ... +/-3,4E+38 32-bit IEEE 754, es wird empfohlen, diesen Wert nicht für Programme zu verwenden, die sehr genau rechnen müssen. double 64 bit java.lang.Double +/-4,9E-324 ... +/-1,7E+308 64-bit IEEE 754, doppelte Genauigkeit Der logische Typ
Mit boolean besitzt Java einen eigenen logischen Datentyp und beseitigt damit eine oft diskutierte Schwäche von C und C++. Der boolean-Typ muss zwangsweise dort verwendet werden, wo ein logischer Operand erforderlich ist. Ganzzahlige Typen mit den Werten 0 oder 1 dürfen nicht als Ersatz für einen logischen Typen verwendet werden. Der Datentyp boolean kennt zwei verschiedene Werte, nämlich true und false. Neben den vordefinierten Konstanten gibt es keine weiteren Literale für logische Datentypen.Der Zeichentyp
Java wurde mit dem Anspruch entworfen, bekannte Schwächen bestehender Programmiersprachen zu vermeiden, und der Wunsch nach Portabilität stand ganz oben auf der Liste der Designziele. Konsequenterweise wurde der Typ char in Java daher bereits von Anfang an 2 Byte groß gemacht und speichert seine Zeichen auf der Basis des Unicode- Zeichensatzes. Als einziger integraler Datentyp ist char nicht vorzeichenbehaftet. char-Literale werden grundsätzlich in einfache Hochkommata gesetzt. Daneben gibt es String-Literale, die in doppelten Hochkommata stehen. Ähnlich wie C stellt Java eine ganze Reihe von Standard-Escape-Sequenzen zur Verfügung, die zur Darstellung von Sonderzeichen verwendet werden können:Zeichen Bedeutung \b Rückschritt (Backspace) \t Horizontaler Tabulator \n Zeilenschaltung (Newline) \r Seitenumbruch (Formfeed) \f Wagenrücklauf (Carriage return) \" Doppeltes Anführungszeichen \' Einfaches Anführungszeichen \\ Backslash \nnn Oktalzahl nnn (kann auch kürzer als 3 Zeichen sein, darf nicht größer als oktal 377 sein) Variablen
Variablen dienen dazu, Daten im Hauptspeicher eines Programms abzulegen und gegebenenfalls zu lesen oder zu verändern. In Java gibt es drei Typen von Variablen:
- Instanzvariablen, die im Rahmen einer Klassendefinition definiert und zusammen mit dem Objekt angelegt werden.
- Klassenvariablen, die ebenfalls im Rahmen einer Klassendefinition definiert werden, aber unabhängig von einem konkreten Objekt existieren.
- Lokale Variablen, die innerhalb einer Methode oder eines Blocks definiert werden und nur dort existieren.
Daneben betrachtet die Sprachdefinition auch Array-Komponenten und die Parameter von Methoden und Exception-Handlern als Variablen.
Eine Variable in Java ist immer typisiert. Sie ist entweder von einem primitiven Typen oder von einem Referenztypen. Mit Ausnahme eines Spezialfalls bei Array-Variablen, auf den wir später zurückkommen, werden alle Typüberprüfungen zur Compile-Zeit vorgenommen. Java ist damit im klassischen Sinne eine typsichere Sprache.
Um einer Variablen vom Typ T einen Wert X zuzuweisen, müssen T und X zuweisungskompatibel sein.
Variablen können auf zwei unterschiedliche Arten verändert werden:
1. durch eine Zuweisung
2. durch einen Inkrement- oder Dekrement-Operator
Deklaration von Variablen
Die Deklaration einer Variable erfolgt in der Form Typname Variablenname;
Dabei wird eine Variable des Typs Typname mit dem Namen Variablenname angelegt. Variablendeklarationen dürfen in Java an beliebiger Stelle im Programmcode erfolgen.
Lebensdauer/Sichtbarkeit von Variablen
Die Sichtbarkeit lokaler Variablen erstreckt sich von der Stelle ihrer Deklaration bis zum Ende der Methode, in der sie deklariert wurden. Falls innerhalb eines Blocks lokale Variablen angelegt wurden, sind sie bis zum Ende des Blocks sichtbar. Die Lebensdauer einer lokalen Variable beginnt, wenn die zugehörige Deklarationsanweisung ausgeführt wird. Sie endet mit dem Ende des Methodenaufrufs. Falls innerhalb eines Blocks lokale Variablen angelegt wurden, endet ihre Lebensdauer mit dem Verlassen des Blocks. Es ist in Java nicht erlaubt, lokale Variablen zu deklarieren, die gleichnamige lokale Variablen eines weiter außen liegenden Blocks verdecken. Das Verdecken von Klassen- oder Instanzvariablen ist dagegen zulässig.
Instanzvariablen werden zum Zeitpunkt des Erzeugens einer neuen Instanz einer Klasse angelegt. Sie sind innerhalb der ganzen Klasse sichtbar, solange sie nicht von gleichnamigen lokalen Variablen verdeckt werden. In diesem Fall ist aber der Zugriff mit Hilfe des this-Zeigers möglich: this.name greift immer auf die Instanz- oder Klassenvariable name zu, selbst wenn eine gleichnamige lokale Variable existiert. Mit dem Zerstören des zugehörigen Objekts werden auch alle Instanzvariablen zerstört.
Klassenvariablen leben während der kompletten Laufzeit des Programms. Die Regeln für ihre Sichtbarkeit entsprechen denen von Instanzvariablen.
Arrays
Arrays in Java unterscheiden sich dadurch von Arrays in anderen Programmiersprachen, dass sie Objekte sind. Obwohl dieser Umstand in vielen Fällen vernachlässigt werden kann, bedeutet er dennoch:
- dass Array-Variablen Referenzen sind,
- dass Arrays Methoden und Instanz-Variablen besitzen,
- dass Arrays zur Laufzeit erzeugt werden.
Dennoch bleibt ein Array immer eine (möglicherweise mehrdimensionale) Reihung von Elementen eines festen Grundtyps. Arrays in Java sind semi-dynamisch, d.h., ihre Größe kann zur Laufzeit festgelegt, später aber nicht mehr verändert werden.
Deklaration einer Array-Variablen
Erzeugen eines Arrays und Zuweisung an die Array-Variable
Die Deklaration eines Arrays entspricht syntaktisch der einer einfachen Variablen, mit dem Unterschied, dass an den Typnamen eckige Klammern angehängt werden:
int[] zahlen; double[] kommazahlen; boolean[] check;
Zum Zeitpunkt der Deklaration wird noch nicht festgelegt, wie viele Elemente das Array haben soll. Dies geschieht erst später bei seiner Initialisierung, die mit Hilfe des new-Operators oder durch Zuweisung eines Array-Literals erfolgt. Sollen also beispielsweise die oben deklarierten Arrays 2, 4 und 6 Elemente haben, würden wir das Beispiel wie folgt erweitern:
a = new int[2]; b = new double[4]; c = new boolean[6];
Ist bereits zum Deklarationszeitpunkt klar, wie viele Elemente das Array haben soll, können Deklaration und Initialisierung zusammen geschrieben werden:
int[] a = new int[2]; double[] b = new double[4]; boolean[] c = new boolean[6];
Alternativ zur Verwendung des new -Operators kann ein Array auch literal initialisiert werden.
Dazu werden die Elemente des Arrays in geschweifte Klammern gesetzt und nach einem Zuweisungsoperator zur Initialisierung verwendet. Die Größe des Arrays ergibt sich aus der Anzahl der zugewiesenen Elemente:
int[] x = {1,2}; boolean[] y = {true, false};
Das Beispiel generiert ein int-Array x mit zwei Elementen und ein boolean-Array y mit zwei Elementen. Anders als bei der expliziten Initialisierung mit new muss die Initialisierung in diesem Fall unmittelbar bei der Deklaration erfolgen.
Zugriff auf Array-Elemente
Bei der Initialisierung eines Arrays von n Elementen werden die einzelnen Elemente von 0 bis n-1 durchnummeriert. Der Zugriff auf jedes einzelne Element erfolgt über seinen numerischen
Index, der nach dem Array-Namen in eckigen Klammern geschrieben wird. Das nachfolgende Beispiel deklariert zwei Arrays mit Elementen des Typs int bzw. boolean, die dann ausgegeben werden:
Bitte a eingeben: 33 public class array1 { public static void main(String[] args) { int[] prim = new int[5]; boolean[] b = {true,false}; prim[0] = 2; prim[1] = 3; prim[2] = 5; prim[3] = 7; prim[4] = 11; System.out.println("prim hat "+prim.length+" Elemente"); System.out.println("b hat "+b.length+" Elemente"); System.out.println(prim[0]); System.out.println(prim[1]); System.out.println(prim[2]); System.out.println(b[0]); System.out.println(b[1]); } }
Die Ausgabe des Programms ist:
prim hat 5 Elemente b hat 2 Elemente
2
3 5
true
false
Der Array-Index muss vom Typ int sein. Aufgrund der vom Compiler automatisch vorgenommenen Typkonvertierungen sind auch short, byte und char zulässig. Jedes Array hat eine Instanzvariable length, die die Anzahl seiner Elemente angibt. Indexausdrücke werden vom Laufzeitsystem auf Einhaltung der Array-Grenzen geprüft. Sie müssen größer gleich 0 und kleiner als length sein.
Mehrdimensionale Arrays
Mehrdimensionale Arrays werden erzeugt, indem zwei oder mehr Paare eckiger Klammern bei der Deklaration angegeben werden. Mehrdimensionale Arrays werden als Arrays von Arrays angelegt. Die Initialisierung erfolgt analog zu eindimensionalen Arrays durch Angabe der Anzahl der Elemente je Dimension.
Der Zugriff auf mehrdimensionale Arrays geschieht durch Angabe aller erforderlichen Indizes, jeweils in eigenen eckigen Klammern. Auch bei mehrdimensionalen Arrays kann eine literale Initialisierung durch Schachtelung der Initialisierungssequenzen erreicht werden. Das folgende Beispiel erzeugt ein Array der Größe 2 * 3 und gibt dessen Elemente aus:
Bitte a eingeben: 33 public class array2 { public static void main(String[] args) { int[][] a = new int[2][3]; a[0][0] = 10; a[0][1] = 20; a[0][2] = 30; a[1][0] = 40; a[1][1] = 50; a[1][2] = 60; System.out.println(""+a[0][0]+a[0][1]+a[0][2]); System.out.println(""+a[1][0]+a[1][1]+a[1][2]); } }
Die Ausgabe des Programms ist:
102030
405060
Da mehrdimensionale Arrays als geschachtelte Arrays gespeichert werden, ist es auch möglich, nichtrechteckige Arrays zu erzeugen. Das folgende Beispiel deklariert und initialisiert ein zweidimensionales dreieckiges Array und gibt es auf dem Bildschirm aus. Gleichzeitig zeigt es die Verwendung der length-Variable, um die Größe des Arrays oder Sub-Arrays herauszufinden.
Bitte a eingeben: 33 public class array3 { public static void main(String[] args) { int[][] a = {{0}, {1,2}, {3,4,5}, {6,7,8,9}}; for (int i=0; i < a.length; ++i) { for (int j=0; j < a[i].length; ++j) { System.out.print(a[i][j]); } System.out.println(); } } }
Operatoren
Arithmetische Operatoren
Operator
Bezeichnung
Bedeutung
+
Positives Vorzeichen
+n ist gleichbedeutend mit n
-
Negatives Vorzeichen
-n kehrt das Vorzeichen von n um
+
Summe
a + b ergibt die Summe von a und b
-
Differenz
a - b ergibt die Differenz von a und b
*
Produkt
a * b ergibt das Produkt aus a und b
/
Quotient
a / b ergibt den Quotienten von a und b. Bei integralen Typen handelt es sich hierbei um die ganzzahlige Division ohne Rest.
%
Restwert
a % b ergibt den Rest der ganzzahligen Division von a durch b. In Java lässt sich dieser Operator auch auf Fließkommazahlen anwenden.
++
Präinkrement
++a ergibt a+1 und erhöht a um 1. In Java lässt sich dieser Operator auch auf Fließkommazahlen anwenden.
++
Postinkrement
a++ ergibt a und erhöht a um 1. In Java lässt sich dieser Operator auch auf Fließkommazahlen anwenden.
--
Prädekrement
--a ergibt a-1 und verringert a um 1. In Java lässt sich dieser Operator auch auf Fließkommazahlen anwenden.
--
Postdekrement
a-- ergibt a und verringert a um 1. In Java lässt sich dieser Operator auch auf Fließkommazahlen anwenden.
Zuweisungsoperatoren
Operator
Bezeichnung
Bedeutung
=
Einfache Zuweisung
a = b weist a den Wert von b zu und liefert b als Rückgabewert.
+
=
Additionszuweisung
a += b weist a den Wert von a + b zu und liefert a + b als Rückgabewert.
-
=
Subtraktionszuweisung
a -= b weist a den Wert von a - b zu und liefert a - b als Rückgabewert.
*
=
Multiplikationszuweisung
a *= b weist a den Wert von a * b zu und liefert a * b als Rückgabewert.
/
=
Divisionszuweisung
a /= b weist a den Wert von a / b zu und liefert a / b als Rückgabewert.
%
=
Modulozuweisung
a %= b weist a den Wert von a % b zu und liefert a % b als Rückgabewert.
&
=
UND-Zuweisung
a &= b weist a den Wert von a & b zu und liefert a & b als Rückgabewert.
|
=
ODER-Zuweisung
a |= b weist a den Wert von a | b zu und liefert a | b als Rückgabewert.
^
=
Exklusiv-ODER-Zuweisung
a ^= b weist a den Wert von a ^ b zu und liefert a ^ b als Rückgabewert.
<
<
=
Linksschiebezuweisung
a <<= b weist a den Wert von a << b zu und liefert a << b als Rückgabewert.
>
>
=
Rechtsschiebezuweisung
a >>= b weist a den Wert von a >> b zu und liefert a >> b als Rückgabewert.
>
>
>
=
Rechtsschiebezuweisung mit Nullexpansion
a >>>= b weist a den Wert von a >>> b zu und liefert a >>> b als Rückgabewert.
Relationale Operatoren
Operator
Bezeichnung
Bedeutung
==
Gleich
a == b ergibt true, wenn a gleich b ist. Sind a und b Referenztypen, so ist der Rückgabewert true, wenn beide Werte auf dasselbe Objekt zeigen.
!=
Ungleich
a != b ergibt true, wenn a ungleich b ist. Sind a und b Objekte, so ist der Rückgabewert true, wenn beide Werte auf unterschiedliche Objekte zeigen.
<
Kleiner
a < b ergibt true, wenn a kleiner b ist.
<=
Kleiner gleich
a <= b ergibt true, wenn a kleiner oder gleich b ist.
>
Größer
a > b ergibt true, wenn a größer b ist.
>=
Größer gleich
a >= b ergibt true, wenn a größer oder gleich b ist.
Logische Operatoren
Operator
Bezeichnung
Bedeutung
!
Logisches NICHT
!a ergibt false, wenn a wahr ist, und true, wenn a falsch ist.
&&
UND mit Short-CircuitEvaluation
a && b ergibt true, wenn sowohl a als auch b wahr sind. Ist a bereits falsch, so wird false zurückgegeben und b nicht mehr ausgewertet.
||
ODER mit Short-CircuitEvaluation
a || b ergibt true, wenn mindestens einer der beiden Ausdrücke a oder b wahr ist. Ist bereits a wahr, so wird true zurückgegeben und b nicht mehr ausgewertet.
&
UND ohne Short-CircuitEvaluation
a & b ergibt true, wenn sowohl a als auch b wahr sind. Beide Teilausdrücke werden ausgewertet.
|
ODER ohne Short-CircuitEvaluation
a | b ergibt true, wenn mindestens einer der beiden Ausdrücke a oder b wahr ist. Beide Teilausdrücke werden ausgewertet.
^
Exklusiv-ODER
a ^ b ergibt true, wenn beide Ausdrücke einen unterschiedlichen Wahrheitswert haben.
Anweisungen
Die if-Anweisung
Syntax if (ausdruck) anweisung; oder if (ausdruck) anweisung1; else anweisung2;Die if-Anweisung wertet zunächst den Ausdruck aus. Danach führt sie die Anweisung genau dann aus, wenn das Ergebnis des Ausdrucks true ist. Ist Ausdruck hingegen false, so wird die Anweisung nicht ausgeführt, sondern mit der ersten Anweisung nach der if-Anweisung fortgefahren.
Mit der if-else-Anweisung gibt es eine weitere Verzweigung in Java. Falls Ausdruck wahr ist, wird Anweisung1 ausgeführt, andernfalls Anweisung2. Eine der beiden Anweisungen wird also in jedem Fall ausgeführt.
Die switch-Anweisung
Syntax
switch (ausdruck)
{ case constant: anweisung;
...
default:
}
Die switch-Anweisung ist eine Mehrfachverzweigung. Zunächst wird der Ausdruck, der vom Typ byte, short, char, int oder der Wert eines Aufzählungstyps sein muss, ausgewertet. In Abhängigkeit vom Ergebnis wird dann die Sprungmarke angesprungen, deren Konstante mit dem Ergebnis des Ausdrucks übereinstimmt. Die Konstante und der Ausdruck müssen dabei zuweisungskompatibel sein.
Das optionale default-Label wird dann angesprungen, wenn keine passende Sprungmarke gefunden wird. Ist kein default-Label vorhanden und wird auch keine passende Sprungmarke gefunden, so wird keine der Anweisungen innerhalb der switch-Anweisung ausgeführt. Jede Konstante eines case-Labels darf nur einmal auftauchen. Das default-Label darf maximal einmal verwendet werden.
Die while-Schleife
Syntax  while (ausdruck)
anweisung;
Zuerst wird der Testausdruck, der vom Typ boolean sein muss, geprüft. Ist er true, wird die Anweisung ausgeführt, andernfalls wird mit der ersten Anweisung hinter der Schleife weitergemacht. Nachdem die Anweisung ausgeführt wurde, wird der Testausdruck erneut geprüft usw. Die Schleife wird beendet, sobald der Test false ergibt.
Die do-Schleife Syntax do anweisung; while (ausdruck);
Die do-Schleife arbeitet nichtabweisend, d.h. sie wird mindestens einmal ausgeführt. Da zunächst die Schleifenanweisung ausgeführt und erst dann der Testausdruck überprüft wird, kann die do-Schleife frühestens nach einem Durchlauf regulär beendet werden. Die Bearbeitung der Schleife wird immer dann beendet, wenn der Test des Schleifenausdrucks false ergibt.
Die for-Schleife
Syntax
for (init; test; update) anweisung;
Der Kopf der for-Schleife besteht aus drei Ausdrücken, die jeder für sich optional sind:
Der init-Ausdruck wird einmal vor dem Start der Schleife aufgerufen. Er dient dazu, Initialisierungen durchzuführen, die durch die Auswertung von Ausdrücken mit Nebeneffekten verursacht werden. Der Rückgabewert der Ausdrücke wird vollständig ignoriert. Der init-Teil darf auch aus mehreren Ausdrücken bestehen, wenn die einzelnen
Teilausdrücke durch Kommata getrennt sind. Diese syntaktische Erweiterung ist allerdings nur innerhalb des Initialisierungsteils einer for-Schleife erlaubt.
Fehlt der Initialisierungsteil, wird keine Initialisierung im Kopf der Schleife durchgeführt. Der init-Teil darf auch Variablendeklarationen enthalten, beispielsweise, um einen
Schleifenzähler zu erzeugen. Die Variablen müssen bei der Deklaration initialisiert werden. Sichtbarkeit und Lebensdauer erstrecken sich auf den Block, der die Schleifenanweisungen enthält. Damit ist es möglich, den Namen einer Schleifenvariablen innerhalb einer Methode mehrfach zu deklarieren.
Der test-Teil bildet den Testausdruck der Schleife. Analog zur while-Schleife wird er am Anfang der Schleife ausgeführt und die Schleifenanweisung wird nur ausgeführt, wenn die Auswertung des Testausdrucks true ergibt. Fehlt der Testausdruck, so setzt der Compiler an seiner Stelle die Konstante true ein.
Der update-Ausdruck dient dazu, den Schleifenzähler zu verändern. Er wird nach jedem Durchlauf der Schleife ausgewertet, bevor der Testausdruck das nächste Mal ausgewertet wird. Wie der init-Teil darf auch der update-Teil aus mehreren Ausdrücken bestehen. Der Rückgabewert des Ausdrucks wird ignoriert. Fehlt der update-Ausdruck, so wird keine automatische Modifikation des Schleifenzählers durchgeführt.
In Java gibt es zwei weitere Möglichkeiten, die normale Auswertungsreihenfolge in einer Schleife zu verändern. Taucht innerhalb einer Schleife eine break-Anweisung auf, wird die
Schleife verlassen und das Programm mit der ersten Anweisung nach der Schleife fortgesetzt.
Taucht dagegen eine continue-Anweisung auf, springt das Programm an das Ende des
Schleifenrumpfs und beginnt mit der nächsten Iteration.
Java, the World's Most Populous Island
- 22 Apr. 2018
10:05Datenstrukturen und Algorithmen Die drei Ebenen des Algorithmenentwurfs
1. Spezifikation Vor dem Schreiben eines Programmes muss das Problem spezifiziert werden. Es stellen sich präzise Fragen, die von Vorteil vor der eigentlichen Programmierarbeit beantwortet werden.
2. Algorithmus Vor dem Schreiben eines Programmes muss der genaue Ablauf von elementaren Aktionen, die das Problem schrittweise lösen, klar sein. Alle Einzelschritte und Vorbedingungen müssen bekannt sein und können mit zahlreichen Methoden dargestellt werden.
3. Programm Konkrete Formulierung des Algorithmus in einer Programmiersprache (sog. "glue code"). In Modul 411 wenden wir Java an.Spezifikation
Als Beispiel nehmen wir den euklidischen Algorithmus des grössten gemeinsamen Teiler ggT(a,b). Für beliebige Zahlen a und b wird der ggT(a,b) berechnet, also die grösste Zahl, die sowohl a und b teilt.
Wir unterscheiden in der Spezifikation zwischen Pre-conditions (Vorbedingungen) und Post- conditions (Nachbedingungen).Beispiele von Pre-conditions für den ggT(a,b):
-
Welche Zahlen a, b sind zugelassen? àPositive oder auch negative Zahlen?
-
Welche Grundoperationen sind erlaubt? à '+', '-' oder auch div und mod?
Beispiele für Post-conditions für den ggT(a,b):
-
Was wird ausgegeben, falls m, n < 0?
-
Was wird ausgegeben, falls die Eingabe nicht den pre-conditions genügt?
Pre-conditions umfassen alle relevanten Eigenschaften, die vor Ausführung des Algorithmus gelten.
Post-conditions umfassen alle relevanten Eigenschaften, die nach Ausführung des Algorithmus gelten.Das Praxisproblem der Spezifikation
In der Praxis werden häufig weniger formale Beschreibungen in natürlicher Sprache verwendet (Pflichtenhefte).
-
- Häufig umfangreich, mehrdeutig, inkonsistent
-
- Ist die Ausgabespezifikation das, was der Kunde wollte?
-
- Bekommt der Kunde von seinen "Zulieferern" das, was die Eingabespezifikation sagt?
-
- Tut der Algorithmus das, was in der Spezifikation steht?
-
- Tut der Algorithmus das, was der Kunde wollte?
Tipp: versuchen Sie, für Algorithmen immer eine "möglichst formale" Spezifikation zu schreiben!
Algorithmus
Begriffe in der Definition für "Algorithmus" nach Adam Riese
Ausführung des Algorithmus erfolgt in diskreten Schritten:
-
einzelne, einfache Elementaraktionen
-
Welche dies sind hängt vom sog. Algorithmischen Modell ab
-
- Maschineninstruktionen?
-
- Hochsprachliche Konstruktionen (JAVA)?
-
- Mathematische Funktionen wie z.B. log(x)?
-
Geordnete Menge:
Die Reihenfolge der Schritte genügt gewissen Regeln.
-
- Schritte müssen nicht unbedingt nacheinander ausgeführt werden.
-
- Es ist erlaubt, dass mehrere Schritte parallel von verschiedenen Recheneinheiten
ausgeführt werden (parallele oder verteilte Algorithmen).
-
- Bei einer einzigen aktiven Recheneinheit allerdings gibt es einen ersten, zweiten,
dritten Schritt usw. (sequentielle Algorithmen).
Eindeutigkeit:
Der Verfahrensablauf ist zu jedem Zeitpunkt determiniert, d.h.,
-
- zum Zeitpunkt der Ausführung eines Schrittes muss eindeutig und vollständig
festgelegt sein, was zu tun ist; und
-
- gleiche Eingaben sollen zum gleichen Ablauf und Ergebnis führen.
-
Ausnahme: randomisierte Algorithmen, deren Ablauf von (mathematisch bestimmten)
Zufallsgrößen abhängt. Weitere Ausnahme ist die Parallelisierung durch
Recheneinheiten.
Effektivität:
Jeder Schritt des Verfahrens muss effektiv mechanisch oder rechenbar ausführbar sein.
- Bemerkung: "Effektivität" (= erzielt das gewünschte Resultat) ist nicht zu verwechseln
mit "Effizienz" (= Wirtschaftlichkeit)
Terminierung:
Der Algorithmus hält nach endlich vielen Schritten mit einem Ergebnis an. Sofern die Eingaben der Eingabespezifikation genügen.
Nicht erlaubt sind z.B. Schrittfolgen, die nie ein Ergebnis liefern:-
Starte mit Zahl 0
-
Addiere 2
-
Falls Ergebnis ungerade, halte an, sonst weiter bei Schritt 2.
Korrektheit:
Korrektheit heisst, dass jedes berechnete Ergebnis der Ausgabespezifikation genügt, sofern die Eingaben der Eingabespezifikation eingehalten sind. D.h., Ein- und Ausgabeparameter genügen im Falle der Terminierung immer den Spezifikationen.
Es gibt zahlreiche Methoden zur Darstellung eines Algorithmus:
1. Pseudocode Beispiel Pseudocode
2. Flussdiagramme (Ablaufdiagramm)
3. Struktogramme
4. UML-Diagramme
5. Programmcode
Das Collatz-Problem
Das Collatz-Problem (auch als ULAM Funktion oder als (3n+1)-Vermutung) bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde.
Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:
-
Beginne mit irgendeiner natürlichen Zahl n > 0.
-
Ist n gerade, so nimm als Nächstes n/2,
-
Ist n ungerade, so nimm als Nächstes 3n + 1.
-
Wiederhole die Vorgehensweise mit der erhaltenen Zahl, solange n ≠ 1.
So erhält man zum Beispiel für die Startzahl n = 19 die Folge
19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
Anscheinend mündet jede Folge mit n > 0 in den Zyklus 4, 2, 1 unabhängig davon, welche Startzahl n man probiert hat. Die Collatz-Vermutung lautet:
Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1 egal, mit welcher natürlichen Zahl n > 0 man beginnt.
Trotz zahlreicher Anstrengungen gehört diese Vermutung noch immer zu den ungelösten Problemen der Mathematik. Mehrfach wurden Preise für eine Lösung angeboten.//BeiSpeil https://www.apfeltalk.de/community/threads/java-collatz-folge.182905/ public class colatz { public static void main( String[] args) { int n = 27; while ( n > 1) { if ( n%2 == 0) { n = n /2; } else { n = 3*n+1; } System.out.println(n); }} }
Java Übungen - 4 - Collatz Problem