Lösungsversuch Miniklausur

system · January 21, 2014, 2:52pm

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

HAL_9000 · January 21, 2014, 2:52pm

Lösungsversuch Miniklausur
Hallo zusammen!
Ich habe mir gedacht, dass es (zwecks Klasurvorbereitung o. Ä.) ganz hilfreich wäre, eine Lösung für die Miniklausur zusammenzustellen, da der LS 2 (meines Wissens) keine Lösung herausgegeben hat. Ich poste hier mal meinen (teilweisen) Lösungsversuch (keine Garantie auf Korrektheit!). Wer ihr Korrekturen habt oder Lösungen für die anderen Aufgaben, stellt sie einfach hier rein!

1) (MC)
a) falsch: nur bei assert(x < 4711) wären die Codefragmente äquivalent
b) Option 2 und 3 sind richtig
c) O(n)
d) richtig
e) richtig

2a) (magisches Quadrat)

boolean isSolved(int[][] sq){
	int n = sq.length;
	int checkSum = ((n * n * n) + n) / 2;
	int rowSum = 0, colSum = 0, diag1Sum = 0, diag2Sum = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			rowSum += sq[i][j];
			colSum += sq[j][i];
		}
		if(rowSum != checkSum || colSum != checkSum){
			return false;
		}
		else {
			rowSum = colSum = 0;
		}
	}
	for(int i = 0; i < n; i++){
			diag1Sum += sq[i][i];
			diag2Sum += sq[n - 1 - i][i];
	}
	if(diag1Sum != checkSum || diag2Sum != checkSum){
		return false;
	}
	return true;
}

3) ADTs
a)
head.next = head;

b)
13 zwischen den Elementen 11 und 17 einfügen. Die next-Referenz von 11 zeigt dann auf 13, und next von 13 verweist auf 17.

c)
-2 zwischen dem head-Element und 7 einfügen. Die next-Referenz des Sentinel-Elements zeigt dann auf -2, und next von -2 verweist auf 7.

4) ADTs
ops
create: T → AA
get: int x AA → T
set: int x T x AA → AA
delete: int x AA → AA
size: AA → int

axs
get(x,create) = null
get(x, set(y, e, aa)) = e, wenn x = y; sonst: get(x, aa)
delete(x, create) = create
delete(x, set(y, e, aa)) = aa, wenn x = y; sonst: set(y, e, delete(x, aa))
size(create) = 0
size(x, set(x, e, aa) = size(aa), wenn get(x, aa) = null; sonst: 1 + size(aa)

system · January 21, 2014, 3:04pm

a) head.next = head; unter keinen Umständen den Konstruktor von Entry aufrufen!

edit: Bei 2a darf checkSum nicht auf 0 gesetzt werden.
edit2: dachte eig. schon, aber nein.

br0gr4mm3r · January 21, 2014, 3:32pm

Nope, hier bin ich etwas anderer Meinung, denn die beiden Zeilen koennen IMHO nie äquivalent sein, da fuer Assertions immer das entsprechende Flag beim Programmstart uebergeben werden muss, wohingegen das manuelle Schmeißen der Exception immer passieren kann.

HAL_9000 · January 21, 2014, 5:35pm

Es gab eine 1f)?

Danke, ich hab es gefixt. (hatte colSum mit CheckSum verwechselt).

N0he · January 21, 2014, 5:44pm

Der Sinn von Assertions ist ja schließlich dass man sie abschalten kann, richtig?

Volschaf · January 21, 2014, 6:27pm

Ja. Es geht ja auch nicht um den Sinn von Assertions, sondern darum, ob sich die beiden Codefragmente immer gleich verhalten. Und da man Assertions eben an- und abschalten kann, tun sie das nicht.

Alicen · January 24, 2014, 3:40pm

2b)
3d) O(n) (schlimmster Fall ist die komplette Liste durchlaufen)

Ich trag hier mal meine 2b) nach, für die Musterlösung:

if(pos > used.length){
     return isSolved(sq);
}
else {
     for(int i = 1; i <= used.length; i++){
          if(used[i-1] == false){
               sq[col][row] = i;
               used[i-1] = true;
               if(solve(sq, pos+1, used)){
                    return true;
               }
               sq[col][row] = 0;
               used[i-1] = false;
          }
     }
}
return false;

ict · January 24, 2014, 3:46pm

