Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss18 [08.03.2019 16:45] – TremTrempruefungen:bachelor:aud:loesungss18 [31.05.2019 11:41] – SpeedyGonzalez
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
-  * [[https://fsi.cs.fau.de/forum/post/159888]]+  * [[https://fsi.cs.fau.de/forum/post/159888]] Allgemeine Diskussion 
 +  * https://fsi.cs.fau.de/forum/post/159926;nocount  Aufgabe 3 (Gierige Algorithmen) Schulden begleichen
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
  
 ==== Aufgabe 1 ==== ==== Aufgabe 1 ====
-  * 1.a) +  * a) 
 <code java> <code java>
 long aDP(int n) { long aDP(int n) {
Zeile 17: Zeile 18:
  
 long aDP(int n, long[] a, long[] b) { long aDP(int n, long[] a, long[] b) {
-    if(a[n] != -1) { + if(n ==0) return 1; 
-        return a[n]; + if(n == 1) return 0; 
-    } + if(a[n] == -1){ 
-    long resultA; + a[n]=aDP(n-2, a, b) + 2*bDB(n-1, a, b); 
-    if(n == 0) {  + } 
-        resultA = 1; + return a[n];
-    } else if(n == 1) { +
-        resultA = 0; +
-    } else { +
-        resultA = aDP(n-2, a, b) + 2*bDP(n-1, a, b);          //muss hier nicht a[n]=... stehen statt resultA=... +
-    } +
-    return resultA;+
 } }
  
 long bDP(int n, long[] a, long[] b) { long bDP(int n, long[] a, long[] b) {
-    if(b[n] != -1) { + if(n ==0) return 0; 
-    return b[n]; + if(n ==1) return 1; 
-    } + if(b[n] == -1){ 
-    long resultB; + b[n]=aDP(n-1, a, b) + bDB(n-2, a, b); 
-    if(n == 0 || n == 1) { + } 
-        resultB = n; + return b[n];
-    }else { +
-        resultB = aDP(n -1, a, b) + bDP(n-2, a, b); +
-    } +
-    return resultB;+
 } }
 </code> </code>
  
-  * 1.b) +  * b) 
 <code java> <code java>
 long aIter(int n) { long aIter(int n) {
Zeile 53: Zeile 44:
     a[1] = 0;     a[1] = 0;
     b[1] = 1;     b[1] = 1;
 +    
     for (int i = 2; i <= n; i++){     for (int i = 2; i <= n; i++){
         a[i] = a[i-2] + 2*b[i-1];         a[i] = a[i-2] + 2*b[i-1];
Zeile 61: Zeile 53:
 </code> </code>
  
-  * 2.a) +==== Aufgabe 2 ==== 
 +  * a) 
  
 ^ A    ^ B     ^ C     ^ D    ^ E      ^ Prio-Queue  ^ ^ A    ^ B     ^ C     ^ D    ^ E      ^ Prio-Queue  ^
Zeile 72: Zeile 65:
 | 0      | 10     | 5     | 9    | 8     | [ ]  |  | 0      | 10     | 5     | 9    | 8     | [ ]  | 
  
-  * 2.b) A -> C -> E -> B +  * b) A -> C -> E -> B 
-  * 2.c)+ 
 +  * c)
  
 ^ uj    ^ vi     ^ wk     ^ γj,k alt    ^ γj,i,k     ^ γj,k neu  ^ ^ uj    ^ vi     ^ wk     ^ γj,k alt    ^ γj,i,k     ^ γj,k neu  ^
Zeile 87: Zeile 81:
 |C |E |D|5|4|4| |C |E |D|5|4|4|
  
- * 3.+==== Aufgabe 3 ==== 
 <code java> <code java>
 class Schuld { class Schuld {
Zeile 96: Zeile 91:
 } }
 </code> </code>
-a)+  *a)
 <code java> <code java>
 HashMap<String, Long> deltas(List<Schuld> schulden) { HashMap<String, Long> deltas(List<Schuld> schulden) {
Zeile 105: Zeile 100:
         dAlt = ds.get(s.s);         dAlt = ds.get(s.s);
         dAlt = dAlt == null ? 0L : dAlt;         dAlt = dAlt == null ? 0L : dAlt;
-        ds.put(s.s, dAlt - s.b);+        ds.put(s.s, dAlt - s.b);      
 +    
 +   
         // eingehender Betrag (zu Geldgeber):         // eingehender Betrag (zu Geldgeber):
         dAlt = ds.get(s.g);         dAlt = ds.get(s.g);
-        dAlt = dAlt == null ? 0L +        dAlt = dAlt == null ? 0L : dAlt; 
-                                    : dAlt; +        ds.put(s.g, dAlt + s.b);    
-        ds.put(s.g, dAlt + s.b);+        
 +        //Anmerkung: A ist z.B. Schuldner gegenueber B und D und Geldgeber gegenueber C (s.Zeile 2 S.6)!
     }     }
     return ds;     return ds;
