Ausgabe Flashcards
Was gibt mystical(3) aus?
[] es passiert nichts
[] es werden unendlich viele * Ausgegeben
[] es geht in eine Endlosschleife und nichts wird ausgegben
[] es wird eine Leerzeile ausgegeben und es gibt einen Stackoverflow
[] es wird genau ein * ausgegeben
[] Die Lösung ist oben nicht angegeben
(eventuell noch weitere Möglichkeiten)
public class Stern{
public static void stern(int N){
for(int i = 0; i < N, i++)
System.out.print(“*”);
System.out.println();
}
public static void mystic(int N){
if(N == 0) return;
stern(N);
mystic(N-1);
stern(N);
}
}
**
***
Was gibt mystical(4) aus?
[] es passiert nichts
[] es werden unendlich viele * Ausgegeben
[] es geht in eine Endlosschleife und nichts wird ausgegben
[] es wird eine Leerzeile ausgegeben und es gibt einen Stackoverflow
[] es wird genau ein * ausgegeben
[] Die Lösung ist oben nicht angegeben
(eventuell noch weitere Möglichkeiten)
public class Stern{
public static void stern(int N){
for(int i = 0; i < N, i++)
System.out.print(“*”);
System.out.println();
}
public static void mystic(int N){
if(N == 0) return;
stern(N);
mystic(N-1);
stern(N);
}
}
**
***
**
Was gibt mystical(-1) aus?
[] es passiert nichts
[] es werden unendlich viele * Ausgegeben
[] es geht in eine Endlosschleife und nichts wird ausgegben
[] es wird eine Leerzeile ausgegeben und es gibt einen Stackoverflow
[] es wird genau ein * ausgegeben
[] Die Lösung ist oben nicht angegeben
(eventuell noch weitere Möglichkeiten)
public class Stern{
public static void stern(int N){
for(int i = 0; i < N, i++)
System.out.print(“*”);
System.out.println();
}
public static void mystic(int N){
if(N == 0) return;
stern(N);
mystic(N-1);
stern(N);
}
}
Wenn mystic(-1) aufgerufen wird, wird keine der if-Bedingungen wahr sein und die mystic-Funktion wird in eine Endlosschleife geraten und nichts wird ausgegeben. Da die Rekursion nicht aufhört, wird es zu einem Stack Overflow kommen und die Ausführung des Programms wird abbrechen.
Was gibt folgendes Program aus?
public class a5 {
public static void f(int x, int[] y, String z) {
x = 1111;
y[0] = 2222;
y = new int[5];
y[0] = 4444;
z = “5555”;
}
public static void main(String[] args) {
int x = 1;
int[] y = { 2, 3, 4 };
String z = "5";
f(x, y, z);
z = z.replaceAll("5", "6");
System.out.println(x);
System.out.println(y[0]);
System.out.println(z);
z.replaceAll("6", "12");
System.out.println(z);
}
}
1
2222
6
6
In der main-Methode werden die Variablen x, y und z mit den Werten 1, {2, 3, 4} und “5” initialisiert. Dann wird die Methode f aufgerufen, wobei die Variablen x, y und z als Parameter übergeben werden. In der Methode f werden die Parameter x und y[0] verändert. Die Variable x wird auf den Wert 1111 gesetzt, aber da es sich um einen primitiven Datentyp handelt, wird diese Änderung nur innerhalb der Methode sichtbar sein und wird keinen Einfluss auf die Variable x in der main-Methode haben. Die Variable y[0] wird auf den Wert 2222 gesetzt, was auch außerhalb der Methode sichtbar sein wird. In der Methode wird dann ein neues Array mit der Größe 5 erstellt und die Variable y auf dieses neue Array gesetzt. Der Wert y[0] des neuen Arrays wird auf 4444 gesetzt, aber dies wird keinen Einfluss auf das Array y in der main-Methode haben, da das Array y in der main-Methode unverändert bleibt. Die Variable z wird auf den Wert “5555” gesetzt, aber auch hier wird diese Änderung keinen Einfluss auf die Variable z in der main-Methode haben, da Strings in Java unveränderlich sind.
Nachdem die Methode f beendet wurde, wird die Variable z in der main-Methode mit der replaceAll-Methode auf “6” umgestellt. Das Ergebnis ist der String “6”. Dieser String wird dann zweimal ausgegeben.
Die Methode replaceAll gibt jedoch einen neuen String zurück und verändert nicht den ursprünglichen String. Daher wird der letzte System.out.println(z)-Aufruf immer noch “6” ausgeben und nicht “12”.
Aufgabe Quizz: Was gibt folgendes Program aus?
class B {
public String s;
public B() {
s = "b";
}
public String foo() {
return "B" + s;
}
public String bar() {
return foo() + s;
}
}
class C extends B {
public String s;
public C() {
s = "c";
}
public String foo() {
return "C" + s;
}
}
public class Quizz {
public static void main(String[] args) {
C c = new C();
B b = c;
System.out.println(b.foo() + b.s);
System.out.println(c.foo() + c.s);
System.out.println(b.bar() + b.s);
System.out.println(c.bar() + c.s);
}
}
Das Programm gibt folgendes aus:
Copy code
CB
Cc
CBb
Ccb
Zuerst wird ein Objekt der Klasse C mit der Variable c erstellt. Dann wird die Variable b als B-Objekt initialisiert, aber tatsächlich referenziert sie auf das C-Objekt, da C von B erbt.
In der ersten Ausgabe wird die foo()-Methode des B-Objekts aufgerufen und gibt “B” + “c” zurück. Die Variable s in B ist “b”, daher lautet die Ausgabe “CB”.
In der zweiten Ausgabe wird die foo()-Methode des C-Objekts aufgerufen und gibt “C” + “c” zurück. Die Variable s in C ist auch “c”, daher lautet die Ausgabe “Cc”.
In der dritten Ausgabe wird die bar()-Methode des B-Objekts aufgerufen. Die foo()-Methode des B-Objekts gibt “B” + “c” zurück, und die Variable s in B ist “b”. Daher lautet die Ausgabe “CBb”.
In der vierten Ausgabe wird die bar()-Methode des C-Objekts aufgerufen. Die foo()-Methode des C-Objekts gibt “C” + “c” zurück, und die Variable s in C ist “c”. Daher lautet die Ausgabe “Ccb”.
Aufgabe Binomialkoeffizient:
Der Binomialkoeffizient C(int N, int k) gibt an wie viele verschiedene Arten man aus einer Menge von N Elementen eine Teilmenge mit k Elementen auswählen kann. Er kann wie folgt rekursiv berechnet werden:
public static int C(int N, int k) {
if (k==0) return 1;
if (N==0) return 0;
return C(N-1, k) + C(N-1, k-1);
}
1) Welches Ergebnis liefert der Aufruf C(4,2)
2) Für die Berechnung von C(36,18) braucht ein herkömmlicher Pc über 15 Minuten. Des Weiteren liefert dieser Aufruf ein falsches Ergebnis, nämlich 485.200.700 anstatt 9.075.135.300. Erklären sie diese beiden Phänomene.
Der Aufruf C(4,2) liefert das Ergebnis 6.
Das Phänomen, dass die Berechnung von C(36,18) sehr lange dauert, liegt daran, dass der rekursive Algorithmus sehr ineffizient ist. Bei jedem Aufruf der Funktion werden zwei weitere Aufrufe gemacht, wodurch sich die Anzahl der Funktionsaufrufe exponentiell mit der Größe der Eingabeparameter erhöht. Das bedeutet, dass für größere Werte von N und k sehr viele Funktionsaufrufe nötig sind, um das Ergebnis zu berechnen, was zu einer sehr langen Berechnungszeit führt.
Das falsche Ergebnis von 485.200.700 kommt daher, dass bei der Berechnung von C(36,18) sehr große Zahlen auftreten, die nicht mehr in den Datentyp int passen. Dadurch kommt es zu einem sogenannten Überlauf (engl. overflow), bei dem der Wert des Datentyps überschritten wird und das Ergebnis dadurch falsch ist. Um das richtige Ergebnis zu erhalten, müsste man eine andere Methode zur Berechnung des Binomialkoeffizienten verwenden, z.B. den Pascal’schen Dreieck oder die Formel von Legendre.
Programmausführung
Der Binomialkoeffizient C(int N, int k) gibt an wie viele verschiedene Arten man aus einer Menge von N Elementen eine Teilmenge mit k Elementen auswählen kann. Er kann wie folgt rekursiv berechnet werden:
public static int C(int N, int k) {
if (k==0) return 1;
if (N==0) return 0;
return C(N-1, k) + C(N-1, k-1);
}
1) Welches Ergebnis liefert der Aufruf C(6,2)
2) Für die Berechnung von C(36,18) braucht ein herkömmlicher Pc über 15 Minuten. Des Weiteren liefert dieser Aufruf ein falsches Ergebnis, nämlich 485.200.700 anstatt 9.075.135.300. Erklären sie diese beiden Phänomene.
Der Aufruf C(6,2) liefert das Ergebnis 15.
Der Grund für die lange Berechnungszeit und das falsche Ergebnis bei C(36,18) liegt darin, dass bei großen Werten von N und k die rekursive Berechnungsmethode sehr ineffizient wird und zu einer großen Anzahl von wiederholten Berechnungen führt. Dies wird als Overlapping Subproblems bezeichnet. Die Berechnung von C(36,18) erfordert die Berechnung von C(35,17) und C(35,18), die beide wiederum die Berechnung von C(34,16), C(34,17), C(34,17) und C(34,18) erfordern, und so weiter. Dies führt zu einer exponentiellen Anzahl von wiederholten Berechnungen und einer sehr langen Berechnungszeit.
Um dieses Problem zu lösen, können verschiedene Ansätze verwendet werden, wie z.B. die Verwendung einer Memoization-Technik, bei der die Ergebnisse von Zwischenberechnungen gespeichert werden, um unnötige Wiederholungen zu vermeiden, oder die Verwendung einer iterativen Berechnungsmethode, die das Problem in linearer Zeit löst.
Aufgabe 5: Was gibt folgendes Program aus?
public class a5 {
public static void f(int x, int[] y, String z) {
x = 1111;
y[0] = 2222;
y = new int[5];
y[0] = 4444;
z = “5555”;
}
public static void main(String[] args) {
int x = 1;
int[] y = { 2, 3, 4 };
String z = "5";
f(x, y, z);
z = z.replaceAll("5", "6");
System.out.println(x);
System.out.println(y[0]);
System.out.println(z);
z.replaceAll("6", "12");
System.out.println(z);
}
}
1
2222
6
6
In der Methode f werden die Werte der Parameter x, y und z verändert. Die Variable x erhält den Wert 1111, das erste Element des Arrays y erhält den Wert 2222 und die Referenz auf das Array y wird auf ein neues Array der Länge 5 gesetzt, dessen erstes Element den Wert 4444 erhält. Die Variable z wird auf den String “5555” gesetzt.
Im main-Block wird die Methode f mit den Variablen x, y und z als Argumenten aufgerufen. Die Variable z wird anschließend mit replaceAll so verändert, dass der String “5” durch “6” ersetzt wird. Die Methode replaceAll gibt jedoch einen neuen String zurück und verändert den ursprünglichen String nicht. Deshalb hat die Variable z immer noch den Wert “6” und wird zweimal hintereinander mit System.out.println ausgegeben.
Die Methode replaceAll wird danach erneut aufgerufen, um den String “6” durch “12” zu ersetzen. Da der ursprüngliche String “6” jedoch nicht verändert wurde, gibt die Ausgabe auch hier den Wert “6” aus.
Programmausführung
Der Binomialkoeffizient C(int N, int k) gibt an wie viele verschiedene Arten man aus einer Menge von N Elementen eine Teilmenge mit k Elementen auswählen kann. Er kann wie folgt rekursiv berechnet werden:
public static int C(int N, int k) {
if (k==0) return 1;
if (N==0) return 0;
return C(N-1, k) + C(N-1, k-1);
}
1) Welches Ergebnis liefert der Aufruf C(6,2)
2) Für die Berechnung von C(36,18) braucht ein herkömmlicher Pc über 15 Minuten. Des Weiteren liefert dieser Aufruf ein falsches Ergebnis, nämlich 485.200.700 anstatt 9.075.135.300. Erklären sie diese beiden Phänomene.
Der Aufruf C(6,2) liefert das Ergebnis 15.
Der Grund für die lange Berechnungszeit und das falsche Ergebnis bei C(36,18) liegt darin, dass bei großen Werten von N und k die rekursive Berechnungsmethode sehr ineffizient wird und zu einer großen Anzahl von wiederholten Berechnungen führt. Dies wird als Overlapping Subproblems bezeichnet. Die Berechnung von C(36,18) erfordert die Berechnung von C(35,17) und C(35,18), die beide wiederum die Berechnung von C(34,16), C(34,17), C(34,17) und C(34,18) erfordern, und so weiter. Dies führt zu einer exponentiellen Anzahl von wiederholten Berechnungen und einer sehr langen Berechnungszeit.
Um dieses Problem zu lösen, können verschiedene Ansätze verwendet werden, wie z.B. die Verwendung einer Memoization-Technik, bei der die Ergebnisse von Zwischenberechnungen gespeichert werden, um unnötige Wiederholungen zu vermeiden, oder die Verwendung einer iterativen Berechnungsmethode, die das Problem in linearer Zeit löst.
Aufrufkonvention
Was ist die Ausgabe bei dem folgenden Programm?
public class Param {
private char c;
public Param(char c) {this.c = c;}
public void print() {
char a = 'a';
char b = 'b';
char c[] = {'c'};
char e[] = {'e'};
Param g = new Param('g');
Param i = new Param('i');
foo(a);
bar(b);
foo(c);
bar(e);
foo(g);
bar(i);
System.out.println("" + a + b + c[0] + e[0] + g + i);
}
public void foo(char p) {p = 'k';}
public void foo(char p[]) {p = new char[] {'q'};}
public void foo(Param p) {p.c = 'u'; }
public void bar(char p) {p = new Param('o').c;}
public void bar(char p[]) { p[0] = new Param('r').c;}
public void bar(Param p) {p = new Param('v');}
public String toString() { return "" + c;}
public static void main(String s[]) {
new Param('z').print();
}
}
Note: Das Programm lässt sich übersetzen und ausführen
Die Ausgabe des Programms ist “abcurv”.
Die Methode print() ruft nacheinander sechs verschiedene Methoden auf, wobei jedes Mal ein Argument von einem anderen Typ an die Methode übergeben wird. Die Methoden foo() und bar() ändern das Argument, das sie erhalten, auf unterschiedliche Weise, abhängig von dessen Typ. Die Methode print() gibt dann eine Zeichenkette aus, die aus den Werten von sechs verschiedenen Variablen besteht, die in der Methode deklariert wurden oder von anderen Objekten stammen, die in der Methode erzeugt wurden.
Hier ist der Ablauf der Methode print():
foo(a) wird aufgerufen, wobei a = ‘a’. Da a ein char-Typ ist, wird die Methode foo(char p) aufgerufen, die das Argument p ignoriert und stattdessen den lokalen Variablen p auf ‘k’ setzt. Deshalb bleibt der Wert von a unverändert bei ‘a’.
bar(b) wird aufgerufen, wobei b = ‘b’. Da b ein char-Typ ist, wird die Methode bar(char p) aufgerufen, die das Argument p ignoriert und stattdessen eine neue Instanz von Param erzeugt, deren Attribut c auf ‘o’ gesetzt wird. Der lokale Variablen p wird jedoch kein Wert zugewiesen. Deshalb bleibt der Wert von b unverändert bei ‘b’.
foo(c) wird aufgerufen, wobei c = {‘c’}. Da c ein char[]-Typ ist, wird die Methode foo(char[] p) aufgerufen, die das Argument p ignoriert und stattdessen p auf ein neues char[]-Array {‘q’} setzt. Dies hat jedoch keine Auswirkungen auf das ursprüngliche Array c, das weiterhin {‘c’} bleibt.
bar(e) wird aufgerufen, wobei e = {‘e’}. Da e ein char[]-Typ ist, wird die Methode bar(char[] p) aufgerufen, die das Argument p ignoriert und stattdessen das erste Element des Arrays auf ‘r’ setzt, das durch eine neue Instanz von Param repräsentiert wird. Dies ändert das erste Element des ursprünglichen Arrays e auf ‘r’.
foo(g) wird aufgerufen, wobei g eine neue Instanz von Param ist, die auf ‘g’ initialisiert wurde. Da g ein Param-Typ ist, wird die Methode foo(Param p) aufgerufen, die das Attribut c des Objekts p auf ‘u’ setzt. Dies ändert das Attribut c des ursprünglichen Objekts g auf ‘u’.
bar(i) wird aufgerufen, wobei i eine neue Instanz von Param ist, die auf ‘i’ initialisiert wurde. Da i ein Param-Typ ist, wird die Methode bar(Param p) aufgerufen, die das Argument p ignoriert und stattdessen eine neue Instanz von Param erzeugt, die auf ‘v’ initialisiert wurde. Dies hat jedoch keine Auswirkungen auf das ursprüngliche Objekt i, das weiterhin auf ‘i’ initialisiert ist.
Schließlich gibt die Methode print() eine Zeichenkette aus, die aus sechs verschiedenen Werten besteht, die durch das + Zeichen verkettet wurden: a, b, das erste Element des Arrays
