Магический квадрат
Магический квадрат
Магическим квадратом называют таблицу, в которой записаны числа 1,2,3,… по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечётной стороной (3×3,5×5,…).
Поставим число 1 в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа 2,3,4,…. Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с неё. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.
Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов 3×3 и 5×5 показаны на рисунках.
На вход подается одно натуральное нечётное число N, не превосходящее 30 — размер квадрата.
Выведите числа, записанные в квадрате. Выравнивать числа по столбцам не обязательно. Обратите внимание: требуется вывести именно магический квадрат, полученный применением указанного метода.
Вариантов решения у нас пока нет никаких. Помогите пожалуйста с решением.
Построение магического квадрата. Python.
Магическим квадратом порядка N называется квадратная матрица размера N × N , составленная из чисел 1, 2, . N 2 так, что суммы по каждому столбцу, каждой строке и каждой из двух больших диагоналей равны между собой. Напишите программу, которая строит магический квадрат заданного порядка N .
Входные данные
Входная строка содержит размер матрицы N ( 3 ≤ N ≤ 100 ).
Выходные данные
Программа должна вывести магический квадрат размера N × N .
Долго думал, как сделать, и что делать. И вот к чему я пришел:
Есть 3 вида алгоритмов для построения магического квадрата:
1) Для нечетного порядка
2) Для порядка двойной четности (например: 4, 8, 12, . )
3) Для четного порядка НЕ двойной четности (например: 6, 10, 14)
Само описание алгоритма довольно понятно расписано тут: https://ru.wikipedia.org/wiki/. 0%B0%D1%82.
Итак, код на Питоне (не пугайтесь размера, так надо )
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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
import math from sys import stdout LOG_10 = 2.302585092994 def build_oms(s): if s % 2 == 0: s += 1 q = [[0 for j in range(s)] for i in range(s)] p = 1 i = s // 2 j = 0 while p (s * s): q[i][j] = p ti = i + 1 if ti >= s: ti = 0 tj = j - 1 if tj 0: tj = s - 1 if q[ti][tj] != 0: ti = i tj = j + 1 i = ti j = tj p = p + 1 return q, s def build_sems(s): if s % 2 == 1: s += 1 while s % 4 == 0: s += 2 q = [[0 for j in range(s)] for i in range(s)] z = s // 2 b = z * z c = 2 * b d = 3 * b o = build_oms(z) for j in range(0, z): for i in range(0, z): a = o[0][i][j] q[i][j] = a q[i + z][j + z] = a + b q[i + z][j] = a + c q[i][j + z] = a + d lc = z // 2 rc = lc for j in range(0, z): for i in range(0, s): if i lc or i > s - rc or (i == lc and j == lc): if not (i == 0 and j == lc): t = q[i][j] q[i][j] = q[i][j + z] q[i][j + z] = t return q, s def format_sqr(s, l): for i in range(0, l - len(s)): pass return s + " " def display(q): s = q[1] k = 1 + math.floor(math.log(s * s) / LOG_10) for j in range(0, s): for i in range(0, s): stdout.write(format_sqr("".format(q[0][i][j]), k)) print() def ifNotEven(N): magic_square = [[0] * N for i in range(N)] n = 1 i, j = 0, N//2 while n N**2: magic_square[i][j] = n n += 1 newi, newj = (i-1) % N, (j+1)% N if magic_square[newi][newj]: i += 1 else: i, j = newi, newj for char in magic_square: print(*char) def DoublyEven(n): arr = [[(n*y)+x+1 for x in range(n)]for y in range(n)] for i in range(0,n//4): for j in range(0,n//4): arr[i][j] = (n*n + 1) - arr[i][j]; for i in range(0,n//4): for j in range(3 * (n//4),n): arr[i][j] = (n*n + 1) - arr[i][j]; for i in range(3 * (n//4),n): for j in range(0,n//4): arr[i][j] = (n*n + 1) - arr[i][j]; for i in range(3 * (n//4),n): for j in range(3 * (n//4),n): arr[i][j] = (n*n + 1) - arr[i][j]; for i in range(n//4,3 * (n//4)): for j in range(n//4,3 * (n//4)): arr[i][j] = (n*n + 1) - arr[i][j]; for char in arr: print(*char) N = int(input()) if N % 4 == 2: display(build_sems(N)) elif N % 2 == 1: ifNotEven(N) else: DoublyEven(N)
Тут все без комментариев — все есть на вики, но если будет непонятно — пишите, объясню, расскажу.
P.S. Функцию format_sqr(s, l) можно подстроить под то, чтобы все числа выводились с нулями вначале (например: 001, 002, 003, . )
Вставьте это на место функции в исходном коде! Удачи!
def format_sqr(s, l): for i in range(0, l - len(s)): s = "0" + s return s + " "
Магический квадрат
Python.Магическим квадратом называют таблицу, в которой записаны числа 1,2,3,… по одному разу, так что сумма чисел в каждой строке и в каждом столбце равные. Мы расскажем вам об одном из методов построения магических квадратов (его называют сиамским). Он годится только для построения квадратов с нечётной стороной (3×3,5×5,…).
Поставим число 1 в верхнюю клетку центрального столбца. Далее будем двигаться по диагонали вправо-вверх, расставляя в клетки последовательно числа 2,3,4,…. Если мы вышли за пределы таблицы вверх, то нужно перейти к нижней клетке того же столбца и продолжить с неё. Если мы вышли за правую границу, нужно перейти к левой клетке той строки, куда мы должны были попасть. Если же мы одновременно вышли и вверх, и вправо, то нужно перейти в левую нижнюю клетку квадрата.
Если в следующей клетке на нашем пути уже стоит число, то вместо хода “вправо-вверх” нужно сделать ход “вниз” (опять же, если мы при этом выйдем за границы квадрата, нужно перейти к верхней клетке того же столбца). Примеры для квадратов 3×3 и 5×5 показаны на рисунках.
На вход подается одно натуральное нечётное число N, не превосходящее 30 — размер квадрата.
Выведите числа, записанные в квадрате. Выравнивать числа по столбцам не обязательно. Обратите внимание: требуется вывести именно магический квадрат, полученный применением указанного метода.
Примеры
Ввод
Вывод
3
8 1 6
3 5 7
4 9 2
5
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
Уважаемые корифеи помогите разобраться.