Zeile 116: Zeile 114:
 </code> </code>
  
-b) +  *b) 
 <code java> <code java>
 List<Schuld> minimiere(List<Schuld> schulden) { List<Schuld> minimiere(List<Schuld> schulden) {
Zeile 131: Zeile 129:
             dS = d;             dS = d;
             }             }
-            if (dS > d) { dS = d;}+            if (dS > d) { 
 +                S = p;  //(Ergänzt) auch der String des groessten Schuldners muss m.E.n. angepasst werden. 
 +                dS = d; 
 +            }
             if (G == null) {             if (G == null) {
             G = p;             G = p;
             dG = d;             dG = d;
             }             }
-            if (dG < d) {dG = d;}+            if (dG < d) { 
 +                G = p; //(Ergänzt) auch der String des groessten Geldgebers muss m.E.n. angepasst werden. 
 +                dG = d; 
 +           }
         }         }
         // begleiche Schuld von S nach G:         // begleiche Schuld von S nach G:
         long dmin = Math.min(Math.abs(dS), Math.abs(dG));         long dmin = Math.min(Math.abs(dS), Math.abs(dG));
-        if (deltas.size() == 2){ 
         Schuld result = new Schuld (S, dMin, G);         Schuld result = new Schuld (S, dMin, G);
         ergebnis.add(result);         ergebnis.add(result);
-        } 
         // aktualisiere deltas von S bzw. G:         // aktualisiere deltas von S bzw. G:
         if (dmin == Math.abs(dS)) {         if (dmin == Math.abs(dS)) {
-            long dNeuG = deltas.get(G) ; +            deltas.put(G, dG - dmin);                   
-            dNeuG += dS; +
-            deltas.put(G, dNeuG);+
             deltas.remove(S);             deltas.remove(S);
 +             // Alternative: long dNeuG = deltas.get(G) ;
 +            // dNeuG += dS; oder  dNeuG -= dmin; 
 +            // deltas.put(G, dNeuG);
        } else {        } else {
-            long dNeuS = deltas.get(S); +            deltas.put(S, dS + dmin);                  
-            dNeuS += dG; +
-            deltas.put(S, dNeuS);+
             deltas.remove(G);             deltas.remove(G);
 +             // Alternative: long dNeuS = deltas.get(S);
 +             // dNeuS += dG; oder  dNeuS += dmin;
 +             //deltas.put(S, dNeuS);
         }         }
     }     }
Zeile 160: Zeile 164:
 } }
 </code> </code>
 +
 +
 +==== Aufgabe 4 ====
  
 <code java> <code java>
-  * 4.a)+  * a)
            remove(Add(s,v1),v2) = remove (s,v2) falls v1 == v2            remove(Add(s,v1),v2) = remove (s,v2) falls v1 == v2
                                                Add(remove(s,v2),v1) sonst                                                Add(remove(s,v2),v1) sonst
                                                                                  
-  * 4.b)+  * b)
            contains(Add(s, v1), v2) = true falls v1 == v2            contains(Add(s, v1), v2) = true falls v1 == v2
                                                   contains(s,v2) sonst                                                   contains(s,v2) sonst
-  * 4.c)+  * c)
            addAll(Add(s1; v); s2) = Add(addAll(s1,s2), v)            addAll(Add(s1; v); s2) = Add(addAll(s1,s2), v)
-  * 4.d)+  * d)
            eval(Decision(v; t; f); s) = eval (t,s) falls contains(s,v) == true            eval(Decision(v; t; f); s) = eval (t,s) falls contains(s,v) == true
                                                    eval (f,s) sonst                                                    eval (f,s) sonst
-  * 4.e)+  * e)
            collect(Decision(v; t; f)) = Add(addAll(collect(t), collect(f)),v)            collect(Decision(v; t; f)) = Add(addAll(collect(t), collect(f)),v)
                                                                                                                    
-  * 4.f)+  * f)
            isBDD(Decision(v; t; f)) = isBDD(t)            isBDD(Decision(v; t; f)) = isBDD(t)
                                                ^ isBDD(f)                                                  ^ isBDD(f)  
