Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws17 [27.03.2019 10:26] – SpeedyGonzalez | pruefungen:bachelor:aud:loesungws17 [05.08.2019 13:54] – TOKAMAK | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | **__Aufgabe1__** | + | ==== |
a) 1,3,4 //4 ist falsch, nicht die Argumentfolge, | a) 1,3,4 //4 ist falsch, nicht die Argumentfolge, | ||
b) 2,3 //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben // | b) 2,3 //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben // | ||
- | c) 2,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)// | + | c) 2,3,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)// |
d) 1,4 | d) 1,4 | ||
Zeile 11: | Zeile 10: | ||
e) 1,2 | e) 1,2 | ||
- | **__Aufgabe2__** | + | ==== |
a) | a) | ||
Zeile 17: | Zeile 16: | ||
{{: | {{: | ||
- | b) 31, | + | b) 31, |
c) 41, | c) 41, | ||
Zeile 24: | Zeile 23: | ||
- | **__Aufgabe3__** | + | ==== |
a) | a) | ||
Zeile 34: | Zeile 33: | ||
for(int i=0; | for(int i=0; | ||
b[i] = true; | b[i] = true; | ||
- | for (int x = i; x< | + | for (int x = i+1; x< |
- | b[x]=true; | + | b[x]=true; |
if(istGut(b)){ | if(istGut(b)){ | ||
- | z=z+1; | + | z++; |
} | } | ||
b[x]=false; | b[x]=false; | ||
Zeile 91: | Zeile 90: | ||
</ | </ | ||
Evtl noch besser: | Evtl noch besser: | ||
+ | ^ ist das " | ||
<code java> | <code java> | ||
public static void naechste(boolean[] b) { | public static void naechste(boolean[] b) { | ||
Zeile 102: | Zeile 102: | ||
} | } | ||
</ | </ | ||
- | c) 2^n | + | |
+ | Evtl noch besserer: | ||
<code java> | <code java> | ||
- | long mgl (int n){ | + | for (int i = 0; i < b.length; i++) { |
- | return (long) Math.pow(2, n); | + | b[i] = b[i]? false : true; |
- | } | + | if(b[i]) break; |
+ | } | ||
</ | </ | ||
- | Aufgabenstellung: | + | |
+ | c) 2^n | ||
<code java> | <code java> | ||
- | | + | long mgl (int n){ |
- | return | + | return 1 << |
- | } | + | } |
</ | </ | ||
- | beide Ansätze sind falsch, ohne Methoden aus der Java-API und ohne weitere Anweisungen, | + | |
d) | d) | ||
Zeile 132: | Zeile 137: | ||
</ | </ | ||
e) | e) | ||
+ | ueber(n - 1, k - 1) und ueber(n - 1, k) | ||
- | ueber(n-1, | + | ==== |
- | + | ||
- | **__Aufgabe4__** | + | |
a) | a) | ||
<code java> | <code java> | ||
- | | + | class Cell { |
List< | List< | ||
int v; | int v; | ||
- | | + | } |
- | | + | class Chain { |
List< | List< | ||
int sum; | int sum; | ||
- | | + | boolean satisfiable() { |
- | int s = 0; | + | int s = 0; |
- | boolean[] vs = new boolean[10]; | + | boolean[] vs = new boolean[10]; |
- | for(Cell c : zs) { | + | |
- | s = s + c.v; | + | |
- | if(c.v != 0 && vs[c.v] == true){ | + | s = s + c.v; |
- | return false;} | + | |
- | | + | |
- | } | + | return false; |
- | | + | |
- | | + | // |
- | } | + | //vs[c.v] = true; |
- | else if(sum != s){ | + | |
- | | + | |
- | } | + | |
- | | + | |
} | } | ||
+ | if (s > sum && vs[0] == true) { // i) | ||
+ | return false; | ||
+ | } else if (s != sum && vs[0] == false) { // i) | ||
+ | return false; | ||
+ | } | ||
+ | |||
+ | return true; | ||
+ | } | ||
</ | </ | ||
b) | b) | ||
<code java> | <code java> | ||
- | | + | boolean solve (LinkedList< |
- | if(cs.size()< | + | if (cs.size() <= 0) { |
- | | + | return true; |
} | } | ||
- | Cell z = cs.removeFirst(); | + | |
- | for( z.v = 1; z <= 9; z++){ // Schleifenkopf falsch, | + | |
- | | + | // try to assign |
- | | + | for (z.v = 1; z.v <= 9; z.v++) { |
- | | + | boolean ok = true; |
- | | + | for (Chain c : z.ks) { |
- | | + | if (!c.satisfiable()) { |
- | | + | ok = false; |
- | | + | } |
- | | + | } |
- | | + | // if all chains are ok => recurse |
- | | + | |
- | | + | return true; |
- | | + | } |
- | | + | } |
- | | + | |
+ | // backtrack | ||
+ | | ||
+ | cs.addFirst(z); | ||
+ | |||
+ | | ||
+ | } | ||
</ | </ | ||
- | **__Aufgabe5__** | ||
- | a) | + | ==== |
<code java> | <code java> | ||
- | | + | class UndirEdge< |
- | UndirEdge(T v, T w) { this.v = v; this.w = w; } | + | public final T v, |
- | } | + | public final T w; |
+ | | ||
+ | UndirEdge(T v, T w) { | ||
+ | | ||
+ | | ||
+ | | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | a) | ||
+ | <code java> | ||
+ | Map<T, T> initUnionFind(List< | ||
+ | | ||
| | ||
- | | + | |
- | Map<T, T> ufds = new HashMap< | + | |
- | for(UndirEdge | + | |
- | | + | |
- | | + | |
} | } | ||
return ufds; | return ufds; | ||
- | | + | } |
</ | </ | ||
+ | |||
b) | b) | ||
<code java> | <code java> | ||
- | | + | |
ufds.put(v, | ufds.put(v, | ||
} | } | ||
</ | </ | ||
- | c) bitte ergänzen | + | |
+ | c) | ||
<code java> | <code java> | ||
- | Feld 1 | + | T find(Map< |
- | | + | |
+ | // find root of n in ufds: | ||
+ | while (r != udfs.get(r) { | ||
r = udfs.get(r); | r = udfs.get(r); | ||
} | } | ||
- | Feld 2 | + | |
- | | + | // r is now pointing to the root of the partial set tree. |
- | | + | // perform path compression: |
+ | T c = n; | ||
+ | pc = ufds.get(c); | ||
+ | |||
+ | while (pc != r) { | ||
+ | // so lange wir noch nicht bei der Wurzel sind, machen wir die Knoten auf dem Pfad dorthin zu Kindern der Wurzel | ||
+ | | ||
c = pc; | c = pc; | ||
pc = udfs.get(c); | pc = udfs.get(c); | ||
} | } | ||
+ | | ||
+ | } | ||
</ | </ | ||
- | **__Aufgabe6__** | ||
+ | |||
+ | ==== | ||
a) | a) | ||
F(4, | F(4, | ||
Zeile 233: | Zeile 269: | ||
frac2cf(Frac(n, | frac2cf(Frac(n, | ||
- | frac2cf(Frac(n, | + | frac2cf(Frac(n, |
- | ich hätte hier: | ||
- | frac2cf(Frac(n, | ||
c) | c) | ||
- | cf2frac(L(n)) = Frac(n, 1) | ||
- | cf2frac(F(b, cf)) = Frac( num(Frac(b x den(Frac(cf))+den(cf2frac(cf)),den(cf2frac(cf))), | + | cf2frac(L(n)) = Frac(n, 1) |
- | + | ||
- | den(Frac(b x den(Frac(cf))+den(cf2frac(cf)), | + | |
- | ) | + | |
- | Ich hätte hier: | ||
cf2frac(F(b, | cf2frac(F(b, | ||
- | Das oben macht ja schon teilweise syntaktisch keinen Sinn | ||
d) | d) | ||
Zeile 265: | Zeile 293: | ||
same(L(x), | same(L(x), | ||
- | **__Aufgabe7__** | + | ==== |
bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht. | bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht. |