Letzte Klausur dieses Semester: Hands-On Programmieren 1
von Kai um 18:38 am Freitag, 13. März 2009 in Gadgets, Klausuren, Studium | 5 KommentareUpdate: Ungetestete Lösung Aufgabe 8 noch angehängt
Nachdem ich gestern die letzte Klausur in diesem Semester in Programmieren 1 geschrieben habe und deren Ausgang noch unklar ist, habe ich mich mal hingesetzt und versucht die ganzen Aufgaben zu rekapitulieren (danke auch an Fabian und Seba) und korrekt zu lösen:
1.) Man sollte die EBNF für beliebig lange Summen-Terme hinschreiben und danach das entsprechende Syntaxdiagramm dazu bilden (z.B. a+b, a+b+c+b+a+c, a ). Als EBNF ist wohl folgendes korrekt:
und das entsprechende Syntaxdiagramm sieht dann wohl so aus:
2.) Als nächtes musste man ein paar Code-Fragmente auf Korrektheit überprüfen. Da ich die einzelnen Abschnitte nicht mehr rekonstruieren kann, lasse ich diese hier außen vor.
3.) Die Aufgabe war anhand eines übergebenen Monats (1 – 12) die korrekte Jahreszeit wiederzugeben. Einmal mittels Switch-Anweisung und einmal mit einem Array gelöst: Ich hab folgendes hingeschrieben:
{
// Lösung mit switch
switch(monat) {
case 1: case 2: case 12:
return "Winter";
case 3: case 4: case 5:
return "Frühling";
case 6: case 7: case 8:
return "Sommer";
case 9: case 10: case 11:
return "Herbst";
default:
return "Ungültige Monatsangabe";
}
// Lösung mit String-Array
String[] jahreszeiten = {"","Winter","Winter","Frühling","Frühling","Frühling","Sommer","Sommer","Sommer","Herbst","Herbst","Herbst","Winter"}
return jahreszeiten[monat];
4.) Bei der nächsten Aufgabe sollten für eine Zahl n alle ungeraden Teiler ausgegeben werden. Einmal mit einer while-Schleife, mit einer do-while-Schleife und mit einer for-Schleife. Meine Lösung:
// while-Schleife
int i=1;
while(i < n) {
if(n%i==0 && i%2 != 0) {
System.out.println(i);
}
i++;
}
// do-while-Schleife
int j=1;
do {
if(n%j==0 && j%2 != 0) {
System.out.println(j);
}
j++;
} while(j < n);
// for-Schleife
for (int k=1; k < n;k++)
if(n%k==0 && k%2 != 0) {
System.out.println(k);
}
}
5.) Die nächste Aufgabe bestand darin, eine Reihe von Zahlen nach Größe sortiert wieder auszugeben. Hier war es von Vorteil, wenn man sich eine der üblichen Sortierverfahren vorher eingeprägt hatte. Obwohl der QuickSort-Algorithmus mit einer der effizientesten Algorithmen ist, hab ich mich dennoch für den BubbleSort entschieden, weil ich mir den leichter merken kann:
// Einlesen der Zahlen von der Kommandozeile
int[] array = new int[args.length];
int i=0;
while(i<args.length) {
array[i] = Integer.parseInt(args[i]);
i++;
}
// sortieren mit BubbleSort-Verfahren
i= 1;
while(i< array.length) {
int j = array.length -1;
while (j >= i) {
if (array[j] < array[j-1] ) {
// vertauschen der beiden Stellen
int tmp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
j--;
}
i++;
}
// sortierte Liste ausgeben
i=0;
while (i < array.length ) {
System.out.println(array[i]);
i++;
}
}
6.) Die sechste Aufgabe behandelte die binäre Suche. Das ist ein Algorithmus, der auf einem Array recht schnell ein gesuchtes Element finden kann. Der Algorithmus funktioniert folgendermaßen:
Als erstes wird das mittlere Element des Array auf geprüft. Wenn es gleich dem gesuchten Element ist, ist die Suche beendet, ist es kleiner als das gesuchte Element, muss man in der hinteren Hälfte des Arrays weitersuchen, ist es größer, wird in der vorderen Hälfte des Arrays weitergesucht.
Im nächsten Schritt wird dann wieder wie vorher weitergemacht: Also mittleres Element überprüfen, falls das gesuchte Element gleich dem mittleren Element ist, abbrechen, ansonsten jeweilige Hälfte überprüfen usw.
Ein Programmbeispiel konnte ich in der Klausur leider nicht liefern, werde mir aber dafür das Beispiel in der Wikipedia anschauen. Dort ist es neben einem Pseudocode ebenfalls in Java gelöst worden (neben Python und C).
7.) In der siebten Aufgabe sollte ein Skalarprodukt zweier Vektoren mit gleicher Länge ausgerechnet werden. Das Problem sollte einmal iterativ und einmal rekursiv gelöst werden:
public static int skalar(int[] v, int[] w) {
int result = 0;
for(int i=0;i<v.length;i++)
{
result += v[i] * w[i];
}
return result;
}
// rekursive Lösung
public static int skalar(int[] v, int[] w) {
int l = v.length;
if (l == 0)
return 0;
else {
int[] vv = new int[l - 1];
int[] ww = new int[l - 1];
for (int i = 0; i <= l - 2; i++) {
vv[i] = v[i];
ww[i] = w[i];
}
return v[l - 1] * w[l - 1] + skalar(vv, ww);
}
}
8.) Die letzte Aufgabe war es, eine Verbindungslinie zwischen zwei Punkten zu berechnen. Vorgegeben war eine fiktive Funktion setPixel(int[][] a, int[][] b). Zuerst sollte man den Mittelpunkt M zwischen dem Anfangs- und Endpunkt berechnen. Lagen dann alle berechneten Punkte in einem jeweils benachbartem Feld, war man fertig und konnte die errechneten Punkte an die Funktion setPixel übergeben, ansonsten musste man wieder jeweils den Mittelpunkt zwischen dem Anfangs- bzw. Endpunkt berechnen usw. Zum besseren Verständnis eine Grafik:
Die Lösung erspare ich mir heute und wird morgen nachgereicht. Update: Ungetestete Lösung noch beigefügt:
int[][] M = new int[(A.length/2)+(B.length/2)][(A[0].length/2)+(B[0].length/2)];
if (A.length == B.length && A[0].length == B[0].length) {
// Die Punkte A und B liegen übereinander
return M;
} else if (A.length == B.length && A[0].length != B[0].length) {
// Der x-Wert der Punkte A und B sind korrekt
return getMiddlePixel(A,M);
} else {
// Der y-Wert der Punkte A und B sind korrekt
return getMiddlePixel(M,B);
}
}