1 files changed, 34 insertions, 0 deletions
diff --git a/reports/lab2/lab2.tex b/reports/lab2/lab2.tex
new file mode 100644
index 0000000..61b70aa
--- /dev/null
+++ b/reports/lab2/lab2.tex
@@ -0,0 +1,34 @@
+\documentclass[spec, och, labwork]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+
+\section*{Описание работы алгоритма}
+
+В качестве рекурсивного алгоритма будет рассмотрена задача о ходе коня "---
+задача о нахождении маршрута шахматного коня, проходящего через все поля доски
+по одному разу.
+
+Алгоритм нахождения данного пути можно описать следующим образом:
+\begin{enumerate}
+    \item Пометить текущую клетку;
+    \item Если все клетки помечены, то закончить алгоритм, иначе перейти к шагу 3;
+    \item
+        Перейти в одну из возможных не помеченных клеток. Если невозможно
+        совершить ни один ход, то снять метку с текущей клетки, вернуться в
+        предыдущую клетку и перейти к шагу 1.
+\end{enumerate}
+
+\subsection*{Оценка сложности}
+
+Так как из заданной клетки конь может перейти в 2-8 клеток, из которой он в
+свою очередь так же может перейти в 2-7 других клеток и т.д. Такой путь
+состоит из $n^2$ клеток. При этом доска также состоит из $n^2$ клеток.
+Таким образом, сложность данного алгоритма составляет $O(n^{2n^2})$
+
+\subsection*{Реализация на языке C++}
+
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../../knights-tour.cpp}
+
+\end{document}