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:loesungws16 [07.02.2018 10:42] – Horscchtpruefungen:bachelor:aud:loesungws16 [22.05.2019 12:32] – SpeedyGonzalez
Zeile 1: Zeile 1:
-<note warning>~ Hier entsteht in nächster Zeit eine Beispiellösung ~ 
- 
-</note> 
- 
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
Zeile 27: Zeile 23:
 ** a) ** ** a) **
  
-TODO+Bucket 1: 27 - 75 
 + 
 +Bucket 3: 44 - 4 - 0 
 + 
 +Bucket 5: 13 - 65 - 33 
 + 
 +Bucket 7: 46 - 26 
  
 ** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. ** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind.
  
-** c) ** TODO+** c) **  
 + 
 +Bucket 0: 12 S 
 + 
 +Bucket 1: 33 D 
 + 
 +Bucket 2: 66 S 
 + 
 +Bucket 3: 28 P 
 + 
 +Bucket 4: 14 D 
 + 
 +Bucket 5: 6 S 
 + 
 +Bucket 6: 18 D 
 + 
 +Bucket 7: 5 D 
 + 
 +Bucket 8: 15 P 
 + 
 +Bucket 9: 9 D
  
-==== Aufgabe 4 RadixSort ====+==== Aufgabe 3 RadixSort ====
 ** a) ** ** a) **
 <code java> <code java>
 void radixSort (LinkedList<Integer> list) { void radixSort (LinkedList<Integer> list) {
- LinkedList<Integer>[] bs = new LinkedList[];+        //prepare sufficient buckets bs with empty lists: 
 + LinkedList<Integer>[] bs = new LinkedList[10];
  for (int i = 0; i < bs.length; i++) {  for (int i = 0; i < bs.length; i++) {
- bs[i] = new LinkedList();+ bs[i] = new LinkedList<>();
  }  }
 +        //for each segment of the Integer radix...
  for (int i = 0; i < 10; i++) {  for (int i = 0; i < 10; i++) {
 +                //...distribute values into buckets:
  for (Integer x: list) {  for (Integer x: list) {
- int b = (x/Math.pow(10,i)) % 10;+ int b = (int) (x/Math.pow(10,i)) % 10;
  bs[b].addLast(x);  bs[b].addLast(x);
  }  }
 +                //...recollect values from buckets:
  list.clear();  list.clear();
- for (int i = 0; i < bs.length; i++) { + for (int j = 0; j < bs.length; j++) { 
- list.addAll(bs[i]); + list.addAll(bs[j]); 
- bs[i].clear();+ bs[j].clear();
  }  }
  }  }
Zeile 57: Zeile 84:
 <code java> <code java>
 ... ...
-int b = ((x/Math.pow(10,i)) % 10) + 9;+int b = ((int) (x/Math.pow(10,i)) % 10) + 9;
 ... ...
 +</code>
 +
 +oder einfacher:
 +<code java>
 +...
 +bs[b + 9].addLast(x);
 </code> </code>
 ==== Aufgabe 4 Dynamische Programmierung ==== ==== Aufgabe 4 Dynamische Programmierung ====
Zeile 67: Zeile 100:
  return 1;  return 1;
  }  }
- int sum = 0;+ int sum = 0; //sum muesste eigentlich ein long sein
  for (int i = 0; i < n; i++){  for (int i = 0; i < n; i++){
  sum = sum + countNaive(i) * countNaive(n-1-i);  sum = sum + countNaive(i) * countNaive(n-1-i);
Zeile 75: Zeile 108:
  
 long countDP (int n) { long countDP (int n) {
- long[] mem = new long[]; + long[] mem = new long[n+1]; 
- mem[0] = 1; + mem[0] = mem[1] = 1;
- mem[1] = 1;+
  return countDPH(mem, n);  return countDPH(mem, n);
 +}
 +
 +private long countDPH (long[] mem, int n) {
 + if (mem[n] != 0) {
 + return mem[n];
 + } else {
 + int sum = 0;
 + for (int i = 0; i < n; i++){
 + sum = sum + countDPH(mem, i) * countDPH(mem, n-1-i);
 + }
 + mem[n] = sum;
 + return sum;
 + }
 +}
 +
 +long countIter (int n) {
 + ...
 + for (int k = 2; k < n+1; k++){
 + for (int i = 0; i < n; i++){ //Meiner Meinung nach mus hier unbedingt!!! i < k stehen, sonst rechnet man mit unbefuellten werten (buttom up beachten!)
 + mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]!
 + }
 + }
  ...  ...
 } }
 </code> </code>
-==== Aufgabe 5 Sortieren==== 
-**a)** 
  
