Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Lösungsversuch   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

Both sides previous revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
pruefungen:bachelor:aud:loesungss17 [22.10.2017 15:10]
jonpost Aufgabe 4, 5 hinzugefügt
pruefungen:bachelor:aud:loesungss17 [05.03.2020 13:05] (aktuell)
amelie.ka
Zeile 7: Zeile 7:
 **b)** 2 und 3 **b)** 2 und 3
  
-**c)** ​2 und 4+**c)** 4
  
 **d)** 2 und 4 **d)** 2 und 4
Zeile 25: Zeile 25:
   * zu 4)   * zu 4)
     *=> ​ Eine endrekursive Methode kann unmittelbar entrekursiviert werden.     *=> ​ Eine endrekursive Methode kann unmittelbar entrekursiviert werden.
 +   * zu c) 
 +    *=> ​ Laufzeit ist O(log(n))
  
 ==== Aufgabe 2 Suchen und O-Kalkül ==== ==== Aufgabe 2 Suchen und O-Kalkül ====
Zeile 216: Zeile 217:
  
 as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns),​ as, af)) as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns),​ as, af))
 +
 +====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] == true && c == cs[n]) {
 +             // Kante vorhanden und Farbe bereits vergeben
 +            return false;
 +        }
 +    }
 +    return true;
 +}
 +</​code>​
 +**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, cs, v, c)) {
 +            int color = cs[v]; ​ // aktuelle Farbe sichern
 +            cs[v] = c;  // neue Farbe setzen ​
 +            ​
 +            if (helper(g, cs, c, v + 1)) { // Rekursion ​  ​(Fehler?:​ sollte m statt c sein)
 +                return true;
 +            }
 +            // backtrack
 +            cs[v] = color;
 +        }
 +    }
 +    // keine Loesung gefunden -> Schritt zurueck
 +    return false;
 +}
 +</​code>​
 +
 +**c)**
 +<code java>
 +int[] color(boolean g[][], int m) {
 +    int[] cs = new int[g.length];​
 +    ​
 +    if (!helper(g, cs, m, 0)) {
 +        return null;
 +    }
 +    return cs;
 +}
 +</​code>​