Интересная задачка: как автоматизировать выборку

[Nataly-Mak]

Задача возникла при построении примитивных квадратов.
В процессе решения получается прямоугольник размерами mxn, например, такой - 17х38:

1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  0  1  1  1  1  1  1  0  1  1  0  0  0  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  1  0  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  0  1  1  1  1  1  1  0  0  0  0  0  0  1  0 
 1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  1  1 
 1  0  1  1  1  1  1  1  1  1  0  1  1  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  1 
 1  1  1  1  1  1  1  1  1  1  0  1  0  1  1  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  0  1  1  1  1  1  1  0  1  1  1  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  0  0  0  0  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  1  1  1  1  1  1  1  0  0  1  1  0  0  0  0 
 1  0  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  1  0  1  1  1  1  1  1  0  1  0  1  0  1  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  1  0  0  1  1 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  1  1  1  1  1  1  1  1  1  1  0  0  0  0  0 
 1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
 1  0  0  1  1  1  1  1  1  0  1  0  0  0  1  1  0 
 1  0  1  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  0  0  0  1  1 
 1  0  1  1  1  1  1  1  1  1  0  1  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  1  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  1  1  0 
 1  0  0  1  1  1  1  1  1  1  1  0  0  1  0  0  0 
 1  1  0  1  1  1  1  1  1  0  1  0  0  0  0  1  0 
 1  0  0  1  1  1  1  1  1  1  0  0  1  0  0  0  1 
 1  0  0  1  1  1  1  1  1  1  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  1  0  0  0  0  1  0  0 
 1  0  0  1  1  1  1  1  1  0  0  1  0  0  1  0  0 
 1  1  0  1  1  1  1  1  1  1  0  1  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  0  0  0  0  0  0 
 1  1  0  1  1  1  1  1  1  0  0  1  0  0  0  0  0

Единички соответствуют простым числам, о нули - составным. Но это не так важно, чему они соответствуют.

Требуется определить, можно ли из этого прямоугольника "выкроить" квадрат 13х13, состоящий из одних единичек.
Понятно, что нужна программная реализация процедуры. Как это делать вручную, я знаю. Но вручную очень долго получается, а прямоугольников много надо проверить. Мне кажется, должно быть какое-то простое решение этой задачи.

Подробнее о задаче можно посмотреть здесь:
post364056.html#p364056

[age]

Nataly-Mak
Это задача наподобие закраски произвольной области на компьютере: ноль - красить можно, единица - нельзя (найдена линия). Выходит, вам нужно определить, можно ли "закрасить" квадрат 13 х 13.

[Nataly-Mak]

Ну да, выходит, что так
А как это определить, ну чтобы это компьютер делал, то есть "красил" и выдавал закрашенный квадрат.

[arseniiv]

age в сообщении #364071 писал(а):

Это задача наподобие закраски произвольной области на компьютере: ноль - красить можно, единица - нельзя (найдена линия). Выходит, вам нужно определить, можно ли "закрасить" квадрат 13 х 13.

Это разве как-то облегчает решение?

Если я правильно понял задачу, (самый плохой) алгоритм таков:

цикл по всем квадратам прямоугольника
// можно по координатам левого верхнего угла, два вложенных цикла
  цикл по всем клеткам квадрата
  // аналогично по координатам точки, итого 4 вложенных цикла
    если в клетке 1, вернуть квадрат
    // всё, вышли насовсем
вернуть пусто // раз сюда попали, значит, нет ни одного квадрата

Да?

Алгоритм получше будет смотреть на все нули и помечать строки и столбцы, в которых они находятся. Потом будет искаться "непрерывная" последовательность непомеченных строк из 13 штук и такая же из столбцов. Если такой (если уже для строк нет, столбцы можно не проверять) нет, то и квадрата нет.

[Nataly-Mak]

Вручную я действовала так. 8 строк у меня уже состоят из одних единиц (это "по построению"). Значит, мне нужно добрать 5 строк из 30. Дальше, у меня есть 6 "готовых" столбцов - тоже по построению. Значит, мне надо добрать 7 столбцов. Ну, дальше всё понятно: нахожу такие 7 столбцов, в которых стоят 5 единиц в одних и тех же позициях.

Ну, это вот "на пальцах" алгоритм. А программу написать ну никак не соображу.

[caxap]

Не такие уж и большие массивы, можно и в лоб проверить. Будет быстро.

[arseniiv]

А, знаичит, можно непримыкающие друг к другу строки и столбцы брать? Тогда да, кроме перебора ничего сразу в голову не идёт.

[Nataly-Mak]

Да, массивы небольшие.
А вот проверить быстро не очень получается.
Вы можете быстро сказать, из приведённого прямоугольника можно выделить квадрат 13х13 из единиц?

А мне таких прямоугольников надо сотни проверить.

[arseniiv]

Хотя нет, мой улучшенный алгоритм тоже подходит. Идём по всем клеткам прямоугольника и, встречая 0, помечаем строку и столбец его. В конце смотрим, осталось ли столько непомеченных строк и столбцов, сколько нам нужно.

[Nataly-Mak]

Реализовать можете свой улучшенный алгоритм?

