Здравствуйте, Hard_Club, Вы писали:
H_C>магических квадратов заданного размера
Пусть размер стороны задан и равен k (а всего в квадрате тогда получается k² элементов).
H_C>Как бы вы решали задачи пойска магических квадратов заданного размера в болошоми массиве n * m.
А квадраты и матрицы большие? Если нет, то наивным перебором (как уже предложено тут
Если нужно быстрее, то можно так:
Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них.
Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них.
Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.
Ну и при желании на последний шаг можно навешать различных эвристик. Например, сдвигать скользящее окно не на одну строку/столбец за раз, а сразу на много, действуя подобно тому, как алгоритм Бойера–Мура обрабатывает стоп-символы. При хорошем распределении это позволит сразу прыгать на много шагов вперёд, при плохом — особо ничего не изменит. Собственно, таких дешёвых эвристик можно ещё несколько добавить для достижения синергетического эффекта (в среднем случае).
Пару вопросов о сложности:
W>Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них.
Это не O(mnk)?
W>Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них. W>Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.
А это не O(mnk²)?
Здравствуйте, VladFein, Вы писали:
VF>Пару вопросов о сложности:
W>>за время O(mn) VF>Это не O(mnk)?
W>> Это всё займёт время O(mnk) VF>А это не O(mnk²)?
По определению при n→+∞ любая функция из класса O(n) будет также находится в классах функций O(n^2), O(n^3), O(n!) и даже в O(nn!)
W>Если нужно быстрее, то можно так: W>Тогда первым проходом за время O(mn) находятся точки, начиная с которых идут непрерывные строки, столбцы или диагонали длины k и с суммой k(k²+1)/2 вдоль них. W>Вторым проходом за то же время O(mn) эти точки группируются и определяется то же условие, но с заменой 'или' на 'и'. Полученные точки — это кандидаты в квадраты — любой магический квадрат начинается только в них. W>Теперь осталось лишь проверить, что в каждом таком квадрате выполняется не только ограничение на сумму, но и на уникальность чисел. Если кандидатов мало, то можно проверить их всех непосредственно. Если много, то просто пускается по матрице sliding window размера k×k и в нём отслеживается соблюдение инварианта. Это всё займёт время O(mnk), что и определит общую сложность алгоритма.
Как Вы так быстро догадались? Упражняетесь в аглоритмах?
А стоит ли делать некий кеш из посчитанных сум подстрок и подстолбцов равных k(k^2 + 1)/2, чтобы если мы расчитали один квадрат — квадрат чуть смещенный вниз не надо было полностью пересчитывать?
Здравствуйте, Hard_Club, Вы писали:
H_C> чтобы если мы расчитали один квадрат — квадрат чуть смещенный вниз не надо было полностью пересчитывать?
Так и работает скользящее окно.
Здравствуйте, Hard_Club, Вы писали:
H_C>вот что получилось
У меня есть ещё одно "наивное" предложение: после провалившихся проверок строк или колонок на MAGIC_SUM не просто продолжать по continue, а пометить точки (MAGIC_SQUARE_DIMENSION-1) во все стороны (вверх/вниз для строк или влево/вправо для колонок) как НЕ кандидаты (или во внешнем bool массиве, или флагом в старшем бите, если размерность позволяет).
P.S. Долго думал, стеснялся и сомневался — предлагать или нет? Как бы не засмеяли...