Sämtliche Klassen und Methoden sind als Vorschläge zu begreifen, wie Sie Ihr Programm strukturieren können, damit Sie nicht lange über den Programmentwurf nachdenken müssen. Die leeren Klammerpaare sollen nur verdeutlichen, dass es sich um Methodennamen handelt, die Signatur der Methode können Sie nach Ihrem Bedarf gestalten. Sofern nicht anders angegeben, dürfen Sie die Werte in ein Array einlesen, für das sie eine Länge von 1000 als immer ausreichend ansehen dürfen. Wenn eine andere Datenstruktur (z.B. verkettete Liste) verlangt wird, sollen Sie diese selbst implementieren und nicht die von Java bereit gestellte Klasse List verwenden. Sofern Sie nicht in der Vorlesung präsentierte Java-Klassen verwenden, müssen Sie auch das zugehörige Exception-Handling vollständig implementieren (z.B. von NumberFormatExceptions beim Umwandeln von Zahlen mit Integer.parseInt()). Aufgabe 1 (Bubblesort): Erstellen Sie eine doppelt verkettete Liste mittels einer Klasse DoublyChainedList, die neben den Zeigern auf das nächste auch Zeiger auf das vorige Element hat, indem Sie die Klasse Element aus der Vorlesung um ein geeignetes Attribut "previous" erweitern. Die Datenfelder müssen ausnahmensweise aus Zeitgründen nicht "private" markiert werden. Schreiben Sie sodann ein Programm, das natürliche Zahlen mit einer Methode readFromFile() in eine doppelt verkettete Liste aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Die Klasse DoublyChainedList sollte zu diesem Zweck eine Methode add() erhalten. Diese natürlichen Zahlen soll das Programm dann in einer Methode bubbleSort() aufsteigend sortieren, indem es von vorne nach hinten die Liste durchläuft und jeweils die Zahl an der aktuellen Stelle mit der nächsten Zahl in der Liste vergleicht und diese ggf. vertauscht, wenn die kleinere Zahl an der nächsten Stelle steht. Am Ende einer Iteration steht somit die größte Zahl am Ende der Liste. Wiederholen Sie also diese Iterationen so oft, bis die Liste komplett sortiert ist, also n-1 mal für n Elemente. (sog. Bubblesort-Algorithmus) Schreiben Sie ferner eine Methode printSorted(), die dann die sortierte Liste am Bildschirm ausgibt. Aufgabe 2 (entfaellt) Aufgabe 3 (Doppelt verkettete Liste): Erstellen Sie eine doppelt verkettete Liste mittels einer Klasse DoublyChainedList, die neben den Zeigern auf das nächste auch Zeiger auf das vorige Element hat, indem Sie die Klasse Element aus der Vorlesung um ein geeignetes Attribut "previous" erweitern. Die Datenfelder müssen ausnahmensweise aus Zeitgründen nicht "private" markiert werden. Schreiben Sie sodann ein Programm, das natürliche Zahlen mit einer Methode readFromFile() in eine doppelt verkettete Liste aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Die Klasse DoublyChainedList sollte zu diesem Zweck eine Methode add() erhalten. Unterbrechen Sie jeweils den Einlesevorgang nach jeder fünften Zahl, geben Sie die Zahlen in der Liste mittels einer zu erstellenden Methode print() aus und löschen Sie danach das vorletzte Element der Liste mit einer Methode delete(), die Sie in der Klasse der doppelt verketteten Liste implementieren. Aufgabe 4 (Insertionsort): Erstellen Sie eine verkettete Liste nach Vorbild der Vorlesung mittels einer Klasse ChainedList. Die Datenfelder müssen ausnahmensweise aus Zeitgründen nicht "private" markiert werden. Schreiben Sie sodann ein Programm, das natürliche Zahlen mit einer Methode readFromFile() in eine solche verkettete Liste aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Die Klasse ChainedList sollte zu diesem Zweck eine Methode addSorted() erhalten, die die gelesenen Zahlen gleich an der korrekten Stelle in die aufsteigend sortierte Liste einfügt. (sog. Insertionsort) Geben Sie am Schluss mit einer Methode print() der Klasse ChainedList die sortierte Liste aus. Aufgabe 5 (Oktalzahlen): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Geben Sie sodann alle Zahlen sowie ihre Oktal-Codierung in umgekehter Reihenfolge aus, d.h. ihre Darstellung zur Basis acht statt zur normalen Basis 10, indem Sie das in der Vorlesung genutzte z=Summe_i=0..n (a_i*b^i) mit b=8 statt b=2 für Binärdarstellung nutzen. Erstellen Sie dazu eine Methode getOctal() sowie eine Methode getReverseOctal(), die die Rückwärtsoktalcodierung zurück liefert und geben Sie jeweils in einer Zeile eine der gelesenen Zahlen als Oktalzahl vorwärts und rückwärts aus. Implementieren Sie ferner eine Methode isPalindrome(), die erkennt, ob es sich bei der Oktaldarstellung der Zahl um ein Palindrom handelt, also eine Zahl, deren Ziffern von vorn nach hinten in derselben Abfolge erscheinen wie umgekehrt von hinten nach vorn. Ziffern (einstellige Oktalzahlen) gelten dabei als Palindrom. Geben Sie dann alle eingelesenen Zahlen mittels print() aus und jeweils nebenstehend, ob es sich bei der Zahl um ein Palindrom handelt. Aufgabe 6 (Pythagoräische Zahlen): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Für jeweils drei aufeinander folgend gelesene Zahlen soll das Programm mittels einer Methode isPythagoreanTriangle() ermitteln, ob sich ein pythagoräisches Dreieck mit drei Seiten der gegebenen Längen konstruieren lässt. Anschließend soll das Programm mittels einer Methode computePythagoreanTriangles() alle pythagoräischen Dreiecke mit ganzzahligen Seitenlängen kleiner als maximal 100 ausgeben. Ferner sollen die mit einer Methode getQuerSumme() berechneten Quersummen der beteiligten Dreiecksseiten jeweils pro Dreieck summiert ausgegeben werden (also z.B. 6 8 10 Quersumme 15). Aufgabe 7 (Queue): Das Gegenstück zum Stack als Realisation des LIFO-Prinzips nennt sich Queue und setzt das FIFO-Prinzip (First-in-first-out) um, gibt also bei Aufruf der Methode pop() das Element zurück, das von allen derzeit in der Queue befindlichen als erstes mittels push() eingefügt wurde. Implementieren Sie eine Klasse Queue mit den o.g. Methoden, die auf der verketteten Liste aus der Vorlesung basiert, damit es keine Größenbeschränkung gibt. Dafür benötigen Sie zusätzlich einen Zeiger "tail" auf das aktuell letzte Element der Liste und müssen neue Elemente jeweils hinten anfügen. Schreiben Sie sodann eine Klasse QueueTest, die die main()-Funktion beinhaltet und natürliche Zahlen mit einer Methode readFromFile() aus einer Datei in eine Queue einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Geben Sie dabei nach jeder fünften gelesenen Zahl die Queue mittels einer Methode print() der Queue-Klasse aus und entfernen Sie sodann das erste Element aus der Queue mittels pop(). Aufgabe 8 (Schiebeverschlüsselung): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Die eingelesenen Zahlen sollen mittels einer Methode encrypt() verschlüsselt werden, die den zweiten dem Programm übergebenen Parameter als Zahl interpretiert, um die alle Ziffern einer übergebenen Zahl nach oben verschoben werden, wobei nach 9 wieder 0 folgen soll. (sog. wrap around) Den zweiten eingelesenen Parameter können Sie mittels Integer.parseInt(args[1]) in eine ganze Zahl umwandeln. Wenden Sie die Methode encrypt() auf alle eingelesenen Zahlen an und geben Sie die verschlüsselten Werte am Bildschirm aus. Aufgabe 9 (Zahlen zählen) Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Die Zahlen sollen mittels einer aus der Vorlesung bekannten verketteten Liste gezählt werden, deren Elemente gerade den Wert einer Zahl und ihre zugehörige Häufigkeit speichern. Geben Sie am Ende durch eine Methode print() einfach unsortiert jede Zahl mit der für sie gezählten Häufigkeit aus. Aufgabe 10 (Zahlen in Zeilen suchen): Die Zeilen einer Datei sind durch '\n' getrennt. Schreiben Sie ein Programm, das alle Zeilen einer Datei am Bildschirm ausgibt, die eine bestimmte positive Zahl beinhalten, die dem Programm als zweiter Parameter übergeben wird. Die Zahl muss dabei von Leerzeichen ' ' eingerahmt stehen. Der Name der Datei wird dem Programm als erster Parameter übergeben. Geben Sie neben den Trefferzeilen jeweils die Häufigkeit aus, mit der die gesuchte Zahl in der Zeile vorkommt. Aufgabe 11 (Lottoscheinauswertung): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Das Programm soll jeweils sieben aufeinanderfolgende Zahlen als Lottotipp in der Folge 6+Zusatzzahl interpretieren, wobei die erste Siebenerfolge genau die gezogenen Zahlen angibt. Gehen Sie von einer korrekten Eingabe aus und geben Sie für jeden der nachfolgenden Siebenerblöcke durch Test einzelner Zahlen mit einer Methode contains() aus, wieviele Richtige sich darin befinden (z.B. 3, 4+z, 0, 1+z). Aufgabe 12 (quadratische Gleichungen): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Interpretieren Sie jeweils zwei aufeinander folgend gelesene Zahlen als Koeffizienten p und q einer quadratischen Gleichung der Form x^2+px+q=0 und geben Sie deren Lösungen x_{1/2}=-p/2+-Math.sqrt((p/2)*(p/2)-q) aus. Führen Sie geeignete Fallunterscheidungen für nur eine Lösung und gar keine Lösung durch und verhindern Sie, dass eine negative Wurzel gezogen wird. Geben Sie jeweils die Lösung(en) aus. Erstellen Sie ferner eine Methode getReverse(), die die Ziffern der Darstellung einer Zahl umdreht und geben Sie auch die berechnete(n) Lösung(en) einer quadratischen Gleichung mit Koeffizienten getReverse(p) statt p und getReverse(q) statt q aus. Aufgabe 13 (Würfeln): Schreiben Sie ein Programm, das natürliche Zahlen mit einer Methode readFromFile() aus einer Datei einliest, deren Namen das Programm als ersten Kommandozeilenparameter entgegen nimmt. Jede natürliche Zahl repräsentiert dabei eine Anzahl Würfelwürfe mit dem normalen sechsseitigen Würfel, die Sie mit Math.random() durchführen sollen. Erscheint dabei auch nur eine 1, ist die Gewinnsumme 0. Sonst entspricht die Gewinnsumme nach dem i-ten Wurf gerade i, erhöht sich also mit jedem nicht-1-Wurf beginnend mit Gewinnsumme 1 um je 1. Simulieren Sie die Anzahl Würfelwürfe genau so oft, wie die gelesene Zahl angibt und geben Sie jede Zahl mit der zugehörigen durchschnittlichen Gewinnsumme in einer Zeile aus. Ermitteln Sie in einer weiteren Funktion die vom Gewinn her optimale Würfenwurfzahl (höchstens 100) durch Simulation von jeweils 500 Durchgängen, wenn es sich um einen 20-seitigen Würfel handelt, der die Zahlen 1-20 zeigt und geben Sie die Durchschnittswerte für 1-100 Würfe aus.