Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start [25.02.2025 10:09] – Frank Schiebel
+++ faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:start [25.02.2025 14:44] (aktuell) – [Algorithmus unplugged] Frank Schiebel
@@ Zeile 9: / Zeile 9: @@
 ==== Algorithmus unplugged ====
-Wie würde man das Problem algorithmisch lösen? Am besten probiert man es einmal ohne PC an einem normalen Schachbrett aus - wenn du keines zur Hand hast, kannst du [[https://info-bw.de/static/h5p/8-damen-problem.html|diese Aktivität im Browser]] verwenden, um die 8 Damen auf einem virtuellen Schachbrett zu platzieren.
+Wie würde man das Problem algorithmisch lösen? Am besten probierst du es ohne PC an einem normalen Schachbrett aus - wenn du keines zur Hand hast, kannst du [[https://info-bw.de/static/h5p/8-damen-problem.html|diese Aktivität im Browser]] verwenden, um die 8 Damen auf einem virtuellen Schachbrett zu platzieren. Um mit weniger Feldern zu beginnen, kannst du auch die {{ :faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:n-damen-unplugged.pdf |folgende Vorlage}}verwenden.
 <WRAP center round info 75%>
 Lies hier erst weiter, nachdem du dir selbst Gedanken gemacht hast, wie du vorgehen könntest.
@@ Zeile 44: / Zeile 44: @@
 Arbeite mit der folgenden Vorlage: https://codeberg.org/qg-info-unterricht/bluej-8-Damen-console
-**(A)** Modelliere das Feld mit einem zweidimensionalen Array des Typs ''boolean''. Definiere das Feld als Attribut der Klasse, initialisiere es im Konstrunktor.
+**(A)** Modelliere das Feld mit einem zweidimensionalen Array des Typs ''boolean''. Definiere das Feld als Attribut der Klasse, initialisiere es im Konstruktor.
 **(B)** Implementiere eine Methode ''druckeFeld()'', die den gesamten Zustand des Schachbretts ausdruckt. Du kannst bei der Ausgabe z.B. einen Unterstrich für ein leeres Feld des Bretts, X für ein Feld mit einer Dame verwenden((Du kannst auch Unicode Zeichen wie ⬚ und ♕ verwenden)). Teste deine Methode, indem du im Konstruktor das leere Feld ausgeben lässt, eine oder mehrere Damen setzt und dann das Feld mit den Damen ausgeben lässt.
@@ Zeile 77: / Zeile 77: @@
   * Überprüfe, ob deine Methode beim Aufruf aus der Objektleiste die korrekten Antworten für mögliche Damen auf den Feldern ''(1|0)'', ''(1|1)'', ''(1|2)'', ''(1|3)'' und ''(1|6)'' gibt.
-++++ Hilfestellung 1 zu ''istPositionErlaubt'': |
+++++ Hilfestellung 1 zu "istPositionErlaubt": |
+<code java>
+public boolean istPositionErlaubt(int zeile, int spalte) {
+        // Füge hier deinen Code für die Kollisionserkennung ein.
+        // Einen Lösungsvorschlag findest du im Wiki
+        // Alle Zeilen von 0 bis zeile-1 untersuchen:
+        for(int zeileAktuell=0; zeileAktuell<zeile; zeileAktuell++) {
+            // Felder oberhalb untersuchen, wenn Dame:
+            // return false
+            if( FIXME ) {
+                return false;
+            }
+            // Felder der Diagonalen untersuchen, wenn Dame:
+            // return false
+            // Linke Diagonale
+            if( FIXME ) {
+                return false;
+            }
+            // Rechte Diagonale
+            if( FIXME ) {
+                return false;
+            }
+        }
+        return true;
+    }
+</code>
 ++++
+++++ Lösungsvorschlag zu "istPositionErlaubt": |
+<code java>
+public boolean istPositionErlaubt(int zeile, int spalte) {
+        // Füge hier deinen Code für die Kollisionserkennung ein.
+        // Einen Lösungsvorschlag findest du im Wiki
+        // Alle Zeilen von 0 bis zeile-1 untersuchen:
+        for(int zeileAktuell=0; zeileAktuell<zeile; zeileAktuell++) {
+            // Felder oberhalb untersuchen, wenn Dame:
+            // return false
+            if(feld[zeileAktuell][spalte]) {
+                return false;
+            }
+            // Felder der Diagonalen untersuchen, wenn Dame:
+            // return false
+            if(spalte - (zeile-zeileAktuell) >= 0 && feld[zeileAktuell][spalte - (zeile-zeileAktuell)] ) {
+                return false;
+            }
+            if( spalte + (zeile-zeileAktuell) < SIZE && feld[zeileAktuell][spalte + (zeile-zeileAktuell)] ) {
+                return false;
+            }
+        }
+        return true;
+    }
+</code>
+++++
+**(E)** Wenn du geprüft hast, dass deine ''istPositionErlaubt''-Methode korrekt funktioniert, kannst du den Pseudocode für ''befuelleZeile'' in deinem BlueJ-Projekt implementieren. Tipp: Nicht zuviel nachdenken, versuche den Pseudocode in  Java zu "übersetzen".
+Teste die Methode mit Schachbrettern 4x4 und 8x8. Überprüfe die ausgegebenen Lösungen stichprobenartig.
 {{:aufgabe.png?nolink  |}}
 === (A2) ===
-Was ist der Basisfall dieser Rekursion?
+Was ist der Basisfall dieser Rekursion? Finde einen Weg, dir mit dem Debugger den Stack anzeigen zu lassen, wenn der Basisfall eintritt. Was fällt dir dabei auf?
 {{:aufgabe.png?nolink  |}}
-=== (A3) - Für die Schnellen ===
+=== (A3) ===
 Erweitere das Programm: Lass dir ausgeben, wie viele Lösungen gefunden wurden.
-{{:aufgabe.png?nolink  |}}
-=== (A4) - Für die Schnellen ===
-Wenn du früh fertig bist, dann kannst du überlegen, ob du selbst eine andere/eigene Lösung für die Kollisionsprüfung auf der Diagonalen findest (das ist ziemlich knifflig, wenn man nicht den mathematischen Kniff der Vorlage nutzt).\\ \\
 <WRAP center round info 75%>
@@ Zeile 98: / Zeile 156: @@
 https://www.mathematik.ch/spiele/N_Damenproblem/
 </WRAP>
+==== Material ====
+{{simplefilelist>:faecher:informatik:oberstufe:algorithmen:rekursion:backtracking:8-damen-problem:*}}