Подкинули мне тут задачку, да вот не знаю, как решить.
Есть матрица 4х4 заполненная 0 и 1. Надо выделить в ней прямоугольники, состоящие из 1, причем:
0. Помимо всего прочего соседними считаются первая и последняя строки и первый и последний столбей (короче, карта Карно)
1. Площадь прямоугольников должна равняться степени 2 (вариант когда есть 16 единиц исключен)
2. Каждая единица может покрываться несколько раз
3. Прямоугольник, покрывающий данную 1, должен быть наибольшего размераь (естественно не должно быть найдено 2 и более
абсолютно одинаковых прямоугольника). Но есть исключение: когда рядом с 1, которая может быть объединена в большой
прямоугольник, есть сосед, который может быть объединен только с ней.
Пример:
~y ~y y y
x 1 1 0 1 u
x 1 1 0 1 ~u
~x 1 0 1 1 ~u
~x 1 1 0 0 u
~z z z ~z
> Подкинули мне тут задачку, да вот не знаю, как решить. >
Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!!
Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!
P. S. Для меньшего гемороя с выводом минимизированной функции в виде текста я не стал сильно париться и сделал весь вывод в Unicod'е с использованием Arial Unicode MS (идёт вместе с офисом)!!!
Posted via RSDN NNTP Server 1.9 delta
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Кодт, Вы писали:
К>>В этой карте — очевидно, лучше строить не ДНФ, а КНФ: (~x|y|u)^(x|y|z)^(~x|~y|z|~u)
К>Пардон, забыл проинвертировать : (x|~y|~u)^(~x|~y|~z)^(x|y|~z|u)
Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...
Здравствуйте, Stanky, Вы писали:
>> Подкинули мне тут задачку, да вот не знаю, как решить. >> S>Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!! S>Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!
Хочу: .
S>P. S. Для меньшего гемороя с выводом минимизированной функции в виде текста я не стал сильно париться и сделал весь вывод в Unicod'е с использованием Arial Unicode MS (идёт вместе с офисом)!!!
Странно, у меня отображаются только иксы и квадратики...
Здравствуйте, Reunion, Вы писали:
R>Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...
Скорее, наоборот. Но я бы вот так обобщать не стал...
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, Reunion, Вы писали:
R>>Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...
К>Скорее, наоборот.
Ну да, я тоже забыл синвертировать...
К>Но я бы вот так обобщать не стал...
Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается
> А офис стоит!!! Ладно, это не важно. >
Чтоб этот шрифт поставился нужно при установке "Общие средства Office->Многоязыковая поддержка->Выбрать все пункты"!!!
Posted via RSDN NNTP Server 1.9 delta
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Reunion, Вы писали:
К>>Но я бы вот так обобщать не стал...
R>Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается
Здравствуйте, Кодт, Вы писали:
К>>>Но я бы вот так обобщать не стал...
R>>Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается
К>
К>Пример того, как количество единиц/нулей не согласовано с размером форм.
К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ Ее я уже почти получил — осталось выкинуть лишние слагаемые, которые возникают при определенном раскладе. Хотя, просто так, ради интереса можно посидеть дальше, что-то мне эта задача (полной минимизации) понравилась
Здравствуйте, Stanky, Вы писали:
>> А офис стоит!!! Ладно, это не важно. >> S>Чтоб этот шрифт поставился нужно при установке "Общие средства Office->Многоязыковая поддержка->Выбрать все пункты"!!!
Спаси,о за исходник — он меня на умные идеи навел...
> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ > Ее я уже почти получил — осталось выкинуть лишние слагаемые, > которые возникают при определенном раскладе. Хотя, просто так, ради > интереса можно посидеть дальше, что-то мне эта задача (полной > минимизации) понравилась >
Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!
Posted via RSDN NNTP Server 1.9 delta
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!
Здравствуйте, Stanky, Вы писали:
>> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ >> Ее я уже почти получил — осталось выкинуть лишние слагаемые, >> которые возникают при определенном раскладе. Хотя, просто так, ради >> интереса можно посидеть дальше, что-то мне эта задача (полной >> минимизации) понравилась >> S>Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!
Да, есть... Есть еще метод импликантных таблиц и алгоритм Петрика, а еще метод максимальных граней единичного n-мерного куба (где n — число переменных функции)...
Но ура, я полностью сделал задачу через карту Карно (как и просили) — так что еще раз всем спасибо!
Здравствуйте, Stanky, Вы писали:
>> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ >> Ее я уже почти получил — осталось выкинуть лишние слагаемые, >> которые возникают при определенном раскладе. Хотя, просто так, ради >> интереса можно посидеть дальше, что-то мне эта задача (полной >> минимизации) понравилась >> S>Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!
Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.
Здравствуйте, Dr.Gigabit, Вы писали:
DG>Здравствуйте, Reunion, Вы писали:
R>>Но ура, я полностью сделал задачу через карту Карно (как и просили) — так что еще раз всем спасибо!
DG>И каков же вариант решения? Перебор?
Сначала находим все подходящие прямоугольники для каждой ячейки. Затем сортируем их по убыванию размера. А потом выкидываем ненужные. Алгоритм не самый быстрый, но: во-первых на мой взгляд это не тот случай, когда надо оптимизировать (карта Карно обычно небольшая, в моем случае — вообще 4х4, да и на более больших работает в момент), а во-вторых это просто реализовать. Получается 100% результат для минимальной ДНФ. В принципе, я думаю, можно найти еще минимальную RYA и определить, что лучше. Вот такой вот алгоритм.
> Сначала находим все подходящие прямоугольники для каждой ячейки. Затем > сортируем их по убыванию размера. А потом выкидываем ненужные. Алгоритм > не самый быстрый, но: во-первых на мой взгляд это не тот случай, когда > надо оптимизировать (карта Карно обычно небольшая, в моем случае - > вообще 4х4, да и на более больших работает в момент), а во-вторых это > просто реализовать. Получается 100% результат для минимальной ДНФ. В > принципе, я думаю, можно найти еще минимальную RYA и определить, что > лучше. Вот такой вот алгоритм. >
А недетерминированные функции учитываешь?
Posted via RSDN NNTP Server 1.9 delta
Не бойся выглядеть глупо, от этого ты выглядишь ещё глупей!!!