Differences

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

--- lehrkraefte:blc:informatik:ffprg1-2019:arrays-anwendung2 [2019/03/26 08:30] – created Ivo Blöchliger
+++ lehrkraefte:blc:informatik:ffprg1-2019:arrays-anwendung2 [2019/03/26 08:35] (current) – [Variante Vektorgeometrie] Ivo Blöchliger
@@ Line 1: / Line 1: @@
+====== Wer hat gewonnen? ======
+**Ausgangslage**: Der Zustand des Spielfeldes ist in einer Variable ''feld'' als 2-dimensionales Array gespeichert. Die Einträge sind Strings der Länge 1, entweder " ", "x" oder "o".
+Zu schreiben ist eine Funktion, die überprüft ob 3 (oder allgemeiner $n$) gleiche Einträge "x" oder "o" auf einer Linie sind, horizontal, vertikal oder diagonal.
+Die Grösse vom Spielfeld ist ''w=len(feld)'' in $x$-Richtung und ''h=len(feld[0])'' in $y$-Richtung (für width und height).
+===== Variante "viele if" =====
+Für ein 3x3-Feld könnte man mit einem Haufen if-Abfragen das Feld überprüfen, z.B. wie folgt:
+  if feld[0][0]!=" " and feld[0][0]==feld[1][0] and feld[1][0]==feld[2][0]:
+    return feld[0][0]  # Gewinner melden
+  ...
+  ...
+  return " "   # Niemand hat gewonnen
+Sobald das Feld grösser als 3x3 ist (z.B. 7x6 für Vier gewinnt), ist das natürlich völlig unpraktikabel.
+===== Variante Vektorgeometrie =====
+Die Grundidee ist die gleiche wie bei der Parameterdarstellung der Geraden in der Vektorgeometrie. Man definiert einen Startpunkt und einen Richtungsvektor, der die Verschiebung angibt.
+D.h. Man startet z.B. im Punkt (0,2) und verschiebt dann schrittweise um den Vektor $\binom{1}{-1}$, um die Punkte (1,1) und (2,0) zu erhalten. Auf diesem Weg zählt man, wie viele Male man hintereinander den gleichen Eintrag findet. **Achtung**, der folgende Code ist ein **Pseudo-Code**, der aber an Python angelehnt ist:
+  punkt = startpunkt
+  anzahl = 0
+  was = " "
+  while (punkt noch im feld):
+     inhalt = feld[punktx][punkty]  # Aktuellen Feldinhalt auslesen
+       if inhalt==" ":  # Leeres Feld
+          anzahl = 0
+          was = " "
+       else:
+          if inhalt==was:  # Gleiches Feld!
+             anzahl+=1     # Zähler erhöhen
+             if anzahl==3  # Linie voll? Könnte auch eine grössere Zahl sein.
+                return was  # Plus eventuell melden, wo
+          else:
+             anzahl = 1
+             was = inhalt
+     punkt = punkt + richtung
+Was jetzt noch fehlt, sind die Startpunkte für die Überprüfung und die Richtungsvektoren. Die Idee ist, die Startpunktskoordinaten in einer for-Schleife zu erzeugen.
+==== Variante "noch ein bisschen effizienter" ====
+Es muss nicht jedes Mal das ganze Feld überprüft werden. Es reicht, von der Position aus zu zählen, wo das Feld verändert wurde. Dazu muss in die vier Richtungen (d.h. horizontal, vertikal und 2 diagonal) vorwärts **und** rückwärts gezählt werden.
+Dazu schreibt man am einfachsten eine for-Schleife über die möglichen Richtungen:
+  for dir in [[1,0],[1,1], [0,1], [-1,1]]:
+    anzahl = In Richtung ''dir'' zählen
+    anzahl += In Richtung ''-dir'' zählen
+    anzahl +=1  # Die Position selbst zählen
+    if anzahl==3:  # Oder was auch immer
+       return True  # Sieg melden
+  return False  # Kein Sieg