From bc6fa2f8d7967acd859c0f660cad81199e53b0fb Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 19 May 2022 14:12:12 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?=
 =?UTF-8?q?=D0=B5=20=D0=BE=D1=82=D1=87=D1=91=D1=82=D0=BE=D0=B2=20=D0=BF?=
 =?UTF-8?q?=D0=BE=20=D0=BF=D0=B5=D1=80=D0=B2=D1=8B=D0=BC=20=D1=82=D1=80?=
 =?UTF-8?q?=D1=91=D0=BC=20=D0=BB=D0=B0=D0=B1=D0=B0=D0=BC?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 reports/lab2/lab2.tex | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
 create mode 100644 reports/lab2/lab2.tex

(limited to 'reports/lab2/lab2.tex')

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}
-- 
cgit v1.2.3