diff options
| -rw-r--r-- | graph/graph.tex | 2 | ||||
| -rw-r--r-- | math/math.tex | 48 | ||||
| -rw-r--r-- | sonstiges/sonstiges.tex | 2 | ||||
| -rw-r--r-- | tcr.pdf | bin | 179603 -> 191255 bytes | |||
| -rw-r--r-- | tcr.tex | 3 | ||||
| -rw-r--r-- | toDo.txt | 5 |
6 files changed, 55 insertions, 5 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index 8d525f6..98d5ffd 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -66,6 +66,6 @@ Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen. \item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten. \end{enumerate} -\subsubsection{Maximal Cardinatlity Bipartite Mathcing} +\subsection{Maximal Cardinatlity Bipartite Mathcing} \lstinputlisting{graph/maxCarBiMatch.cpp} diff --git a/math/math.tex b/math/math.tex index feb89ff..8300ee4 100644 --- a/math/math.tex +++ b/math/math.tex @@ -49,3 +49,51 @@ Obiger Code findet kein maximales Teilfeld, das über das Ende hinausgeht. Dazu: \item nimm Maximum aus gefundenem Maximalem und Allem\textbackslash Minimalem \end{enumerate} +\subsection{Kombinatorik} + +\subsubsection{Berühmte Zahlen} +\begin{tabular}{|l|l|l|} + \hline + \textsc{Fibonacci} & $f(0) = 0 \quad f(1) = 1 \quad f(n+2) = f(n+1) + f(n)$ & siehe Bemerkungen \ref{bem:fibonacciMat}, \ref{bem:fibonacciGreedy}\\ + \textsc{Catalan} & $C_n = \sum\limits_{k = 0}^{n - 1} C_kC_{n - 1 - k} = \frac{1}{n + 1}{2n \choose n} = \frac{2(2n - 1)}{n+1} \cdot C_{n-1}$ & siehe Bemerkungen \ref{bem:catalanOverflow}, \ref{bem:catalanAnwendung}\\ + \hline +\end{tabular} + +\begin{bem}\label{bem:fibonacciMat} +$\left(\begin{array}{cc} 0 & 1 \\ 1 & 1\end{array}\right)^n \cdot \left(\begin{array}{c}0 \\ 1\end{array}\right) = \left(\begin{array}{c}f_n \\ f_{n+1}\end{array}\right)$ +\end{bem} + +\begin{bem}[\textsc{Zeckendorfs} Theorem]\label{bem:fibonacciGreedy} +Jede positive natürliche Zahl kann eindeutig als Summe einer oder mehrerer verschiedener \textsc{Fibonacci}-Zahlen geschrieben werden, sodass keine zwei aufeinanderfolgenden \textsc{Fibonacci}-Zahlen in der Summe vorkommen. + +\emph{Lösung: } Greedy, nimm immer die größte \textsc{Fibonacci}-Zahl, die noch hineinpasst. +\end{bem} + +\begin{bem}\label{bem:catalanOverflow} +\begin{itemize} + \item Die erste und dritte angegebene Formel sind relativ sicher gegen Overflows. + \item Die erste Formel kann auch zur Berechnung der \textsc{Catalan}-Zahlen bezüglich eines Moduls genutzt werden. +\end{itemize} +\end{bem} + +\begin{bem}\label{bem:catalanAnwendung} +Die \textsc{Catalan}-Zahlen geben an: $C_n =$ +\begin{itemize} + \item Anzahl der Binärbäume mit $n$ Knoten + \item Anzahl der validen Klammerausdrücke mit $n$ Klammerpaaren + \item Anzahl der korrekten Klammerungen von $n+1$ Faktoren + \item Anzahl der Möglichkeiten ein konvexes Polygon mit $n+2$ Ecken in Dreiecke zu zerlegen. + \item Anzahl der monotonen Pfade in einem $n \times n$-Gitter, die nicht die Diagonale kreuzen. (zwischen gegenüberliegenden Ecken) +\end{itemize} +\end{bem} + +\subsubsection{Verschiedenes} +\begin{tabular}{|l|l|} + \hline + Hanoi Towers (min steps) & $T_n = 2^n - 1$\\ + regions by $n$ lines & $n\left(n + 1\right) / 2 + 1$\\ + bounded regions by $n$ lines & $\left(n^2 - 3n + 2\right) / 2$\\ + labeled rooted trees & $n^{n-1}$\\ + labeled unrooted trees & $n^{n-2}$\\ + \hline +\end{tabular}
\ No newline at end of file diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex index 1a51ad9..375dc6b 100644 --- a/sonstiges/sonstiges.tex +++ b/sonstiges/sonstiges.tex @@ -9,7 +9,7 @@ \end{enumerate} \subsection{Sortieren in Linearzeit} -Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort \lstinline{bucketSort(vector<int> ..., n);} schneller. +Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Bucketsort schneller. \subsubsection{Bucketsort} \lstinputlisting{sonstiges/bucketSort.cpp} Binary files differ@@ -47,6 +47,9 @@ \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} \usepackage{multicol} +\usepackage{multirow} + +\newtheorem{bem}{Bemerkung} \title{Team Contest Reference} \author{ChaosKITs \\ Karlsruhe Institute of Technology} @@ -1,7 +1,6 @@ -- mathe formeln, kombinatorik (catalan, stirling, euler, ...) - bitonic tsp - josephus problem - min cost max flow - roman numerals -- towers of hanoi -- NIM GAMES (WICHTIG)
\ No newline at end of file +- NIM GAMES (WICHTIG) +- bit operationen (WICHTIG)
\ No newline at end of file |