blob: 61b70aa10dd8c8fe6947f58e6dffb28b4d6d546d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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}
|
