Перейти к содержанию

Реализации алгоритмов/Построение магических квадратов

Добавить ссылки
Материал из Викиучебника — открытых книг для открытого мира

Реализация на языке программирования PHP

[править]

Метод террас (квадраты нечётного порядка)

[править]
<?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
Источник — https://ru.wikibooks.org/w/index.php?title=Реализации_алгоритмов/Построение_магических_квадратов&oldid=234453