diff options
| -rw-r--r-- | graph/graph.tex | 10 | ||||
| -rw-r--r-- | math/math.tex | 10 | ||||
| -rw-r--r-- | math/maxTeilfeld.cpp | 14 | ||||
| -rw-r--r-- | tcr.pdf | bin | 329385 -> 331381 bytes | |||
| -rw-r--r-- | toDo.txt | 11 |
5 files changed, 42 insertions, 3 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index e3fd262..bf23c5b 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -30,6 +30,16 @@ Alle kürzesten Pfade im Graphen. \item \textbf{Je nach Aufgabenstellung überprüfen, wie isolierte Punkte interpretiert werden sollen.} \item Der Code unten läuft in Linearzeit. Wenn das nicht notwenidg ist (oder bestimmte Sortierungen verlangt werden), gehts mit einem \lstinline{set} einfacher. \end{itemize} +\begin{figure}[h] +\begin{lstlisting} +VISIT(v): + forall e=(v,w) in E + delete e from E + VISIT(w) + print e +\end{lstlisting} +\caption{Idee für Eulerzyklen} +\end{figure} \lstinputlisting{graph/euler.cpp} \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} 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 Binary files differ@@ -1,4 +1,9 @@ -- max-Teilfeld - max cardinality bipartite matching -- mathe formeln, kombinatorik -- java big integer
\ No newline at end of file +- mathe formeln, kombinatorik (catalan, stirling, euler, ...) +- java big integer +- bitonic tsp +- josephus problem +- min cost max flow +- linear time sorting +- roman numerals +- towers of hanoi |