Not logged in. · Lost password · Register

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen RSS
Lösungsversuch Miniklausur
Page:  1  2  next ›
HAL 9000
Avatar
Member since Aug 2013
85 posts
 2014-01-21, 15:52   #1  
Subject: 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)
This post was edited 2 times, last on 2014-01-21, 18:32 by HAL 9000.
Chayyam (Former member)
2014-01-21, 16:04   #2  
3. 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.
This post was edited 2 times, last on 2014-01-21, 19:25 by Unknown user.
br0gr4mm3r
Avatar
Member since Mar 2012
216 posts
 2014-01-21, 16:32   #3  
In reply to post #1
Quote by HAL 9000:
1) (MC)
a) falsch: nur bei assert(x < 4711) wären die Codefragmente äquivalent

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.
carpe diem, baby!
HAL 9000
Avatar
Member since Aug 2013
85 posts
 2014-01-21, 18:35   #4  
In reply to post #2
Quote by Chayyam:
1. f) richtig
Es gab eine 1f)?

edit: Bei 2a darf checkSum nicht auf 0 gesetzt werden.

Danke, ich hab es gefixt. (hatte colSum mit CheckSum verwechselt).
N0he
Member since Nov 2013
33 posts
 2014-01-21, 18:44   #5  
In reply to post #3
Quote by br0gr4mm3r:
Quote by HAL 9000:
1) (MC)
a) falsch: nur bei assert(x < 4711) wären die Codefragmente äquivalent

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.

Der Sinn von Assertions ist ja schließlich dass man sie abschalten kann, richtig?
Volschaf
Member since May 2013
220 posts
 2014-01-21, 19:27   #6  
+1 br0gr4mm3r
Quote by N0he:
Quote by br0gr4mm3r:
Quote by HAL 9000:
1) (MC)
a) falsch: nur bei assert(x < 4711) wären die Codefragmente äquivalent

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.

Der Sinn von Assertions ist ja schließlich dass man sie abschalten kann, richtig?
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
Member since Oct 2013
84 posts
 2014-01-24, 16:40   #7  
Subject: 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;
This post was edited on 2014-01-24, 19:07 by Alicen.
ict
Member since Nov 2006
347 posts
 2014-01-24, 16:46   #8  
  1. if(used[i-1] != true){
:-/


  1. 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?
/* This is O(scary), but seems quick enough in practice. */
This post was edited on 2014-01-24, 16:47 by ict.
Alicen
Member since Oct 2013
84 posts
 2014-01-24, 19:06   #9  
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?

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 :P

(Habe meinen Beitrag korrigiert. Fehler sind nicht gestattet!)
This post was edited on 2014-01-24, 19:07 by Alicen.
ict
Member since Nov 2006
347 posts
 2014-01-24, 19:12   #10  
Quote by Alicen:
Und ja klar, ich hätte jetzt auch "== false" schreiben können...aber ich dacht mir so: Nea. ärgern wir ict ein wenig :P

Wenn du jetzt noch ein
  1. (!used[i-1])
daraus machst bin ich noch glücklicher :)
/* This is O(scary), but seems quick enough in practice. */
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
555 posts
 2014-01-24, 19:19   #11  
Quote by ict:
Wenn du jetzt noch ein
  1. (!used[i-1])
daraus machst bin ich noch glücklicher :)

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

(Sorry, habe heute von GCC generierten x86-Assembler gesehen.)
Alicen
Member since Oct 2013
84 posts
 2014-01-24, 19:29   #12  
In reply to post #10
Quote by ict:
Quote by Alicen:
Und ja klar, ich hätte jetzt auch "== false" schreiben können...aber ich dacht mir so: Nea. ärgern wir ict ein wenig :P

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

Akzeptiert und abgemacht. Ich hoffe, ich konnte dir den Abend etwas versüßen ;)
ict
Member since Nov 2006
347 posts
 2014-01-24, 22:51   #13  
In reply to post #11
Quote by izibi:
  1. (used[i-1] == used[i-1] ^ used[i-1])

Interessant :D War das mit -Os 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.
/* This is O(scary), but seems quick enough in practice. */
izibi
Blockchain-Exorzist
(Administrator)
Member since Oct 2012
555 posts
 2014-01-24, 23:26   #14  
Nimm den Post nicht so ernst, er ist nur davon inspiriert, wie GCC (und andere Compiler) Register auf x86 nullen: xor eax, eax. So Code hat GCC nicht erzeugt (zumindest bei mir nicht, kann nicht ausschließen, dass man ihn doch irgendwie dazu bringen kann ;)).
ict
Member since Nov 2006
347 posts
 2014-01-25, 01:03   #15  
Ah dachte schon :D Aber ausschließen kann mans nie, deswegen hab ichs dir auch gleich geglaubt..
/* This is O(scary), but seems quick enough in practice. */
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next ›

Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen