[2022] Programmieren 2 - Assignment 1: Mergesort
Programmieren 2 SoSe 2022
Assignment 1
Ihre Abgabe muss aus einer einzelnen zip-Datei bestehen, die den Quellcode und ggf. ein PDF-Dokument bei Freitextaufgaben enthält. Beachten Sie, dass Dateien mit Umlauten im Dateinamen nicht hochgeladen werden können. Entfernen Sie die daher vor der Abgabe die Umlaute aus dem Dateinamen. Überprüfen Sie nach Ihrer Abgabe, ob der Upload erfolgreich war. Bei technischen Problemen, wenden Sie sich an Patric Plattner oder Dennis Stanke. Es wird eine Plagiatsüberprüfung durchgeführt. Gefundene Plagiate führen zum Ausschluss von der Veranstaltung. In dieser Veranstaltung wird ausschließlich die Java/JavaFX Version 17 verwendet. Code und Kompilate anderer Versionen sind nicht zulässig. Ihre Abgaben sollen die vorgegebenen Dateinamen verwenden. Wiederholter Verstoß gegen diese Regel kann zu Punktabzügen führen.
Aufgabe 1: Mergesort (1 Punkt)
In dieser Aufgabe sollen Sie den Sortieralgorithmus Mergesort in Java implementieren. Schreiben Sie Ihren Code in eine Datei namens Mergesort.java in der entsprechenden Mergesort Klasse. Nutzen Sie hier keine Funktionen aus der Standardbibliothek außer die Methoden System.out.print() und System.out.println(). Beispielsweise sollen Sie keine Methoden aus java.util.Arrays benutzen.
a) Erstellen Sie eine public static void main(String[] args) Methode.
Erstellen Sie anschließend eine Methode static String arrayToString(int[] arr), welche den Inhalt eines be-
liebigen Integer Arrays als String zurückgibt:
Beispiel:
1 int[] bsp = {1,2,3,4,5};
2 System.out.println(arrayToString(bsp));
Ausgabe:
1 [1,2,3,4,5]
b) Implementieren Sie die Methode public static int[] merge(int[] leftArray, int[] rightArray). Methode soll zwei Integer Arrays entgegennehmen und diese aufsteigend sortiert zusammenfügen. Die Eingabear- rays werden immer bereits aufsteigend sortiert sein. Die Eingabearrays sollen nicht verändert werden. Sollten Sie Probleme haben einen guten Algorithmus dafür zu finden, schauen Sie in die Lösungshinweise am Ende der Aufgabe.
Beispiel:
1 int[] leftList = {1,3,5,7};
2 int[] rightList = {2,4,6,7};
3 int[] result = merge(leftList, rightList);
4 System.out.println(arrayToString(result));
Diese
Ausgabe:
1 [1,2,3,4,5,6,7,7]
c) Implementieren Sie die Methode public static int[] mergeSort(int[] array). Diese Methode soll mithilfe des Mergesort Algorithmus eine Liste aufsteigend sortieren. Das Eingabearray darf nicht verändert werden. Nutzen Sie dabei die merge Methode aus der vorherigen Teilaufgabe. Der Mergesort Algorithmus funktioniert wiefolgt:
1. Hat das Eingabearray weniger als zwei Elemente, geben Sie das Eingabearray zurück, Ende der Methode.
2. Sonst: Teilen Sie das Eingabearray in der Mitte in zwei Arrays auf, die wir hier left und right nennen.
3. Rufen Sie Mergesort rekursiv auf left und right auf. Wir nennen die Ergebnisse leftSorted und rightSorted
4. Nutzen Sie merge um leftSorted und rightSorted zusammenzufügen. Geben Sie das Ergebnis davon zurück.
Erstellen Sie drei unsortierte Arrays in der main Methode und sortieren Sie diese mit Ihrer mergeSort Imple- mentierung.
Lösungshinweise Hier finden Sie eine Erklärung für den Mergesort Algorithmus: https://en.wikipedia.org/ wiki/Merge_sort
Aufgabe 2: Primzahlensieb (1 Punkt)
In dieser Aufgabe sollen Sie das Sieb des Eratosthenes (https://de.wikipedia.org/wiki/Sieb_des_Eratosthenes) implementieren. Wir wenden dabei einen kleinen Trick an, um eine möglichst simple Lösung für das Problem
zu implementieren. Schreiben Sie Ihren Code in eine Datei namens Primes.java in der entsprechenden Primes Klasse. Nutzen sie hier keine Funktionen aus der Standardbibliothek ausser die Methoden System.out.print()
und System.out.println(). Beispielsweise sollen Sie keine Methoden aus java.util.Arrays benutzen.
a) Erstellen sie eine public static void main(String[] args) Methode.
Erstellen Sie anschließend die Methoden static String intArrayToString(int[] arr) und static String boolArrayToString(boolean[] arr), welche den Inhalt eines beliebigen Integer bzw. Boolean Arrays als String zurückgibt:
Beispiel:
1 int[] bspInt = {1,2,3,4,5};
2 boolean[] bspBool = {true, false, true, false, true};
3 System.out.println(intArrayToString(bspInt));
4 System.out.println(boolArrayToString(bspBool));
Ausgabe:
1 [1,2,3,4,5]
2 [t,f,t,f,t]
Sie können eine beliebige sinnvolle Darstellung für Booleans verwenden.
b) Erstellen Sie eine Methode public static boolean[] fillArray(int n). Diese Methode soll ein Array der
Länge n + 1 zurückgeben, wobei die ersten beiden Elemente false sein sollen und der Rest true.
Beispiel:
1 boolean[] arr = fillArray(10);
2 System.out.println(boolArrayToString(arr));
Ausgabe:
1 [f,f,t,t,t,t,t,t,t,t,t]
c) Erstellen Sie eine Methode public static void filterArray(boolean[] arr). Diese Methode soll nun den tatsächlichen Algorithmus des Siebs des Eratosthenes anwenden. Dazu behandeln Sie das Eingabearray als die Liste der Zahlen, die wir uns aufgeschrieben haben. Dabei repräsentiert der Index die aufgeschriebene Zahl und der dazugehörige Wert, ob die Zahl durchgestrichen ist, oder nicht. Sie sollen das Eingabearray verändern. Als Beispiel würde das Array {false, false, true, true, false, true, false} folgende Zahlenliste bedeuten: [0,1,2,3,4,5,6]
Nutzen Sie den folgenden Algorithmus:
1. Iterieren Sie solange über das Array, bis Sie eine Zahl finden, die nicht durchgestrichen ist (also bis Sie den Wert true finden). Wir nennen die Zahl (also den Index) p. Wenn Sie kein weiteres Element finden, sind Sie fertig.
2. Streichen Sie alle Vielfachen von p (also setzen Sie die Werte an allen Indizes, die vielfache von p sind, auf false).
3. Gehen Sie zu Schritt 1 zurück. Beispiel:
1 boolean[] arr = fillArray(20);
2 filterArray(arr);
3 System.out.println(boolArrayToString(arr));
Ausgabe:
1 [f,f,t,t,f,t,f,t,f,f,f,t,f,t,f,f,f,t,f,t,f]
d) Erstellen Sie eine Metohde public static int[] primes(int n). Diese Methode soll ein Array aller Primzahlen ≤ n zurückgeben. Nutzen Sie dazu die Methoden aus den vorherigen Aufgaben. Das Array darf nicht größer als die Anzahl an Primzahlen ≤ n sein. Hinweis: Um das Ausgabearray der Methode zu erstellen, zählen Sie die Anzahl der trues von dem Ergebnis von filterArray, erstellen Sie ein Integer Array, das so viele Elemente hat und schreiben Sie die Primzahlen in dieses Array.
Beispiel:
1 int[] arr = primes(20);
2 System.out.println(intArrayToString(arr));
Ausgabe:
1 [2,3,5,7,11,13,17,19]
Aufgabe 3: Debugging
Jedes Assignment wird eine Debugging-Aufgabe enthalten. In diesen Aufgaben werden Sie einen fehlerhaften Java Codeabschnitt bekommen. Diese Fehler können syntaktisch oder semantisch sein. Es kann sich dabei um Compiler- oder Laufzeitfehler handeln. Sie dürfen den Code kompilieren und ausführen um die Fehler zu finden. Arbeiten Sie in den Template-Dateien in der Debug01.zip. Diese finden Sie im Stud.IP. Hier nochmal der zu korrigierende Code:
1 ckass Debug {
2 // Methode that checks whether a given number is prime
3 public static boolean isPrime(int n) {
// Return false if number is one, zero or negative
4 if (n <= 2) {
5 return false;
6 }
7 // Check for all factors smaller and equal to n/2 whether it is a prime factor. // If it is a prime factor, return false.
for (int i = 2; i <= n / 2; i--) {
8 if (n % i == 0) {
9 return true;
10 }
11 }
12 // If no prime factor was found, return true.
13 return true;
14 }
15 // Method that prints all numbers in an array that are prime
16 public static void printPrime(int[] arr) {
17 for (int i = 0; i <= arr.length; i++) {
18 if (isPrime(arr[i])) {
19 System.out.println(arr[i]);
20 }
21 }
22 }
23 int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
24 printPrime(arr);
25 // output should be as follows: // 2
// 3
// 5
26 // 7
27 }
a) Der Codeabschnitt enthält c.a. 4 Fehler. Kompilieren und führen Sie den Code aus. Suchen Sie anhand der Fehlermeldungen des Compilers oder der Laufzeitfehlermeldungen Fehler im Code und korrigieren Sie diese. Kommentieren Sie am Ende der jeweiligen Zeile, was Sie korrigiert haben.
Erstellen Sie während der Fehlerkorrektur einen Blockkommentar unter dem Code, in dem Sie die Fehler doku- mentieren. Schreiben Sie die Zeile(n) des Fehlers auf und beschreiben Sie den Fehler. Kopieren sie die Fehler- meldung, sofern es eine gab, anhand welcher Sie den Fehler erkannt haben. Die Dokumentation soll wie in folgendem Beispiel aussehen:
1 public class Debug { //K: class falsch geschrieben (ckass) 2
3 ...
4
2 /*
3 ...
4 Zeile 1: class Keyword falsch geschrieben (ckass):
5 Fehlermeldung:
6 **************
7 Debug.java:1: error: class, interface, or enum expected
8 public ckass Debug {
9 **************
10 Der Compiler erwartet eines der drei oben angegebenen Keywords, hat aber nur das falsch geschriebene ckass bekommen.
11 */
Im Code vorgegebene Kommentare beschreiben immer das korrekte Verhalten des Programms.
