From f201d8cbb514802529d9a2f3024a258600d46aaa Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Mon, 24 Nov 2014 15:16:57 +0100 Subject: max Teilfeld und to-do-liste --- math/math.tex | 10 ++++++++++ math/maxTeilfeld.cpp | 14 ++++++++++++++ 2 files changed, 24 insertions(+) create mode 100644 math/maxTeilfeld.cpp (limited to 'math') 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 -- cgit v1.2.3