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

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

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

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

Содержание

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

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

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

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

m. В первом квадрате выделим клетки в виде шахматного поля, таким образом:

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


 

Также отметим  клетки, симметричные этим, относительно вертикальной оси.

 

 

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


 

Теперь  выделенные элементы меняем с элементами, симметричными им относительно центра. Получается такой магический квадрат:

 

1

63

3

61

60

6

58

8

56

10

54

12

13

51

15

49

17

47

19

45

44

22

42

24

40

26

38

28

29

35

31

33

32

34

30

36

37

27

39

25

41

23

43

21

20

46

18

48

16

50

14

52

53

11

55

9

57

7

59

5

4

62

2

64


 

Псевдокод:

j=2

m=порядок

 малого квадрата (N/2)

for

(для всех элементов  малого квадрата(i)) {

for

(для всех m/2) {

-Корректируем координаты  при смене строки

if

(j==m+1) j=2

else

 if(j==m+2) j=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

j=2;

int

m=N / 2;

 

for (int i=1; i<= m; i++) {

for

(int k=1; k<=m / 2 ; k++) {

 

if (j==m+1) j=2;

 

else if (j==m+2)  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=j+2;

 

}

 

Результат:

 

 

 

 

 

Диагональный метод

Изначально  разобьем основной квадрат на малые  с порядком 4. И в каждом из малых  квадратов пометим диагонали.

+

   

+

+

   

+

 

+

+

   

+

+

 
 

+

+

   

+

+

 

+

   

+

+

   

+

+

   

+

+

   

+

 

+

+

   

+

+

 
 

+

     

+

+

 

+

   

+

+

   

+


 

Дальше  начнем заносить числа в квадрат  в их естественном порядке, но будем 

пропускать те числа, на месте которых стоит знак +.

+

2

3

+

+

6

7

+

9

+

+

12

13

+

+

16

17

+

+

20

21

+

+

24

+

26

27

+

+

30

31

+

+

34

35

+

+

38

39

+

41

+

+

44

45

+

+

48

49

+

+

52

53

+

+

56

+

58

59

+

+

62

63

+


 

Теперь  начинам вписывать в квадрат  не вошедшие в него числа в направлении  снизу вверх, справа налево (с нижней правой клетки).

 

 

 

 

64

2

3

61

60

6

7

57

9

55

54

12

13

51

50

16

17

47

46

20

21

43

42

24

40

26

27

37

36

30

31

33

32

34

35

29

28

38

39

25

41

23

22

44

45

19

18

48

49

15

14

52

53

11

10

56

8

58

59

5

4

62

63

1


 

Это уже  готовый магический квадрат 8-го порядка.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

  1. Google.ru  -поисковая система
  2. Cyberforum.ru – форум программистов
  3. Окулов С.М. Программирование в алгоритмах
  4. Постников М.М. Магические квадраты

 

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