-                                               ^ contains(addAll(collect(t), collect(f)),v)  +                                               ^ !contains(addAll(collect(t), collect(f)),v)   
 +</code> 
 + 
 +==== Aufgabe 5 ==== 
 + 
 +  * a) 
 +<code java> 
 +Str8ts(boolean[][] blk, int[][] num) { // Konstruktor 
 +    this.blk = blk; 
 +    this.num = num; 
 +    vert = new ArrayList<>(); 
 +    horz = new ArrayList<>(); 
 +    for(int i = 0; i < 9; i++) { 
 +        vert.add(new HashSet<Integer>()); 
 +        horz.add(new HashSet<Integer>()); 
 +    } 
 +    // fill vert/horz with predefined values 
 +    for(int row = 0; row < 9; row++) { 
 +        for(int col = 0; col < 9; col++) { 
 +            vert.get(col).add(num[row][col]); 
 +            horz.get(row).add(num[row][col]); 
 +        } 
 +    } 
 +    solve(0, 0); // find solution if possible 
 +} 
 +</code> 
 + 
 +  *b) 
 +<code java> 
 +boolean isStr8tOrUnfinished(List<Integer> s) { 
 +    Collections.sort(s); 
 +    if (!s.contains(0)) { 
 +        int previous = s.get(0); 
 +         
 +        for(int i = 1; i < s.size(); i++) { 
 +            if(s.get(i) != previous + 1) { 
 +                return false; 
 +            } 
 +            previous = s.get(i); 
 +        } 
 +    } 
 +    return true; 
 +} 
 +</code> 
 + 
 +  *c) 
 +<code java> 
 +boolean checkStr8t(int row, int col) { 
 +    List<Integer> sh = new ArrayList<>(), sv = new ArrayList<>(); 
 +    int c = col, r = row; 
 +    while (c >= 0 && !blk[row][c]) { // search start of horizontal str8t 
 +        c--; 
 +    } // collect values of current horizontal str8t in sh: 
 +    while(++c < 9 && !blk[row][c]) { 
 +        sh.add(num[row][c]); 
 +    } 
 +    while (r >= 0 && !blk[r][col]) { // search start of vertical str8t 
 +        r--; 
 +    } // collect values of current vertical str8t in sv: 
 +    while(++r < 9 && !blk[r][col]) { 
 +        sv.add(num[r][col]); 
 +    } 
 +    // check that both sh and sv are str8ts or unfinished: 
 +    return isStr8tOrUnfinished(sh) && isStr8tOrUnfinished(sv); 
 +} 
 +</code> 
 + 
 +  *d) 
 +<code java> 
 +boolean solve(int row, int col) { 
 +    if (row >= 9) { 
 +        return true; // solution found 
 +    } else if (col >= 9) { 
 +        return solve(row + 1, 0); 
 +    } else if (blk[row][col] || num[row][col] > 0) { 
 +        return solve(row, col + 1); // skip field 
 +    } 
 +    for (int v = 1; v <= 9; v++) { 
 +        // if row and column do not contain v... 
 +        if(!vert.get(col).contains(v) && !horz.get(row).contains(v)) { 
 +            // ... process current field: 
 +            num[row][col] = v; 
 +            vert.get(col).add(v); 
 +            horz.get(row).add(v); 
 +             
 +            // check current str8t and recur on next field: 
 +            if(checkStr8t(row, col)) { 
 +                if(solve(row, col + 1) { 
 +                    return true; 
 +                } 
 +            } 
 +             
 +            // backtrack current field: 
 +            num[row][col] = 0; 
 +            vert.get(col).remove(v); 
 +            horz.get(row).remove(v); 
 +        } 
 +    } 
 +    return false; // puzzle has no solution 
 +}
 </code> </code>
    
-  * 6.+==== Aufgabe 6 ==== 
  
-  * a) 3,4 richtig          /--2 recht sicher auch, steht so zumindest auf den TÜ- Folien+  * a) 3,4 richtig          /--2 recht sicher auch, steht so zumindest auf den TÜ- Folien/ 2 ist falsch, QuickSort kann in-situ implementiert werden siehe Vorlesungsfolie "Überblick über die Sortierverfahren"
  
-  * b) 2, 3,4 richtig          /--4 ist denke ich falsch, siehe {{:pruefungen:bachelor:aud:02-2008-7f2.png?linkonly|}}+  * b) 2, 3 richtig          /--4 ist denke ich falsch, siehe {{:pruefungen:bachelor:aud:02-2008-7f2.png?linkonly|}}
  
   * c) 1,4 richtig   * c) 1,4 richtig
  
-  * d) 1,3 richtig          /--Code von 2 in Eclipse eingetippt, hat nicht gemeckert.+  * d) 1,2 richtig          /--Code von 2 in Eclipse eingetippt, hat nicht gemeckert. 3 sollte auch nicht richtig sein, da der rueckgabetyp sehr wohl generisch sein kann, z.b Unimodale Suche
  
-  * e) 2 richtig (vielleicht 3 auch richtig, aber nicht sicher)+  * e) 2 ,3 sind richtig, wobei bei 3 javac -ea fuer "enable assertions" steht. (Wieso das Stoff in AuD ist, ist fraglich)