Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:glf25:labyrinthe:start [2026/02/06 08:42] – ↷ Links adapted because of a move operation Ivo Blöchliger
+++ lehrkraefte:blc:informatik:glf25:labyrinthe:start [2026/03/26 11:08] (current) – [Wegfindung mit Todo-Liste] Ivo Blöchliger
@@ Line 1: / Line 1: @@
 ====== Labyrinthe ======
   * [[lehrkraefte:blc:informatik:glf25:labyrinthe:intro|Intro]], Wegfindungsalgorithmen als Pseudocode
-  * [[labyrinthe:lib|Klassen Laby und Zelle]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:lib|Klassen Laby und Zelle]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:wegfindung|Wegfindungsalgorithmen]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:wegfindung-mit-liste|Wegfindung mit Todo-Liste]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:wegfindung-tiefen-breiten-random|Tiefensuche, Breitensuche, Zufallssuche]] Handhabung der Todo-Liste
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:labyrinth-generieren|Labyrinthe generieren]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:bilder-einlesen|Bilder einlesen]]
+  * [[lehrkraefte:blc:informatik:glf25:labyrinthe:modularisierung|Modularisierung von Verteilen des Codes auf mehrere Dateien.]]
+===== Mögliche Prüfungsfragen =====
+Der Begriff «Labyrinth» bezieht sich im folgenden immer auf rechteckiges Raster aus quadratischen Zellen, die mit einem beliebigen Symbol markiert sein können und von denen es bis zu vier Nachbarn (rechts, unten, links, oben) geben kann, wobei dazwischen jeweils eine Mauer vorhanden ist, oder eben nicht.
+==== Wegfindung mit Todo-Liste ====
+Gegeben ist folgener Pseudo-Code
+<code txt>
+Gegeben: ein Labyrinth und eine Startzelle. Alle Zellen unmarkiert.
+Markiere Startzelle mit 'S'
+Neue Todo-Liste mit Startzelle als einzigen Eintrag.
+So lange Todo-Liste nicht leer:
+    Entferne die letzte Zelle aus der Todo-Liste, nenne diese «aktuell».
+    Wenn es eine unmarkierte Nachbarszelle gibt, keine Mauer dazwischen:
+        Markiere Nachbarszelle mit '.'
+        Füge die «aktuelle» Zelle der Todo-Liste hinzu
+        Füge die Nachbarszelle der Todo-Liste hinzu
+</code>
+  * Erklären Sie, warum jede direkte Nachbarszelle (ohne Mauer dazwischen) von 'S' besucht wird.
+  * Erklären Sie, warum jede von 'S' aus erreichbare Zelle auch besucht und markiert wird.
+  * Erklären Sie, warum die Todo-Liste immer einen direkten Weg von 'S' zur Aktuellen Zelle enthält.
+  * Welche Zelle wird zuallerletzt aus der Todo-Liste entfernt (bevor diese dann definitiv leer ist und die Wiederholung abgebrochen wird).
+==== Generierung eines Labyrinths ====
+Gegeben ist folgener Pseudo-Code
+<code txt>
+Gegeben: Breite und Höhe des zu generierenden Labyrinths
+Erzeuge ein neues Labyrinth mit gegebener Grösse, alle Mauern geschlossen, alle Zellen unmarkiert.
+Sei die Startzelle die Zelle oben links.
+Markiere Startzelle mit 'S'
+Neue Todo-Liste mit Startzelle als einzigen Eintrag.
+So lange Todo-Liste nicht leer:
+    Entferne die letzte Zelle aus der Todo-Liste, nenne diese «aktuell».
+    Wenn es eine unmarkierte Nachbarszelle mit einer Mauer dazwischen gibt, wähle diese zufällig aus allen möglichen aus:
+        Entferne die Mauer zwischen «aktuell» und der Nachbarszelle
+        Markiere Nachbarszelle mit '.'
+        Füge die «aktuelle» Zelle der Todo-Liste hinzu
+        Füge die Nachbarszelle der Todo-Liste hinzu
+</code>
+  * Erklären Sie, warum es danach zu sämtlichen Zellen einen Weg von der Startzelle aus gibt.
+  * Erklären Sie, warum es nie zwei unterschiedliche Wege von der Startzelle aus zu einer Zelle gibt.
+  * Erklären Sie, warum es zwischen zwei beliebigen Zellen exakt einen Weg gibt (und nicht zwei oder null).
+  * Erklären Sie, warum der obige Algorithmus relativ lange Gänge ohne Kreuzungen erzeugt.
+    * Wie könnte der Algorithmus abgeändert werden, dass «etwas mehr Kreuzungen» erzeugt werden?