if(used[i-1] != true){

:-/

if(solve(sq; pos+1; used)){

Nur weil eine Methode drei Parameter hat (und deswegen gewisse Ähnlichkeit zum for-Kopf bestehen?) werden die Kommas nicht durch Strichpunkte ersetzt Habe das in der Korrektur öfter gesehen, wie kommts?

Alicen · January 24, 2014, 6:06pm

Schlecht abgetippt. In der Klausur stehen bei mir ,

Und ja klar, ich hätte jetzt auch „== false“ schreiben können…aber ich dacht mir so: Nea. ärgern wir ict ein wenig

(Habe meinen Beitrag korrigiert. Fehler sind nicht gestattet!)

ict · January 24, 2014, 6:12pm

Wenn du jetzt noch ein

(!used[i-1])

daraus machst bin ich noch glücklicher

izibi · January 24, 2014, 6:19pm

(used[i-1] == used[i-1] ^ used[i-1])

(Sorry, habe heute von GCC generierten x86-Assembler gesehen.)

Alicen · January 24, 2014, 6:29pm

ict:

Alicen:

Und ja klar, ich hätte jetzt auch „== false“ schreiben können…aber ich dacht mir so: Nea. ärgern wir ict ein wenig

Wenn du jetzt noch ein
(!used[i-1])
daraus machst bin ich noch glücklicher

Akzeptiert und abgemacht. Ich hoffe, ich konnte dir den Abend etwas versüßen

ict · January 24, 2014, 9:51pm

Interessant War das mit [m]-Os[/m] oder sowas? Denke die machen das, weil man so eine 0 mit etwas erzeugen kann, was man eh aus dem RAM laden muss und sonst keinen Speicherzugriff und keinen Immediate Operand braucht.

izibi · January 24, 2014, 10:26pm

Nimm den Post nicht so ernst, er ist nur davon inspiriert, wie GCC (und andere Compiler) Register auf x86 nullen: [m]xor eax, eax[/m]. So Code hat GCC nicht erzeugt (zumindest bei mir nicht, kann nicht ausschließen, dass man ihn doch irgendwie dazu bringen kann ;)).

ict · January 25, 2014, 12:03am

Ah dachte schon Aber ausschließen kann mans nie, deswegen hab ichs dir auch gleich geglaubt…

bulsa · January 25, 2014, 12:23am

int test(int arg) {
        return arg == 0;
}

→

$ gcc -O2 -S -o - test.c -c

→

        .file   "test.c"
        .text
        .p2align 4,,15
        .globl  test
        .type   test, @function
test:
.LFB0:
        .cfi_startproc
        xorl    %eax, %eax
        testl   %edi, %edi
        sete    %al
        ret
        .cfi_endproc
.LFE0:
        .size   test, .-test
        .ident  "GCC: (Debian 4.8.2-12) 4.8.2"
        .section        .note.GNU-stack,"",@progbits

Fazit: Test auf 0 gibts billiger mit ‘test’, Register nullen für den Rückgabewert funktioniert so in der Tat ohne immediate operand und spart so Speicher.

Necronomecon · March 19, 2014, 6:07pm

Alicen:1390578016:

3d) O(n) (schlimmster Fall ist die komplette Liste durchlaufen)

Ich trag hier mal meine 2b) nach, für die Musterlösung:

if(pos > used.length){
     return isSolved(sq);
}
else {
     for(int i = 1; i <= used.length; i++){
          if(used[i-1] == false){
               sq[col][row] = i;
               used[i-1] = true;
               if(solve(sq, pos+1, used)){
                    return true;
               }
               sq[col][row] = 0;
               used[i-1] = false;
          }
     }
}
return false;

müsste Zeile 1 im Basisfall nicht „if(pos >= used.length)“ lauten. pos beginnt bei „0“ und geht doch bis „used.length -1“?

Necronomecon · March 19, 2014, 7:33pm

Miniklausur WS13/14 Aufgabe 3e)
Hätte hier noch einen Vorschlag für die 3e)

if (toAdd != null) {
	while (cur != head) {
		if (cur.element <= toAdd.element) {
			drag = cur;
			cur = cur.next;
		} else {
			drag.next = toAdd;
			toAdd.next = cur;
			return;
		}
	}
}

system · March 19, 2014, 9:38pm

Necronomecon:

Alicen:1390578016:
3d) O(n) (schlimmster Fall ist die komplette Liste durchlaufen)

Ich trag hier mal meine 2b) nach, für die Musterlösung:
if(pos > used.length){
     return isSolved(sq);
}
else {
     for(int i = 1; i <= used.length; i++){
          if(used[i-1] == false){
               sq[col][row] = i;
               used[i-1] = true;
               if(solve(sq, pos+1, used)){
                    return true;
               }
               sq[col][row] = 0;
               used[i-1] = false;
          }
     }
}
return false;
müsste Zeile 1 im Basisfall nicht „if(pos >= used.length)“ lauten. pos beginnt bei „0“ und geht doch bis „used.length -1“?

Edit: Man kann beides machen und auch „if(pos == used.length)“ funktioniert. Wenn man einen Schritt später als nötig abbricht, sind alle Elemente besucht und man begeht den Inhalt der for-Schleife quasi gar nicht.

Ich habe meinen Fehler vom ehemaligen Post gefunden und gefixt.