Автор работы: Пользователь скрыл имя, 03 Декабря 2012 в 03:28, курсовая работа
В данной задаче нужно обойти конем всю шахматную доску, при этом побывав в каждой из клеток лишь один раз.
В данной работе, я рассмотрю два разных алгоритма для решения этой задачи: итеративный и рекурсивный. Без каких либо усовершенствований, они действуют методом полного перебора, до тех пор, пока не получат результат, либо переберут все возможные варианты. Поэтому, без оптимизации они не эффективны.
Обход конем 3
Генерация перестановок 8
Гамильтонов цикл 11
Магические квадраты
Литература 15
27
Результат работы программы:
Для разбора работы алгоритма возьмем более простой граф:
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
2
5
3
Подбор будет происходить так:
Листинг
алгоритма:
void
gamilt(int k)
{
for
(int y = 1; y < N; y++) //идем по всем вершинам
{
if
(graph[x[k - 1]][y] != 0) // если соединены
{
if
((k==N-1)&&(y == v0)) // если текущая вершина - замыкающая маршрута
{
for
(int i=0;i<N-1;i++) cout<<x[i]<<" ";
cout
<<endl;
}
else
{
if
(dop[y] == 1) //если y еще не включена в маршрут
{
x
[k] = y;
dop
[y] = 0; //включаем y в маршрут
gamilt
(k + 1);
dop
[y] = 1;
}
}
}
}
}
void
gamiltCycle()
{
for
(int i = 0; i < N; i++) dop[i] = 1; //все вершины изначально не включены в маршрут
v0 = 1;
//начало
x
[0] = v0;
dop
[v0] = 0;
gamilt
(1);
}
Магические квадраты
Магический квадрат – квадрат, заполненный натуральными числами таким образом, что сумма всех столбцов, строк и диагоналей одна и та же.
Я рассмотрю алгоритмы построения трех типов таких квадратов:
- квадрат с нечетной стороной
- квадрат с четной стороной
- дважды четный квадрат
Нечетный квадрат
Метод диагоналей
Изначально ставим единицу по центру в первой строке
. Дальше начинаем подряд
Псевдокод процедуры заполнения квадрата:
-изначальные координаты
i и j : середина первой строки
do
{
if
(если дошли до правого верхнего угла) {
-меняем координаты (
i,j) на клетку под предыдущим числом
}
if
(если дошли до верхней границы) -переходим на последнюю строку
if (если дошли до правой границы) - переходим на первый столбец
if
(выбранная клетка пустая) {
-ставим цифру
-увеличиваем цифру
-устанавливаем координаты на следующую клетку вверх по диагонали
}
else {
-ставим цифру под предыдущей цифрой
-увеличиваем цифру
-устанавливаем координаты на следующую клетку вверх по диагонали
}
}
while (цифра не равна максимально возможной)
Реализация на С++
:
void
generate() {
int
i=1;
int
j=(N-1) / 2 +1;
int
b=1;
matrix[
i][j]=0;
do
{
if
(i<1&&j>=N) {i=i+2;j--;}
if
(i<=0) i=N-1;
if
(j>N-1) j=1;
if
(matrix[i][j]==0) {
matrix[
i][j]=b;
i
--;
j
++;
b
++;
}
else {
matrix[
i+2][j-1]=b;
b
++;
i
++;
}
}
while
(b<=(N-1)*(N-1));
}
Сгенерированный программой квадрат 5х5:
Метод террас
Для примера создадим магический квадрат размерности 5х5. Для этого к каждой стороне квадрата нужно присоединить так называемые
“террасы”.
После этого все
“длинные” диагонали снизу вверх заполняются подряд идущими цифрами
5 | |||||||||||||||||||||
4 |
10 | ||||||||||||||||||||
3 |
9 |
15 | |||||||||||||||||||
2 |
8 |
14 |
20 | ||||||||||||||||||
1 |
7 |
13 |
19 |
25 | |||||||||||||||||
6 |
12 |
18 |
24 | ||||||||||||||||||
11 |
17 |
23 | |||||||||||||||||||
16 |
22 | ||||||||||||||||||||
21 | |||||||||||||||||||||
После этого цифры с террас переносятся в квадрат таким образом: новое место цифры будет
n-ой клеткой, считая от текущей клетки террасы. n- порядок квадраты. Выполнив эти перемещения мы получим магический квадрат.
5 | |||||||||||||||||||||
4 |
10 | ||||||||||||||||||||
3 |
16 |
9 |
22 |
15 | |||||||||||||||||
2 |
20 |
8 |
21 |
14 |
2 |
20 | |||||||||||||||
1 |
7 |
25 |
13 |
1 |
19 |
25 | |||||||||||||||
6 |
24 |
12 |
5 |
18 |
6 |
24 | |||||||||||||||
11 |
4 |
17 |
10 |
23 | |||||||||||||||||
16 |
22 | ||||||||||||||||||||
21 | |||||||||||||||||||||
Четный квадрат
Метод разбиения на квадраты
Чет
ный квадрат – квадрат со стороной n=2m, где m=2r+1.
Разобьем основной квадрат на 4 квадрата со сторонами
m и заполним весь квадрат подряд идущими цифрами от 1 до n2.
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 |
35 |
36 |
Затем первые
r(в данном примере r=1) цифр в первом квадрате пометим знаком *. Следующую цифру знаком - . Следующую: |. И циклически сдвинем их по всему квадрату
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 |
35 |
36 |
Знаком * пометим и цифры, которые симметричны относительно вертикали уже помеченным цифрам.
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 |
35 |
36 |
Затем меняем цифры местами таким образом:
цифры со знаком * меняем местами с симметричной относительно центра цифрой. Со знаком – относительно серединной горизонтали, а | относительно серединной вертикали. В итоге получится магический квадрат:
36 |
32 |
4 |
3 |
5 |
31 |
12 |
29 |
27 |
10 |
26 |
7 |
19 |
17 |
22 |
21 |
14 |
18 |
13 |
20 |
16 |
15 |
23 |
24 |
25 |
11 |
9 |
28 |
8 |
30 |
6 |
2 |
33 |
34 |
35 |
1 |
Листинг функции генерации квадрата:
void
generate() {
int
k=1; // заполняем матрицу числами
for
(int i=1; i<=N; i++)
{
for
(int j=1; j<=N; j++)
{
a[
i][j]=k; k++;
}
}
int
r = ((N)/2 -1) /2; int m=(N) / 2;
for
(int i= 1;i<= m; i++) // инвертируем диагонали
{
int
j = i;
for
(int k = 1; k<= r ;k++)
{
if
(j > m) j = 1;
int
s= N- i +1;
int
b = N - j + 1;
swap(
a[i][j], a[s][b]);
swap(
a[i][b], a[s][j]);
j++
;
}
}
int
i=1; int j=r+1; // обмениваем относительно горизонтали
for
(int k=1; k<=m; k++) {
if
(j > m) j = 1;
int
s = N - i + 1;
swap(
a[i][j], a[s][j]);
i++
; j++;
}
i
= 1; j = r + 2;// обмениваем относительно вертикали
for
(int k = 1; k<= m;k++) {
if
(j > m) j = 1;
int
b = N - j + 1;
swap(
a[i][j], a[i][b]);
i++
; j++;
}}
Псевдокод:
-заполняем матрицу подряд идущими числами
r
= количество диагоналей для обмена
m
= количество элементов в малом квадрате
for
(по всем элементам малого квадрата(i)) {
j=i
for
(по всем дигоналям(r) для обмена(k)) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
-меняем местами текущие элементы каждой из диагоналей
}
}
j=
следующая клетка, после диагоналей
for
(по всем элементам малого квадрата) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
- обмениваем текущий элемент с
симметричным ему относительно горизонтали
}
j=
следующая клетка, после диагоналей +1
for
(по всем элементам малого квадрата) {
if
(столбец вышел за пределы малого квадрата) -снова переходим на первый столбец
- обмениваем текущий элемент с
симметричным ему относительно вертикали
}
Результат работы:
Дважды четные квадраты
Дважды ч
етный квадрат – квадрат со стороной n=2m, где m=2r.
“
Шахматный” способ
Выпишем в квадрат все числа от 1 до
n2.
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 |
35 |
36 |
37 |
38 |
39 |
40 |
41 |
42 |
43 |
44 |
45 |
46 |
47 |
48 |
49 |
50 |
51 |
52 |
53 |
54 |
55 |
56 |
57 |
58 |
59 |
60 |
61 |
62 |
63 |
64 |
Разделим квадрат на 4 квадрата порядка