185.A02 Grundlagen der Programmkonstruktion 2015S 1 Aufgabenblatt GPK1 zu Grundlagen der Programmkonstruktion für die Übung am 7. Mai 2015 Dieses Aufgabenblatt gilt nur für Teilnehmer(innen) an „Grundlagen der Programmkonstruktion“, nicht für Teilnehmer(innen) an „Programmkonstruktion“ oder „Programmierpraxis“. Bitte lösen Sie alle Aufgaben auf diesem Aufgabenblatt und bringen Sie die Lösungen zur Übung am 7. Mai 2015 in den HS14 mit. Sie sollen in der Lage sein, die Lösungen zu präsentieren und Fragen dazu zu beantworten. Bei der Lösung ist ein Computer hilfreich. Für die Präsentation steht aber nur die Tafel zur Verfügung. Zu Beginn der Übung müssen Sie bekanntgeben, welche Aufgaben Sie gelöst haben – gelöste Aufgaben ankreuzen. Diese Lösungen müssen Sie präsentieren können. Jedes Kreuz steht für fünf Punkte. Eine Voraussetzung für eine positive Beurteilung ist, dass Sie (über alle vier Übungen hinweg) mindestens 50 Punkte erreichen, je mehr, desto besser. Werden Fragen zu angekreuzten Aufgaben nicht oder nur mangelhaft beantwortet oder auf Aufforderung keine korrekten Lösungen präsentiert, wird die Anzahl der Punkte dieser Übung anteilsmäßig reduziert, in Extremfällen bis auf 0%. 1 Termination rekursiver Methoden Folgende Java-Methoden sind gegeben: int f(int x) { return x*x == 64 ? 0 : f(x-3) + 1; } int g(int x) { return x <= -8 ? 0 : g(x/2 - 2) + 1; } int h(int x) { return x == 64 ? 0 : h(x*x + 15) + 1; } int p(int x) { return x == 0 ? 0 : x%2 == 1 ? p(x/2) + 2 : p(x-1) + 1; } int q(int x) { return x%3 == 0 ? 0 : q(x*7) + 1; } Beantworten Sie dazu diese Fragen: • Unter welchen allgemeinen Voraussetzungen terminieren rekursive Methoden? • Für jeweils welche Argumente terminieren diese Methoden, ohne dass es bei der Berechnung zu einem Überlauf kommt? • Aus welchen Gründen terminieren diese Methoden mit anderen Argumenten nicht? • Welchen Ergebnisse werden von den terminierenden Methoden zurückgegeben? 185.A02 Grundlagen der Programmkonstruktion 2 2015S 2 Türme von Hanoi Zur Lösung der „Türme von Hanoi“ gibt es einen einfachen rekursiven Algorithmus: void rec(int i, char a, char b, char c) { if (i > 0) { rec(i-1, a, c, b); System.out.println("von " + a + " nach " + c); rec(i-1, b, a, c); } } Beantworten Sie dazu folgende Fragen: • Wie viele Zeilen werden bei Aufruf von rec mit 5, 10, 15 und 20 als erstem Parameter ausgegeben. Wie oft wird dabei rec mit 0 als erstem Parameter ausgeführt? • Durch welche allgemeine Formeln lassen sich diese Anzahlen einfach aus dem ersten Parameter von rec berechnen? 3 Primzahlberechnung Vervollständigen Sie die Methode primes, indem Sie anstelle von ___ geeigneten JavaCode einfügen. Verwenden Sie dabei keine vorgefertigten Methoden aus Bibliotheken. primes soll ein Array mit den kleinsten Primzahlen befüllen. Es wird davon ausgegangen, dass die Array-Einträge mit Index 0 bis n-1 bereits mit richtigen Werten befüllt sind. void primes(int[] array, int n) { if (___) { // array exists, but not yet completely filled if (___) { // no array entry correctly set array[0] = 2; primes(___, ___); } else { // array entries at indexes 0 to n-1 correctly set int check = array[n - 1]; boolean isPrime; do { check++; isPrime = true; for (___) { // all necessary divisions will be tried, // loop terminates as soon as possible isPrime = isPrime && (check % array[i] != 0); } } while (! isPrime); array[n] = check; primes(___, ___); } } } 185.A02 Grundlagen der Programmkonstruktion 2015S 3 Beantworten Sie zusätzlich folgende Fragen: • Wie geht primes vor um die Primzahlen zu ermitteln? • Welche Rolle spielt der Parameter n? Kann man das Programm auf einfache Weise so abändern, dass n nicht nötig ist? • Aus welchen einzelnen Bedingungen setzt sich die Abbruchbedingung der for-Schleife in primes zusammen, und wozu benötigt man jede der Bedingungen? 4 Variablen, Literale und Operatoren Beantworten Sie folgende Fragen im Detail, nicht nur oberflächlich: • Was versteht man unter der Lebensdauer und dem Scope einer Variablen? Wodurch werden deren Grenzen jeweils festgelegt? • Was versteht man unter einem L-Wert bzw. R-Wert? Welche Operatoren in Java benötigen L-Werte und R-Werte als Operanden? • Wie schreibt man in Java Oktalzahlen und Hexadezimalzahlen als Literale an? Woran erkennt man den Typ int, long, float, double oder char eines Literals? • Gibt es auch Literale für Referenztypen? Wenn ja, nennen Sie Beispiele. • Wie, wo und womit werden Variablen (explizit bzw. implizit) initialisiert? 5 String und Array Geben Sie tiefgehende Antworten auf folgende Fragen in Bezug auf Java: • Warum ist ein Vergleich von Strings mittels == nicht sinnvoll? In welchen Fällen könnte ein solcher Vergleich falsche Ergebnisse liefern? Wie kann und soll man Strings stattdessen vergleichen? • Wie vergleicht man im Gegensatz zu Strings Werte elementarer Typen? Ähnelt ein Vergleich mit null eher einem Vergleich elementarer Typen oder einem Vergleich von Strings? Warum ist das so? Wozu sind Vergleiche mit null nötig? • Stellen Sie ein char-Array einem String gegenüber. In welchen Fällen ist welcher dieser beiden Typen zu bevorzugen? • Welche Möglichkeiten gibt es um ein (mehrdimensionales) Array zu erzeugen und mit Inhalten zu befüllen? • Auf vielen Arrays sind Schleifen der Form for (... : ...) ... ebenso wie solche der Form for (...; ...; ...) ... anwendbar. In welchen Fällen ist die Verwendung welcher Form von for-Schleifen möglich, vorteilhaft bzw. nötig?