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

--- pruefungen:bachelor:aud:loesungss17 [12.07.2018 06:19] – LasagneAlForno
+++ pruefungen:bachelor:aud:loesungss17 [05.03.2020 12:05] (aktuell) – amelie.ka
@@ Zeile 222: / Zeile 222: @@
 <code java>
 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;
         }
@@ Zeile 233: / Zeile 234: @@
 <code java>
 boolean helper(boolean g[][], int cs[], int m, int v) {
-    //base case
+    // base case
-    if(v >= g.length) {
+    if (v >= g.length) {
         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   (Fehler?: sollte m statt c sein)
                 return true;
             }
-            //backtrack
+            // backtrack
-            cs[v] = 0;
+            cs[v] = color;
         }
     }
-    //finally give up
+    // keine Loesung gefunden -> Schritt zurueck
     return false;
 }
@@ Zeile 259: / Zeile 261: @@
 int[] color(boolean g[][], int m) {
     int[] cs = new int[g.length];
-    if(!helper(g, cs, m, 0)) {
+    if (!helper(g, cs, m, 0)) {
         return null;
     }