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 ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungss17 [22.10.2017 13:10] – Aufgabe 4, 5 hinzugefügt jonpost | pruefungen:bachelor:aud:loesungss17 [12.07.2018 06:18] – LasagneAlForno | ||
---|---|---|---|
Zeile 7: | Zeile 7: | ||
**b)** 2 und 3 | **b)** 2 und 3 | ||
- | **c)** | + | **c)** 4 (2 ist falsch, oder?) |
**d)** 2 und 4 | **d)** 2 und 4 | ||
Zeile 216: | Zeile 216: | ||
as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), | as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), | ||
+ | |||
+ | ====Aufgabe 6 Graphen==== | ||
+ | **a)** | ||
+ | <code java> | ||
+ | boolean isSafe(boolean g[][], int cs[], int v, int c) { | ||
+ | for(int n = 0; n < g.length; n++) { | ||
+ | if(g[v][n] && c == cs[n]) { | ||
+ | return false; | ||
+ | } | ||
+ | } | ||
+ | return true; | ||
+ | } | ||
+ | </ | ||
+ | **b)** | ||
+ | <code java> | ||
+ | boolean helper(boolean g[][], int cs[], int m, int v) { | ||
+ | //base case | ||
+ | if(v >= g.length) { | ||
+ | return true; | ||
+ | } | ||
+ | | ||
+ | //try different colors for vertex v | ||
+ | for(int c = 1; c <= m; c++) { | ||
+ | if(isSafe(g, | ||
+ | //try and recurse | ||
+ | cs[v] = c; | ||
+ | if(helper(g, | ||
+ | return true; | ||
+ | } | ||
+ | //backtrack | ||
+ | cs[v] = 0; | ||
+ | } | ||
+ | } | ||
+ | //finally give up | ||
+ | return false; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | **c)** | ||
+ | <code java> | ||
+ | int[] color(boolean g[][], int m) { | ||
+ | int[] cs = new int[g.length]; | ||
+ | if(!helper(g, | ||
+ | return null; | ||
+ | } | ||
+ | return cs; | ||
+ | } | ||
+ | </ |