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

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. Постников М.М. Магические квадраты