Реализации алгоритмов/Построение магических квадратов
Метод террас (квадраты нечётного порядка)
править<?php
$n = 7; // Размерность (нечетное число)
$ms = create_magic_square($n);
echo '<table>';
for($i = 0; $i < $n; $i++) {
echo '<tr>';
for($j = 0; $j < $n; $j++)
echo '<td align="center"> '.$ms[$i][$j].' </td>';
echo "</tr>";
}
echo '</table>';
// функция отдаёт двумерный массив размерности NxN
function create_magic_square($N) {
$sol = array();
$ss = (($N-1)/2);
$nn = 1;
for($i=0; $i<$N; $i++)
for($j=0; $j<$N; $j++) {
$x = (-$ss+$i+$j+$N) % $N;
$y = ($ss+$i-$j+$N) % $N;
$sol[$x][$y] = $nn++;
}
return $sol;
}
?>
<?php
$n = 7; // Размерность (нечетное число)
// Генератор пробелов
function spaces($n) { $buf = ""; for($i = 0; $i < $n; $i++) $buf .= " "; return $buf; }
$ms = create_square_method_terraces($n);
$maxlen = strlen($ms[$n - 1][$n - 1]);
for($i = 0; $i < $n; $i++) {
for($j = 0; $j < $n; $j++)
echo $ms[$i][$j] . spaces($maxlen - strlen($ms[$i][$j]) + 2);
echo "<br><br>";
}
// функция отдаёт двумерный массив размерности NxN
function create_square_method_terraces($n) {
$square = array();
// создание ступенчатой симметричной фигуры
$num = 1;
$glob_i = round($n / 2);
$glob_j = 2 - $glob_i;
while ($num < ($n * $n)) {
$i = $glob_i;
$j = $glob_j;
while(($i + 1) != $glob_j) {
$square[$i][$j] = $num;
$num++;
$i--;
$j++;
}
$glob_i++;
$glob_j++;
}
// заполнение левой части квадрата, относительно
// левой диагонали (саму диагональ не трогаем)
$glob_i = 1;
$glob_j = $n;
while(($glob_i <= ($n - 1)) && ($glob_j >= 2)) {
for ($j = 1; $j <= $glob_j; $j++) {
if (!isset($square[$glob_i][$j])) {
if (isset($square[$glob_i + $n][$j])) {
$square[$glob_i][$j] = $square[$glob_i + $n][$j];
unset($square[$glob_i + $n][$j]);
} else {
$square[$glob_i][$j] = $square[$glob_i][$j + $n];
unset($square[$glob_i][$j + $n]);
}
}
}
$glob_i++;
$glob_j--;
}
// заполнение правой части квадрата, относительно
// левой диагонали (саму диагональ не трогаем)
$glob_j = $n - 2;
for ($i = $n; $i >= 2; $i--) {
for ($j = $n; $j >= ($n - $glob_j); $j--) {
if (!isset($square[$i][$j])) {
if (isset($square[$i - $n][$j])) {
$square[$i][$j] = $square[$i - $n][$j];
unset($square[$i - $n][$j]);
} else {
$square[$i][$j] = $square[$i][$j - $n];
unset($square[$i][$j - $n]);
}
}
}
$glob_j--;
}
foreach ($square AS $k => $v) {
if (sizeof($v) == 0) {
unset($square[$k]);
}
}
return $square;
}
?>
Проверка
править<?php
$n = 7; // Размерность (нечетное число)
$m = $n * ($n * $n + 1) / 2; // Магическая константа
// Получение магического квадрата в виде двумерного массива,
// например из функции, что находится выше
$chkarr = create_magic_square($n);
$isMS = is_magic_square($chkarr);
if($isMS == 1) die("Это <b>не магический</b> квадрат");
if($isMS == 2) die("Это <b>полумагический</b> квадрат <i>(магические только строки и столбцы)</i>");
if($isMS == 3) die("Это <b>диагональный магический</b> квадрат <i>(магические только диагонали)</i>");
if($isMS == 4) die("Это <b>магический</b> квадрат <i>(магические строки, столбцы, диагонали)</i>");
/*
Функция отдаёт число, обозначающее:
1 - не магический квадрат
2 - полумагический (только строки и столбцы)
3 - диагональный магический квадрат (только диагонали!)
4 - магический квадрат (строки, столбцы, диагонали)
*/
function is_magic_square($array) {
/*
Реализация: Веселов Денис.
*/
$mag = 2;
$left_diagonal = 0; // Идёт справа НА лево
$right_diagonal = 0; // Идёт слева НА право
for ($i = 1; $i <= $n; $i++) {
$row = 0; // ряд
$col = 0; // столбец
for ($j = 1; $j <= $n; $j++) {
$row += $array[$i][$j];
$col += $array[$j][$i];
$right_diagonal += ($i == $j) ? $array[$i][$j] : 0;
$left_diagonal += (($n - $i) == ($j - 1)) ? $array[$i][$j] : 0;
}
if (($row != $m) || ($col != $m))
$mag = 1;
}
if (($left_diagonal == $m) && ($right_diagonal == $m))
$mag += 2;
return $mag;
}
?>
Реализации на языке Python
правитьМетод террас (для нечетного порядка)
правитьsize = 5
square = [[0 for j in range(2 * size - 1)] for i in range(2 * size - 1)]
counter = 1
dj = 0
for i in range(size):
di = size - 1
for j in range(size):
square[i + di][j + dj] = counter
counter += 1
di -= 1
dj += 1
for j in range(size // 2):
for i in range(2 * size - 1):
square[i][j - (size // 2) * 2] = square[i][j] or square[i][j - (size // 2) * 2]
square[i][j] = 0
square[i][j + (size // 2)] = square[i][j - (size // 2)] or square[i][j + (size // 2)]
square[i][j - (size // 2)] = 0
square[j - (size // 2) * 2][i] = square[j][i] or square[j - (size // 2) * 2][i]
square[j][i] = 0
square[j + (size // 2)][i] = square[j - (size // 2)][i] or square[j + (size // 2)][i]
square[j - (size // 2)][i] = 0
square = [square[i][size // 2: 2 * size - 1 - size // 2] for i in range(size // 2, 2 * size - 1 - size // 2)]
for i in range(len(square)):
for j in range(len(square[i])):
print('%d\t' % square[i][j], end='')
print()
Метод квадратных решеток (для порядка двойной четности)
правитьsize = 12
square = [[0 for j in range(size)] for i in range(size + 2 * (size / 2 - 1))]
counter = 1
i0 = size / 2 - 1
for k in range(size / 4):
for j, i in enumerate(range(size / 2) + sorted(range(size / 2), reverse=True)):
square[i0 - i][j] = counter
counter += 1
for j, i in enumerate(range(size / 2) + sorted(range(size / 2), reverse=True)):
square[i0 + 1 + i][size - 1 - j] = counter
counter += 1
for j, i in enumerate(range(size / 2) + sorted(range(size / 2), reverse=True)):
square[i0 + 2 - i][size - 1 - j] = counter
counter += 1
for j, i in enumerate(range(size / 2) + sorted(range(size / 2), reverse=True)):
square[i0 + 3 + i][j] = counter
counter += 1
i0 += 4
for i in range(size / 2 - 1):
for j in range(size):
square[i - (size / 2) * 2 + 2][j] = square[i][j] or square[i - (size / 2) * 2 + 2][j]
square[i][j] = 0
square[i + (size / 2) - 1][j] = square[i - (size / 2) + 1][j] or square[i + (size / 2) - 1][j]
square[i - (size / 2) + 1][j] = 0
square = [square[i] for i in range(size / 2 - 1, size + size / 2 - 1)]
for i in range(len(square)):
for j in range(len(square[i])):
print '%d\t' %square[i][j],
print
Метод четырех квадратов (для четного порядка)
правитьsize = 14
square = [[0 for j in range(size)] for i in range(size)]
quarter_square = get_terrace(size / 2) # получаем методом террас
for n, ij0 in enumerate([(0, 0), (size / 2, size / 2), (0, size / 2), (size / 2, 0)]):
i0, j0 = ij0
for i in range(size / 2):
for j in range(size / 2):
square[i + i0][j + j0] = quarter_square[i][j] + n * (size / 2) ** 2
square[0][0], square[size / 2][0], square[size / 2 - 1][0], square[size - 1][0] = \
square[size / 2][0], square[0][0], square[size - 1][0], square[size / 2 - 1][0]
for i in range(1, size / 2 - 1):
square[i][1], square[i + size / 2][1] = square[i + size / 2][1], square[i][1]
if size > 6:
for j in range(size / 2 - (size / 2 - 3) / 2, size / 2 + (size / 2 - 3) / 2):
for i in range(size / 2):
square[i][j], square[size / 2 + i][j] = square[size / 2 + i][j], square[i][j]
for i in range(len(square)):
for j in range(len(square[i])):
print '%d\t' %square[i][j],
print