Меня интересует алгоритм, который можно задать программно. Наверняка есть какая то формула по которой это можно вычислить. Вот моё задание. В верху готовый вариант, для обучения, ниже то что я сам сделал. Практически всё там заполняется программным путём, чтобы при смене варианта сразу всё пересчитывалось.

Подсказку мне дали в другом моём вопросе, чтобы сконцентрироваться на конкретном вопросе я создал новый.

"Крестики" можно заполнять по своему усмотрению, вписывая туда хоть 0, хоть 1. При этом все единицы (включая дописанные от себя вместо "крестиков") надо "упаковать" в возможно меньшее число прямоугольников из единиц. В Вашем примере их получилось четыре. Они также соответствуют произведениям, в которые могут входить уже не все члены. Скажем, прямоугольник, образованный пересечением строк 1,2 и столбцов 2,3 (два "крестика" там приняли за единицу) соответствует набору x1x4: он именно на пересечении этих "зон" и находится.

продолжение:

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

Если в моём варианте всё оказалось относительно просто (два объединения B31:C33 и D30:E32 поправьте, если ошибаюсь), то в учебном примере в объединения не включены две единицы.

задан 21 Мар '13 19:51

изменен 21 Мар '13 19:54

10|600 символов нужно символов осталось
1

Ожидать здесь наличия какой-то просто устроенной формулы вряд ли можно. Лучше ставить вопрос о наличии алгоритма, который не слишком сложно программируется, и при этом выдаёт решение близкое к "оптимальному" в каком-то смысле. "Формулу" здесь можно считать частным случаем алгоритма, в котором участвуют только операторы присваивания и разного рода арифметические или логические выражения. Но в задачах такого типа требуются дополнительные средства. Когда несколько вариантов сравниваются на предмет того, какой из них лучше, то приходится использовать условные операторы и прочее.

Если надо "автоматизировать" процесс, то можно поступить так. Сначала алгоритм пытается подобрать самые простые выражения, состоящие из одной переменной или её отрицания. Проверка того, подходит или не подходит то или иное выражение, легко осуществляется автоматически: всякому выражению соответствует множество клеток, и при этом надо, чтобы оно не содержало нулей. Все "крестики", попавшие в рассматриваемую область, считаются равными единице. Скажем, в Вашем задании такой алгоритм сразу же обнаружит подходящее выражение $%x_2$%. И далее останутся всего две единицы, которые нужно куда-то поместить. Алгоритм начинает перебирать произведения двух переменных, каждая из которых может быть с чертой или без. При этом он найдёт выражение $%x_3\bar{x_4}$%, в которое входит единица из нижней строчки. А единица из верхней строчки войдёт в $%\bar{x_3}x_4$%. Выражение получилось весьма простое: дизъюнкция трёх названных членов. В общем случае алгоритм далее будет просматривать тройные произведения, если единицы остались, а в каком-то случае может дойти и до произведений четырёх букв. Например, если есть единица, окружённая нулями: тогда её сгруппировать уже не с чем.

Надо заметить, что выражениям могут соответствовать и не совсем прямоугольники: скажем, выражению $%\bar{x_2}x_3$% (которое здесь не подходит, но я просто для примера рассматриваю) соответствует группа из четырёх клеток, которая становится прямоугольником только после "склейки" верха и низа, но это совершенно не важно для алгоритма.

Если говорить чисто о прямоугольниках, то все единицы из Вашего задания помещаются в два прямоугольника размером $%3\times2$%, но их за основу брать не надо, так как по столбцам там всё хорошо, но строки при этом "неоднородны", и никакое произведение этим фигурам не соответствует. Исходя из этого, можно понять, какого типа фигуры здесь должны возникать. Но это только для "ручного" счёта, а алгоритму оно не требуется.

В учебном примере все единицы куда-то включены: там имеется два квадрата $%2\times2$%, одна серая полоска во второй строчке, и тёмно-серый прямоугольник внизу размером $%1\times2$%.

ссылка

отвечен 22 Мар '13 1:43

попробую всё это переварить со временем... пока пропущу этот шаг из автоматизации вычисления

(22 Мар '13 15:16) shaman888
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×263

задан
21 Мар '13 19:51

показан
1284 раза

обновлен
22 Мар '13 15:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru