Меня интересует алгоритм, который можно задать программно. Наверняка есть какая то формула по которой это можно вычислить. Вот моё задание. В верху готовый вариант, для обучения, ниже то что я сам сделал. Практически всё там заполняется программным путём, чтобы при смене варианта сразу всё пересчитывалось. Подсказку мне дали в другом моём вопросе, чтобы сконцентрироваться на конкретном вопросе я создал новый.
продолжение:
Если в моём варианте всё оказалось относительно просто (два объединения B31:C33 и D30:E32 поправьте, если ошибаюсь), то в учебном примере в объединения не включены две единицы. задан 21 Мар '13 19:51 shaman888 |
Ожидать здесь наличия какой-то просто устроенной формулы вряд ли можно. Лучше ставить вопрос о наличии алгоритма, который не слишком сложно программируется, и при этом выдаёт решение близкое к "оптимальному" в каком-то смысле. "Формулу" здесь можно считать частным случаем алгоритма, в котором участвуют только операторы присваивания и разного рода арифметические или логические выражения. Но в задачах такого типа требуются дополнительные средства. Когда несколько вариантов сравниваются на предмет того, какой из них лучше, то приходится использовать условные операторы и прочее. Если надо "автоматизировать" процесс, то можно поступить так. Сначала алгоритм пытается подобрать самые простые выражения, состоящие из одной переменной или её отрицания. Проверка того, подходит или не подходит то или иное выражение, легко осуществляется автоматически: всякому выражению соответствует множество клеток, и при этом надо, чтобы оно не содержало нулей. Все "крестики", попавшие в рассматриваемую область, считаются равными единице. Скажем, в Вашем задании такой алгоритм сразу же обнаружит подходящее выражение $%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 falcao попробую всё это переварить со временем... пока пропущу этот шаг из автоматизации вычисления
(22 Мар '13 15:16)
shaman888
|