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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungss17 [22.10.2017 18:26] – jonpostpruefungen:bachelor:aud:loesungss17 [24.07.2019 14:44] – Kleine Verbesserung in Aufgabe 6b) + Formatierung angepasst. dom
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 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] == true && c == cs[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, cs, v, c)) { +        if (isSafe(g, cs, v, c)) { 
-            //try and recurse +            int color = cs[v];  // aktuelle Farbe sichern 
-            cs[v] = c; +            cs[v] = c;  // neue Farbe setzen  
-            if(helper(g, cs, m, v+1)) {+             
 +            if (helper(g, cs, c, v + 1)) { // Rekursion
                 return true;                 return true;
             }             }
-            //backtrack +            // 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, cs, m, 0)) {+     
 +    if (!helper(g, cs, m, 0)) {
         return null;         return null;
     }     }