Поскольку БФ представлена в виде ДНФ, то функция равна 1, если хотя бы одна конъюнкция равна 1 (все переменные рассматриваемой конъюнкцией равны 1); функция равна 0, если все конъюнкции равны 0 ( хотя бы одна переменная в каждой конъюнкции равна 0).
Тогда процедура построения бинарной программы состоит в том, чтобы, используя команды условного перехода, последовательно проверить все конъюнкции БФ на равенство 1 или 0, руководствуясь при этом следующими обстоятельствами.
Если значение проверяемой конъюнкции при данном значении переменной равно 0, то делается переход для проверки следующей переменной данной конъюнкции: если при этом проверяемая переменная в данной конъюнкции последняя, то БФ присваивается значение 1.
Если значение конъюнкции при данном значении входной переменной равно 0, то делается переход на проверку следующей конъюнкции; если проверяемая конъюнкция является последней, то БФ присваивается значение 0.
Число команд в бинарной программе, построенной по правилам, рассмотренным выше, равно сумме переменных всех конъюнкций плюс две команды присвоения БФ значения 1 и 0.
Бинарная программа для рассматриваемой функции с использованием команд условного перехода имеет вид:
1: Если X1, то 6, иначе 2
2: Если X2, то 3, иначе 6
3: Если X3, то 6, иначе 4
4: Если X4, то 5, иначе 6
5: Если X5, то 6, иначе 16
6: Если X6, то 7, иначе 11
7: Если X7, то 11, иначе 8
8: Если X8, то 9, иначе 11
9: Если X9, то 11, иначе 10
10: Если X10, то 16, иначе 11
11: Если X11, то 17, иначе 12
12: Если X12, то 13, иначе 17
13: Если X13, то 17, иначе 14
14: Если X14, то 15, иначе 17
15: Если X15, то 17, иначе 16
16: f=1
17: f=0
Приведенный пример содержит минимальное число команд условного перехода.
Рассмотрим случай, когда БФ задана скобочной формой:
Приведем данную функцию к виду ДНФ, тогда:
Бинарная программа для этой БФ будет иметь следующий вид:
1: Если X1, то 4, иначе 2
2: Если X2, то 4, иначе 3
3: Если X4, то 7, иначе 4
4: Если X2, то 6, иначе 5
5: Если X3, то 6, иначе 7
6: f=0
7: f=1
Рассмотренный пример содержит не минимальное число команд условного перехода. Если рассматриваемую функцию представит в виде:
то можно построить программу следующего Вида:
1: Если X2, то 5, иначе 2
2: Если X1, то 4, иначе 3
3: Если X4, то 6, иначе 4
4: Если X3, то 5, иначе 6
5: f=0
6: f=1
Предложенный вариант программы содержиn на одну команду условного перехода меньше, чем предыдущий вариант. В общем случае, когда речь идет о минимальности бинарных программ, возникает задача представления БФ в специальной форме, удобной для бинарных программ. Эта задача выходит за рамки данной работы и в дальнейшем не рассматривается.
На рис.4 приведена другая форма записи алгоритма бинарной программы - блок-схема алгоритма для функции:
Программа СР 2, показанная па рис. 5, построена по блок-схеме рис. 4.
Команды 1,2
|
Команда 3
Команда 4
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.