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
pruefungen:bachelor:aud:loesungss17 [12.07.2018 08:19]
LasagneAlForno
pruefungen:bachelor:aud:loesungss17 [24.07.2019 16:44]
dom Kleine Verbesserung in Aufgabe 6b) + Formatierung angepasst.
Zeile 222: 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 233: 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 259: 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;
     }     }