2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Задача возникла при построении примитивных квадратов.
В процессе решения получается прямоугольник размерами 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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:25 
Заблокирован
Аватара пользователя


17/06/09

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:28 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:47 
Заслуженный участник


27/04/09
28128
age в сообщении #364071 писал(а):
Это задача наподобие закраски произвольной области на компьютере: ноль - красить можно, единица - нельзя (найдена линия). Выходит, вам нужно определить, можно ли "закрасить" квадрат 13 х 13.
Это разве как-то облегчает решение?

Если я правильно понял задачу, (самый плохой) алгоритм таков:
Код:
цикл по всем квадратам прямоугольника
// можно по координатам левого верхнего угла, два вложенных цикла
  цикл по всем клеткам квадрата
  // аналогично по координатам точки, итого 4 вложенных цикла
    если в клетке 1, вернуть квадрат
    // всё, вышли насовсем
вернуть пусто // раз сюда попали, значит, нет ни одного квадрата
Да?

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:55 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 20:59 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 21:00 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 21:01 
Заблокирован
Аватара пользователя


22/03/08

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

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 21:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 21:09 
Заблокирован
Аватара пользователя


22/03/08

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение20.10.2010, 21:26 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Nataly-Mak в сообщении #364097 писал(а):
Да, массивы небольшие.А вот проверить быстро не очень получается.

Не знаю, как у вас получается его проверить не быстро. Даже на моём древнем домашнем компьютере (селерон 800 Мгц) с переборным "в лоб" алгоритмом при реализации на Ruby (некомпилируемый язык) программа работает 27 мс.
Код:
$ time ./nataly13.rb
real    0m0.027s
user    0m0.020s
sys     0m0.008s

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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение21.10.2010, 04:53 
Заблокирован
Аватара пользователя


22/03/08

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

Сначала подумала, что это означает проверить вручную.
У меня как раз и вопрос о том, как написать программу проверки. Вручную я уже несколько десятков прямоугольников проверила, кстати, нашла таким методом примитивные квадраты 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 чисел не являются простыми. Два столбца из единиц полных удалось добавить, остальные содержат нули.

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение21.10.2010, 07:53 


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

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение21.10.2010, 08:08 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ох, не считала варианты :-)

Проверила ещё около 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 из простых чисел. Непростая задачка!
За подробностями приходите по указанной выше ссылке.

 Профиль  
                  
 
 Re: Интересная задачка: как автоматизировать выборку
Сообщение21.10.2010, 17:03 
Заслуженный участник


27/04/09
28128
Nataly-Mak в сообщении #364106 писал(а):
Реализовать можете свой улучшенный алгоритм?
Пока нет времени. :-) Но раз и «неулучшенный» так быстро работает, то мой и не сильно нужен.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 35 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group