11

Это сообщение отредактировал(а) fybvfpfybc - 26.6.2013, 14:55

Спасибо!))) Конечный результат давно понятен. Не понятны требования по преобразованию матрицы. 


Это понятное требование. Оно влечёт за собой представление матрицы в виде графов и т.п.
Можно было бы переставлять единички на свободные места так, чтобы выполнялось 5-условие.
Но ведь нет, заменяются единички нулями, нарушая баланс между числом нулей и единиц. Вероятность встречи единицы падает.


Это не понятное требование. Действительно, в матрице можно оставить одну единственную единичку, и такая матрица будет удовлетворять условиям:

• каждый комплекс из смежных ячеек-единиц содержит не больше пяти ячеек-единиц
• каждый комплекс окружён как минимум одной ячейкой-нулём так же со всех сторон
• отсутствует повторяющийся узор

Если не нравится перекос в сторону 0 (а вот почему не нравится?), то можно применить более щадящее решение, которое я привёл. "Не нравится" - это не критерий в постановке задачи   

Если же задача стоит в том, чтобы случайным образом сгенерировать узор из единичек, чтобы выполнялось 5-условие, то эта задача решается не так (то есть не генерируются абы где единицы, а потом убираются лишние).

Вот поэтому и возникают вопросы по формулировке задачи.

Это сообщение отредактировал(а) feodorv - 16.12.2012, 15:45

2Фантом: у меня всё-таки есть подозрение, что объяснения нормальным логичным языком менее действенны, чем тыканье мордой в ошыбки. То есть тем, кто обычно понимает логику, и случайно как-то сглючил и задал такой вопрос -- тем вообще неважно, они и так и так поймут. У остальных шанс начать думать после получения грязи в физиономию (ну, чисто из-за разрыва шаблона), на мой взгляд, несколько большэ. Хотя и невелик, конечно.

Между прочим, эта матрица не удовлетворяет первоначальным требованиям (хотя 5-условие соблюдается).

11

Это сообщение отредактировал(а) fybvfpfybc - 26.6.2013, 14:55

Это как раз первое, что случилось в этом обсуждении. Тоже не помогло.

11

Это сообщение отредактировал(а) fybvfpfybc - 26.6.2013, 14:56

Я понял, что матрица большая. Кстати, какого размера?
Нет, не про частоту единиц, а про то, что единицы касаются граней матрицы, а по условию 

То есть эти единицы окружены нулями не со всех сторон   

А вот первый пример матрицы:

целиком и полностью удовлетворяет этому условию  



Я вижу решение этой задачи так:

• У матрицы, уже находящейся в каком-то 0-1-состоянии, есть поле (набор элементов), куда можно добавлять единицу, не нарушая условие задачи. Это поле сужается (по крайней мере, не расширяется))) с добавлением каждой единицы, в конце концов это поле истощается, более ни одной единицы добавить не удастся. Назовём элементы матрицы, входящие в это поле, свободными элементами.
• Соответственно, перед каждым шагом (добавлением единицы) вычисляется число свободных элементов. Тогда случайную позицию (в этом поле) добавляемой единицы можно вычислить как random() % N, где N - число свободных элементов. В самом начале, когда матрица чисто нулевая, N равно M*M за минусом граничных элементов. 
• Согласно полученной позиции в поле вычисляется положение добавляемой единицы в матрице (строка, столбец). Это не тривиально, и если матрица не сильно большая, то это можно решить линейным массивом с M*M элементов (где M - размер матрицы), заполняемым на предыдущем этапе при подсчёте числа свободных элементов. Если матрица - большая, то положение добавляемой единицы в матрице можно определить перебором свободных элементов.

Решение получается громоздким, но зато честно-случайным (или псевдо-случайным в зависимости от генератора "случайных" чисел). Если же следовать Вашим путём (тоже вариант), то честность случайности нарушается, возможны повторяющиеся узоры, уменьшается число единиц, короче говоря, сплошные минусы))))


Это сообщение отредактировал(а) feodorv - 16.12.2012, 18:20

Для простоты реализации алгоритма, я бы ввёл для элемента матрицы (помимо 0 и 1) ещё одно значение, скажем -1, которое будет означать, что данный элемент - свободный. При добавлении единицы в матрицу (как раз на место -1) на свободность нужно будет проверить только прилегающие к этой ячейке элементы 

Добавлено @ 18:38
Если в прилегающей ячейке 0 или 1 - то это значение остаётся. Если же -1, то ячейка проверяется на свободность (а можно ли будет в будущем в неё поместить единицу; если нет, тогда помещаем в эту ячейку 0 - это не 1, и в тоже время не свободная ячейка).

Добавлено @ 18:46

Не, не прав. Если образуется комплекс из 5 единиц, то все -1 вокруг него нужно заменить нулями...

Это сообщение отредактировал(а) feodorv - 16.12.2012, 18:47

11

Это сообщение отредактировал(а) fybvfpfybc - 26.6.2013, 14:56

Число "-1"-элементов (тупо просмотром всех элементов матрицы, и если в ячейке находится -1, то N++).

Добавлено через 3 минуты и 8 секунд
Либо так: 

• в начале Nfree = M*N;
• на каждом шаге: если заменяется ячейка со значением "-1" (на 0 или 1), то Nfree--;

Добавлено через 7 минут и 8 секунд
Тут сложности такие:

• при добавлении 1 понять, образовался ли комплекс из 5 единиц
• проверить, что ячейка - свободная

Добавлено через 8 минут и 21 секунду

Ага. Но если бы там была бы единица, то это был бы уже 6-комплекс   

11

Это сообщение отредактировал(а) fybvfpfybc - 26.6.2013, 14:56

Это видимо узоры для вязания носков, свитеров и т.д.
Вы напрасно на девушку с логикой наехали.

Надо просто расставить единицы красиво, и не так часто, имхо.   

Это сообщение отредактировал(а) volatile - 16.12.2012, 19:30

В принципе, это легко можно сделать той же рекурсией с ведением списка пройденных ячеек комплекса единиц (заодно можно будет узнать число ячеек, входящих в комплекс единиц). То есть для каждой ячейки комплекса (начиная с той, в которой -1 заменили на 1) делаем:

• если ячейка в списке, пропускаем её
• добавляем ячейку в список
• для этой ячейки смотрим прилегающие 8 ячеек. Если в какой-то из них 1, то рекурсивно проверяем и её.

Если число ячеек в списке есть 5, тогда нужна аналогичная рекурсия, но при этом ещё поменять "-1" на "0" во всех ячейках, прилегающих к единичным ячейкам комплекса.
Если меньше, то нужно проверить окружающие (нашу ячейку, в которой "-1" заменили на "0") ячейки со значением "-1" на свободность (ибо их свободность могла измениться). Это делается рекурсией аналогично, только

• временно меняем в этой ячейке "-1" на "1"
• проводим аналогичную рекурсию, только учитываем, что число ячеек в комплексе единиц может превысить 5 (это когда эта "1" внезапно объединила два комплекса единиц); если в процессе рекурсии обнаружится этот факт, то в начальную ячейку (в которой "-1" временно заменили "1") нужно поместить 0 (эта ячейка не свободна), а рекурсию можно прекратить
• если ячейка свободная, то возвращаем ей значение "-1"

Вам всё равно придётся проверять (прилегающие) ячейки со значением "-1" на свободность при добавлении новой единицы (эти ячейки уже могут стать несвободными). 

Вот набросал приблизительный код на C:

Ничего так, симпатичные матрицы получаются: