2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Начало алгоритма Блейка
Сообщение24.04.2014, 16:26 


04/05/13
125
Задача: Во входном файле задана ДНФ. Найти ДНФ, получающуюся из нее применением всех возможных операций обобщенного склеивания (начало алгоритма Блейка). В выходном файле строки, соответствующие ЭК, должны быть упорядочены лексикографически.

ДНФ функции от n переменных задается так: сначала записано n, потом m – число элементарных конъюнкций (далее ЭК), потом m строк, соответствующих конъюнкциям. Каждая ЭК задается строкой длины n без пробелов, где на i-м месте стоит 1, если i-я переменная входит в ЭК без отрицания, 0, если она входит с отрицанием, и *, если она в ЭК не входит. Например, ДНФ функции от 3-х переменных $x_1 \ x_3^- V x_2^- x_3$ задается так:
3 2
1*0
*01

(Оффтоп)

подскажите пожалуйста как ставить отрицание и дизъюнкцию


Насколько я понял, обобщенное склеивание выглядит примерно так: $A^- B V A C = A^- B V A C V B C$.
Для хранения ДНФ я использую структуру, можно сказать, двумерный массив. Каждая строка соответсвует ЭК. Звездочки я заменяю на $-1$.
Если я сделаю следующее: возьму первый элемент(естественно если он равен 1 или 0) первой строки(буду обозначать его $a_{11}$) и буду смотреть только первые элементы всех последующих строк и, если какой-то из них неравен $a_{11}$(и неравен -1), по операции обобщенного склеивания буду добавлять соответствующие ЭК в конец массива; дальше беру второй элемент первой строки и делаю то же самое, и так далее пока не закончится строка.
Потом "наведу" лексикографический порядок в массиве строк.
Будет ли это означать, что я нашел правильный ответ?

PS пишу я на си

 Профиль  
                  
 
 Re: Начало алгоритма Блейка
Сообщение24.04.2014, 18:18 


04/05/13
125
Мне кажется этот раздел форума никто не просматривает кроме модераторов...

(Оффтоп)

нашел как исправить формулы, но не знаю где тут кнопка "править" или что-то в этом роде. под моим первым сообщением есть только кнопки "цитата" и "вставка"

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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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