0

Wir behandeln im Unterricht gerade das Thema Graphen und DFS und BFS. Als Aufgabe habe ich eine sehr theoretische Aufgabe bekommen. Nämlich die folgende:

Jeder Spielstand von Tic-Tac-Toe wird in einem Graphen dargestellt.

a) Wie viele Knoten auf Stufe 1 existieren (also alle Spielstände wenn Spieler X 1 Feld gesetzt)?

Hier hätte ich gesagt, dass es 9 Spielstände gibt. Das heisst in jedem Feld ein "X".

b) Wie viele Knoten auf Stufe 2?

Bei dieser Aufgabe, hätte ich gesagt, das wären hier nur 8 Spielstände pro oberen Spielstand. Das wäre ja dann: 9*8 = 72

c) Wie viele Spielstände die in einem Gewinn für X resultieren gibt es bei Stufe 8

Stimmt dann hier meine Rechnung: 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 = 362'880 Spielstände. Stimmt hier meine Rechnung?

d) Wie viele wirklich unterschiedliche Spielstände gibt es auf Level 2? Mit einemm DAG (Directed acyclic graph) können viele Knoten eliminiert werden, da einige Knoten denselben Spielstand repräsentieren (z.B. man rotiert oder spiegelt das Feld)

Wie geht man hier vor? Ich weiss auf Level 1 gibt es zum Beispiel nur 3 verschiedene Spielstände.

Diese Frage melden
gefragt

Punkte: 10

 

1
Bei der Aufgabe ist völlig unklar, wie ein Spielstand durch einen solchen Graphen dargestellt wird.   ─   cauchy 03.07.2022 um 01:31

Ich hätte mir so etwas vorgestellt: http://www.aplu.ch/home/gifs/tictree.gif
  ─   user2ac83f 03.07.2022 um 08:44

So ist es wohl gemeint, das legt auch die Formulierung zu a) nahe. Die Vorgabe "Jeder Spielstand...." lässt das allerdings offen, da ist sicher auch anderes denkbar. Gemeint ist wohl "Jeder Spielstand... wird ALS KNOTEN in einem Graphen dargestellt."   ─   mikn 03.07.2022 um 13:15

@mikn wäre dies dann so gemeint, dass die Knoten den Spielstand (Gewonnen X, Unentschieden, Gewonnen Y)?

Ich denke jedoch, dass schon das die andere Variante gemeint ist. Hättet ihr eine Antwort zu meinen Fragen?
  ─   user2ac83f 03.07.2022 um 14:54

Achso, ja, unter Spielstand könnte man auch Sieg-unentschieden-Niederlage verstehen. Wie es gemeint ist, kann Dir nur der Autor der Aufgabenstellung sagen (der offensichtlich meint, dass es ja klar gesagt ist).
Ich würde Deine Variante annehmen.
Dann würde ich sagen: a) 9, b) 72. Aber c) was anderes, denn es soll ja ein Gewinn für X resultieren (vermutlich erst im letzten Zug, sonst würde das Spiel ja vorher enden (ist aber auch nicht ganz klar).
  ─   mikn 03.07.2022 um 15:33
Kommentar schreiben
0 Antworten