[caxap]

Nataly-Mak в сообщении #364097 писал(а):

Да, массивы небольшие.А вот проверить быстро не очень получается.

Не знаю, как у вас получается его проверить не быстро. Даже на моём древнем домашнем компьютере (селерон 800 Мгц) с переборным "в лоб" алгоритмом при реализации на Ruby (некомпилируемый язык) программа работает 27 мс.

$ time ./nataly13.rb 
real    0m0.027s
user    0m0.020s
sys     0m0.008s

Т. е. и сотни и тысячи ваших матриц можно проверить достаточно быстро. Кстати, в приведённой матрице квадрата 13х13 из единичек нет.

[Nataly-Mak]

Извиняюсь, я не так поняла ваше выражение "проверить в лоб". Потом дошло, но не стала писать.

Сначала подумала, что это означает проверить вручную.
У меня как раз и вопрос о том, как написать программу проверки. Вручную я уже несколько десятков прямоугольников проверила, кстати, нашла таким методом примитивные квадраты 11х11 из простых чисел.
А вот найти квадрат 13х13 пока не удалось.
Ну, конечно, проверять надо "в лоб", а как же ещё. Но вот эту проверку и надо запрограммировать, а у меня что-то не идёт в голову, как это сделать. Ну, что-то мелькает: проверяем в каждом столбце единички, отмечаем, в каких они строках, потом находим количество совпадающих строк и количество столбцов, в которых они совпадают, то есть стоят в одних и тех же позициях. Это, собственно, алгоритм, который я изложила выше "на пальцах".
Понятно, что такой небольшой массив компьютер проверит за долю секунды.
По программе я получаю прямоугольник из нулей и единиц, у меня вообще-то строится прямоугольник из произвольных натуральных чисел, в котором несколько столбцов и несколько строк (заранее заданы) состоят только из простых чисел. Эта процедура мигом выполняется.

Жаль, что в приведённом прямоугольнике нет квадрата 13х13 из единиц. Вы уверены, что правильно проверили?
Казалось бы: из 30 строк надо добрать всего 5 строк (8 строк уже готовы по построению), но при этом в 7 столбцах единички должны стоять в одних и тех же строках. Значит, не получилось в этом прямоугольнике. Другой построю.

P. S. Сейчас заметила ссылку на программу. Посмотрю, спасибо.

-- Чт окт 21, 2010 06:03:09 --

Посмотрела программку. Но, к сожалению, язык этот не знаю.

У меня такой вопрос: вы, может быть, искали квадрат 13х13, подряд составленный из единичек? Такого здесь точно нет.
Можно брать строки и столбцы в любом месте, а ненужные строки и столбцы удалять.
Да, при ручной выборке я сразу удаляла готовые строки и столбцы, а потом уже добирала нужное количество строк и столбцов. В приведённом прямоугольнике, как я уже говорила, 8 строк и 6 столбцов готовы, то есть полностью состоят из единиц.

-- Чт окт 21, 2010 06:52:01 --

Да, правильно, в приведённом прямоугольнике нет квадрата 13х13 из единиц.
Вот результат ручной выборки:



Но уже где-то близко Фактически построен примитивный квадрат 13х13, в котором только 9 чисел не являются простыми. Два столбца из единиц полных удалось добавить, остальные содержат нули.

[Yu_K]

Это всего вариантов $C^{17}_{13}C^{38}_{13}$, так?

[Nataly-Mak]

Ох, не считала варианты

Проверила ещё около 10 прямоугольников вручную. Прямоугольники-то я строю моментально, а вот проверка тормозит работу.
Но уже удалось построить примитивный прямоугольник 9х14, полностью состоящий из простых чисел:

823  859  1237  5857  6793  7717  7753  7789  8713  9649  12241  17203  30931  36013 
 5003  5039  5417  10037  10973  11897  11933  11969  12893  13829  16421   21383  35111  40193 
 5623  5659  6037  10657  11593  12517  12553  12589  13513  14449  17041   22003  35731  40813 
 6793  6829  7207  11827  12763  13687  13723  13759  14683  15619  18211   23173  36901  41983 
 12343  12379  12757  17377  18313  19237  19273  19309  20233  21169  23761   28723  42451  47533 
 18973  19009  19387  24007  24943  25867  25903  25939  26863  27799  30391   35353  49081  54163 
 25603  25639  26017  30637  31573  32497  32533  32569  33493  34429  37021   41983  55711  60793 
 31153  31189  31567  36187  37123  38047  38083  38119  39043  39979  42571   47533  61261  66343 
 37123  37159  37537  42157  43093  44017  44053  44089  45013  45949  48541   53503  67231  72313

Один столбец лишний для квадрата 13х13, но зато 4 строки не хватает.

Может, кого-нибудь задача в полном объёме заинтересует: построение примитивного квадрата 13х13 из простых чисел. Непростая задачка!
За подробностями приходите по указанной выше ссылке.

[arseniiv]

Nataly-Mak в сообщении #364106 писал(а):

Реализовать можете свой улучшенный алгоритм?

Пока нет времени. Но раз и «неулучшенный» так быстро работает, то мой и не сильно нужен.