max Teilfeld und to-do-liste

2 files changed, 24 insertions, 0 deletions

diff --git a/math/math.tex b/math/math.tex
index 71f9c0e..ca67f0e 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -39,3 +39,13 @@ Weise jedem Zustand $X$ wie folgt eine \textsc{Grundy}-Zahl $g\left(X\right)$ zu
 \]
 $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)$.
+
+\subsection{Maximales Teilfeld}
+\lstinputlisting{math/maxTeilfeld.cpp}
+Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu:
+\begin{enumerate}
+	\item finde maximales Teilfeld, das nicht übers Ende geht
+	\item berechne minimales Teilfeld, das nicht über den Rand geht (analog)
+	\item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem
+\end{enumerate}
+
diff --git a/math/maxTeilfeld.cpp b/math/maxTeilfeld.cpp
new file mode 100644
index 0000000..2b732bb
--- /dev/null
+++ b/math/maxTeilfeld.cpp
@@ -0,0 +1,14 @@
+//N :=  length of field
+int maxStart = 1, maxLen = 0, curStart = 1, len = 0;
+double maxValue = 0, sum = 0;
+for (int pos = 0; pos < N; pos++) {
+	sum += values[pos];
+	len++;
+	if (sum > maxValue) { // neues Maximum
+		maxValue = sum; maxStart = curStart; maxLen = len;
+	}
+	if (sum < 0) { // alles zuruecksetzen
+		curStart = pos +2; len = 0; sum = 0;
+	}
+}
+//maxSum := maximaler Wert, maxStart := Startposition, maxLen := Laenge der Sequenz
\ No newline at end of file