Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:bachelor:aud:loesungss17 [12.07.2018 06:18] – LasagneAlForno | pruefungen:bachelor:aud:loesungss17 [05.03.2020 12:05] (aktuell) – amelie.ka | ||
---|---|---|---|
Zeile 7: | Zeile 7: | ||
**b)** 2 und 3 | **b)** 2 und 3 | ||
- | **c)** 4 (2 ist falsch, oder?) | + | **c)** 4 |
**d)** 2 und 4 | **d)** 2 und 4 | ||
Zeile 25: | Zeile 25: | ||
* zu 4) | * zu 4) | ||
*=> | *=> | ||
+ | * zu c) | ||
+ | *=> | ||
==== Aufgabe 2 Suchen und O-Kalkül ==== | ==== Aufgabe 2 Suchen und O-Kalkül ==== | ||
Zeile 221: | Zeile 222: | ||
<code java> | <code java> | ||
boolean isSafe(boolean g[][], int cs[], int v, int c) { | boolean isSafe(boolean g[][], int cs[], int v, int c) { | ||
- | for(int n = 0; n < g.length; n++) { | + | for (int n = 0; n < g.length; n++) { |
- | if(g[v][n] && c == cs[n]) { | + | if (g[v][n] |
+ | // Kante vorhanden und Farbe bereits vergeben | ||
return false; | return false; | ||
} | } | ||
Zeile 232: | Zeile 234: | ||
<code java> | <code java> | ||
boolean helper(boolean g[][], int cs[], int m, int v) { | boolean helper(boolean g[][], int cs[], int m, int v) { | ||
- | //base case | + | // base case |
- | if(v >= g.length) { | + | if (v >= g.length) { |
return true; | return true; | ||
} | } | ||
| | ||
- | //try different colors for vertex v | + | // try different colors for vertex v |
- | for(int c = 1; c <= m; c++) { | + | for (int c = 1; c <= m; c++) { |
- | if(isSafe(g, | + | if (isSafe(g, cs, v, c)) { |
- | //try and recurse | + | |
- | cs[v] = c; | + | cs[v] = c; // neue Farbe setzen |
- | if(helper(g, | + | |
+ | if (helper(g, cs, c, v + 1)) { // Rekursion | ||
return true; | return true; | ||
} | } | ||
- | // | + | // backtrack |
- | cs[v] = 0; | + | cs[v] = color; |
} | } | ||
} | } | ||
- | //finally give up | + | // keine Loesung gefunden -> Schritt zurueck |
return false; | return false; | ||
} | } | ||
Zeile 258: | Zeile 261: | ||
int[] color(boolean g[][], int m) { | int[] color(boolean g[][], int m) { | ||
int[] cs = new int[g.length]; | int[] cs = new int[g.length]; | ||
- | if(!helper(g, | + | |
+ | | ||
return null; | return null; | ||
} | } |