-^L * ^A1 ^B1 ^F ^A2 ^B2| +oder schöner:
-|A1|L*|B1|F |A2|B2|  +
-|A1|B1|L*|F |A2|B2| +
-|A1|B1|F |L*|A2|B2| +
-|A1|A2|B1|F |L*|B2| +
-|A1|A2|B1|B2|F |L*|+
  
-**b)** 
- 
-==== Aufgabe 7 Graphen ==== 
 <code java> <code java>
-public class GraphWS15 {+private long countDPH (long[] mem, int n) { 
 + if (mem[n] != 0) { 
 + return mem[n]; 
 + } 
 + for (int i = 0; i < n; i++){ 
 +            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i); 
 + } 
 + return mem[n]; 
 +} 
 +</code>
  
-void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +==== Aufgabe 5 Graphen ==== 
- if (!bes.contains(k)) { +** a) ** 
- verb.add(k); +Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0
- bes.add(k); +
- for (int i = 0; i < am[k].length; i++) { +
- if (am[k][i]){ +
- sammle(am, i, verb, bes); +
- } +
- }+
  
- for (int i = 0; i < am.length; i++) { +** b) ** siehe Tafeluebungsfolien
- if (am[i][k]){ +
- sammle(am, i, verb, bes); +
- } +
- } +
- } +
- }+
  
- List<Set<Integer>> mszt(boolean[][] am) { +** c) ** M - H7, M - W, M - H4, A - E, A - H4 oder A - W
- // Ergebnisliste: +
- List<Set<Integer>> ergebnis = new LinkedList<>(); +
- // Menge besuchter Knoten: +
- Set<Integer> bk = new HashSet<>(); +
- // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: +
- for (int k = 0; k < am.length; k++) { +
- if (!bk.contains(k)){ +
- // falls k noch nicht besucht => sammle mit k verbundene Knoten +
- Set<Integer> verb = new HashSet(); +
- sammle(am,k,verb, bk); +
- ergebnis.add(verb); +
- } +
-  +
- }+
  
- return ergebnis; +** d) **  
- }+nein: bei 4 Knoten ungerader Grad 
 +nein: nicht mal ein Eulerweg
  
- void itg(boolean[][] am, Set<Integer> vs) { +==== Aufgabe 6 Rekursion ==== 
- for (int i=0;i<am.length;i++){ +<code java> 
- for (int j=0;j<am[i].length;j++){ +class MaxFlowMinCut { 
- if (am[i][j]){ +    void erreichbareVerteiler(Verteiler v, List<Verteiler> ev){ 
- if (vs.contains(i) && vs.contains(j)){ +        if(!ev.contains(v)){ 
- // ok +            ev.add(v); 
- } +            for(Rohr r : v.rohre){ 
- else { +                this.erreichbareVerteiler(r.a, ev); 
- am[i][j] = false; +                this.erreichbareVerteiler(r.e, ev); 
- } +            } 
- } +        } 
- } +    }  
- +     
 +    double schnittDurchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite){ 
 +        double sum = 0; 
 +        for(Verteiler v : quelleSeite){ 
 +            for(Rohr r : v.rohre){ 
 +                if(senkeSeite.contains(r.a) || senkeSeite.contains(r.e)){ 
 +                    sum += r.df;                     
 +                } 
 +            } 
 +        } 
 +        return sum; 
 +    }  
 +     
 +     
 +    double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){ 
 + Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); 
 + double df = schnittDurchfluss(quelleSeite, senkeSeite); 
 + for(Verteiler v : ssa){ 
 + if(!v.equals(senke)){  // v.equals ist gleich zu == (Weil es von Object erbt, aber .equals nicht überschreibt) 
 + // Hier kann man noch checken, ob zu v auch eine Kante aus quelleSeite existiert, aber nicht notwendig, da der Cut nur länger weden würde -> nur geringere Laufzeit 
 + quelleSeite.add(v); 
 + senkeSeite.remove(v); 
 + df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke)); 
 +                        //"Backtracking" 
 + senkeSeite.add(v); 
 + quelleSeite.remove(v);
  }  }
  }  }
-  + return df;  
- public static void main(String[] args){ +     } 
-                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph +     
- GraphWS15 g = new GraphWS15(); +
- boolean[][] am = {{false, true, false, true, false, false}, +
-                                              {false, false, false, true, false, false}, +
-                                              {false, false, false, false, true, false}, +
-                                              {false, true, false, false, false, false}, +
-                                              {false, false, false, false, false, false}, +
-                                              {false, false, false, false, false, false}}; +
- //Set<Integer> verb = new HashSet(); +
- List<Set<Integer>> n = g.mszt(am); +
- System.out.println(n.size());  +
- System.out.println(n.get(0).size());  +
- System.out.println(n.get(1).size());  +
- System.out.println(n.get(2).size());  +
- }+
 } }
 </code> </code>