From a4d473bfe1d1b77ebc0a6b061d4a126779f48c31 Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Mon, 24 Nov 2014 14:11:14 +0100 Subject: Grundy --- math/math.tex | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'math') diff --git a/math/math.tex b/math/math.tex index 973103a..71f9c0e 100644 --- a/math/math.tex +++ b/math/math.tex @@ -31,3 +31,11 @@ Sei $0 \leq x < n$. Definiere $d := gcd(x, n)$. \subsection{Primzahlsieb von Eratosthenes} \lstinputlisting{math/primeSieve.cpp} + +\subsection{Satz von \textsc{Sprague-Grundy}} +Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu: +\[ + g\left(X\right) := \min\{ \mathbb{Z}_0^+ \textbackslash \{g\left(Y\right)~|~Y \text{ von } X \text{ aus direkt erreichbar}\}\} +\] +$X$ ist genau dann gewonnen, wenn $g\left(X\right) > 0$ ist.\\\\ +Wenn man $k$ Spiele in den Zuständen $X_1, \ldots, X_k$ hat, dann ist die \textsc{Grundy}-Zahl des Gesamtzustandes $g\left(X_1\right) \oplus \ldots \oplus g\left(X_k\right)$. -- cgit v1.2.3