Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов

Автор работы: Пользователь скрыл имя, 03 Декабря 2012 в 03:28, курсовая работа

Краткое описание

В данной задаче нужно обойти конем всю шахматную доску, при этом побывав в каждой из клеток лишь один раз.
В данной работе, я рассмотрю два разных алгоритма для решения этой задачи: итеративный и рекурсивный. Без каких либо усовершенствований, они действуют методом полного перебора, до тех пор, пока не получат результат, либо переберут все возможные варианты. Поэтому, без оптимизации они не эффективны.

Содержание

Обход конем 3
Генерация перестановок 8
Гамильтонов цикл 11
Магические квадраты
Литература 15
27

Прикрепленные файлы: 1 файл

Курсовая СИАКОД.docx

— 315.12 Кб (Скачать документ)

 

Результат работы программы:

 

Для разбора работы алгоритма возьмем более простой граф:

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





height: 12pt; z-index: 0;">

                          2                                          


                     5


3                                     4


 

 

Подбор  будет происходить так:

 



 

 

 

 

 

 

 

Листинг

 алгоритма:

 

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);

}

 

 

 

 

 

 

 

 

 

Магические квадраты

Магический  квадрат – квадрат, заполненный  натуральными числами таким образом, что сумма всех столбцов, строк  и диагоналей одна и та же.

Я рассмотрю  алгоритмы построения трех типов  таких квадратов:

- квадрат  с нечетной стороной

- квадрат  с четной стороной

- дважды  четный квадрат

 

Нечетный квадрат

 

Метод диагоналей

 

Изначально  ставим единицу по центру в первой строке

. Дальше начинаем подряд заполнять  диагонали слева направо (сверху  вниз) учитывая следующие правила:

 

  1. Дойдя до верхнего края квадрата, следующую цифру ставить в следующем столбце в последней строке и продолжать уже с этого места.
  2. Дойдя до правого края квадрата следующую цифру ставить в начале предыдущей строки и продолжать с этого места
  3. Дойдя до угла или до какой-либо цифры, следующую цифру ставить под текущей и продолжать с этого места.

 

 

Псевдокод процедуры заполнения квадрата:

 

-изначальные координаты 

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 квадрата порядка 

Информация о работе Комбинаторные алгоритмы. Исследование решение задачи построения магических квадратов