Uebungsblatt 9 Name: Joe User Tutor: ???? Email: juser@icp.uni-stuttgart.de ========== AUFGABE 9.1 (LaTeX und Fibonacci) ========== LaTeX-Datei: \documentclass[a4paper]{scrartcl} \usepackage{hyperref} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} \usepackage{graphicx} \usepackage{amsmath} \begin{document} \title{Fibonacci-Zahlen mit Python} \author{Olaf Lenz} \date{\today} \maketitle \tableofcontents \newcommand{\fib}{\text{fib}} \section{Definition der Fibonacci-Zahlen} \label{sec:def} Die Fibonacci-Zahlen werden normalerweise wie in Gleichung \eqref{eq:fib1} definitiert. \begin{equation} \fib(n) = \begin{cases} 1 & \text{falls } n \le 1\\ \fib(n-1)+\fib(n-2) & \text{sonst} \end{cases} \label{eq:fib1} \end{equation} \noindent Eine äquivalente Definition der Fibonacci-Zahlen ist in Gleichung \eqref{eq:fib2} gegeben. \begin{align} \label{eq:fib2} \fib_\text{eff}(n) &= \fib_{1,1}(n) \intertext{wobei} \fib_{a,b}(n) &= \begin{cases} a & \text{falls } n = 0\\ b & \text{falls } n = 1\\ \fib_{b, (a+b)}(n-1) & \text{sonst}\\ \end{cases}\nonumber \end{align} \section{Laufzeiten} Wenn man die in Abschnitt \ref{sec:def} definitierten Funktionen in Python\footnote{\url{http://www.python.org}} implementiert, dann erhält man die in Tabelle \ref{tab:fib} auf Seite \pageref{tab:fib} angegebenen Ergebnisse und Laufzeiten. Der semilogarithmische Plot der Laufzeiten in Abbildung \ref{fig:fib} auf Seite \pageref{fig:fib} zeigt, daß die Laufzeit der Definition nach Gleichung \eqref{eq:fib1} exponentiell anwächst. \begin{table}[htbp] \centering \begin{tabular}{|r|r|r|r|} \hline \textbf{N} & \textbf{fib(N)} & \textbf{T1} $[\mu s]$ & \textbf{T2} $[\mu s]$\\ \hline 4 & 5 & 2.000000 & 1.100000\\ 5 & 8 & 3.000000 & 1.400000\\ 6 & 13 & 5.000000 & 1.600000\\ 7 & 21 & 8.000000 & 1.900000\\ 8 & 34 & 12.000000 & 2.200000\\ 9 & 55 & 19.000000 & 2.500000\\ 10 & 89 & 31.000000 & 2.700000\\ 11 & 144 & 50.000000 & 3.000000\\ 12 & 233 & 82.000000 & 3.300000\\ 13 & 377 & 131.000000 & 3.500000\\ 14 & 610 & 211.000000 & 3.900000\\ 15 & 987 & 344.000000 & 4.300000\\ 16 & 1597 & 553.000000 & 4.600000\\ 17 & 2584 & 891.000000 & 4.900000\\ \hline \end{tabular} \caption{Ergebnisse und Laufzeiten der Berechnung von Fibonacci-Zahlen mit Hilfe von Python.} \label{tab:fib} \end{table} \begin{figure}[htbp] \centering \includegraphics[width=0.8\linewidth]{plot} \caption{Semilogarithmischer Plot der Laufzeiten der Berechnung von Fibonacci-Zahlen mit Hilfe von Python.} \label{fig:fib} \end{figure} \end{document} ========== 9.1.3.1 Python-Skript: (Es reicht auch die Ausgabezeile) print "%d & %d & %5.1f & %5.1f\\\\" \ % (i, fib2(i), t1[-1]*1000000, t2[-1]*1000000)