1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 48
Текст из файла (страница 48)
ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА (оператор «есле») к (условие) (безусловный оператор) (условныйоператор)к (оператор«если») ! (оператор«если») иначе (оператор) ) (условие) (оператор цикла )в) ~ (метка): (условный оператор) Если вспомнить,что среди основных операторов есть оператор перехода на М,то станет ясно, что синтаксис алгола 60 охватывает и другие способы указания плюс- и минус-направлений. Ниже следуют несколько фрагментов алгольских программ с логическими операторами, использующими вышеприведенные логические выражения в качестве условий: й) если (х «=' ,т) ос (х ) О) то у: х иначе йч=* (и (х); 2) если (Х у 2 + У (' 2 (~ 1)бс(Х >< У ) )О) то начало если Х~О то начало А: ° егерей(У1Х); на СЧЕТконец конец; ОШИБКА: вывод (Х, У) 8) если ) х,осх»лх» ~ х,вс ~х»бсхз ~/ хзбсх,бс ) х ~/ ~/ хфхтйхз то на ДА иначе на НЕТ ° В нашем изложении, так же как и в первой части, нам будет ;удобно изображать программы графически.
Поскольку передачи управления в графе переходов указываются дугами, ориентация которых указывается стрелками, естественно называть плюс-и минус-направления соответственно плюс- и минус-стрелками. При этом плюс-стрелка будет отличаться от минус-стрелки точкой у своего основания. На рис. 7.2 в графической форме повторены примеры логических операторов. Задача о голосовании. После повторительной главы по математической логике нам естественно сосредоточиться на примере «машины голосования». С одной стороны, в его условии стоит довольно громоздкое выражение, с другой стороны, реализовать его вычисление ничего не стоит: нужно только набраться терпейия и запрограммировать совершенную нормальную форму: гд.
) х,; ~г;. г,йх.,; г;.= г»йхз; г,: ~хз; г,: г,ах»; 1'1 . 'гх б~ х»', гт: гз ~/ гБ з) Для чвтателя будет неплохой задачей додуматься, почему авторы ал тола бс ив првчкслилв <оператор цвкла> к <безусловным операторам>: ведь как будто <оператор цикла> сочетается о <усховксм> так жо, как к <безусловт иый оператор>.
% тл. нлчлльнык нлплюдкния 231 11 1ХЗ Г,: =Г1ЙХ,; г: =г,яхт; Г.,:=Г )/Г1; Г,: =Х,ЙХ1; Г,: = Х, Ое Хт; гт: = 1'1 Ч 1'э: если гт то на ДА иначе на НЕТ. Автор убежден, что в этом ыесте даже самый робкий читатель возмутится тратой буыаги на демонстрацию столь бездарного иег Рис. 7.2. 11рпмеры логических операторов. л) Ал1 териативпме ветви с обл1пм преемником. С) Цепочке условий о уходом иэ ветен. е) Сложное условие.
подхода к программированию этой задачи. Автор просит прощения и сообщает, что пример приведен для контраста, а также для предупреждения, что на практике такие програэппп появляются, и сожалению, не так уж н редко. ГЛ. 7. ОПРЕДЕЛЕНИЕ СХЕМ ЯНОВА Беэ всякой математической логики и общей теории программирования тремя заданными величинами х„х, и х, можно распорядиться очень просто~ Пусть х, $.
Проверим х: если хе = Ф, то мы имеем два голоса и можем сказать ДА; если х, $, то при хе — — $ мы получаем снова ДА, а при х„= т — НЕТ. Пусть х, = т. Проверим х,: если х, = Ф, то опять все зависит от хе.' при хе = 1 имеем ДА, а при х,= т — НЕТ; если х, = т, то мы уже имеем два против: НЕТ, Эта процедура выбора легко изображается графически (рис.
7.3, а). Глядя на нее, мы сразу соображаем, что проверку хе Т ДА Ал м.т 'дя, н~т ле «еТ Рис. 7.3. Машине голосования. е) Непредвзятый прямоц подход. о) Усовершенствоваяиый прямой подход. нет смысла выписывать два раза; достаточно аавести стрелки от двух проверок х на одну вершину графа (рис. 7.3, б). Мы видим, что расчленение сложных логических условий на серию проверок элементарных предикатов может привести к заметному упрощению программы. На этот раз автор вправе рассчитывать на определенный скептицизм читателя, потому что такое прямое рассуждение, скажем, для десяти голосующих будет, возможно, заметно сложнее или чревато ошибками.
Поэтому естественно рассмотреть способы расчленения сложных предикатов на элементарные более систематически. При атом мы ораву выходим на разумное сужение вадачи (методологически — точно так же, как и при введепии понятия логической формулы): мы отвлечемся от способов вычисления элементарных предикатов, считая их невависимыми логическими' переменнымн, чьи аначения задаются другими (счетными) опера-. е тя. НАЧАЛЬНЫЕ НАБЛЮДЕНИЯ 1х г х г 1 г а) г 4 1 л) г) Рис. 7.4.
Правила расчлеиеиия условий. а) Отрицавие. о) Дизъюнкцкя. в) Колъюикция. а) Имллинация, 2) Д и з ъ ю н к ц и я. Коли условием является днзъюнкция х ')Г' у, то надо проверить х с выходом на плюс-направление при х =- 4 и с переходом к проверке у при х = г. Выходы от проверки у — те же, что и у х у' у (рис.
7.4, б)). Заметим, что зто правило непосредственно опирается на известные свойства диэъюнкции 3) К о н ъ ю н к ц и я. Коли условием является конъюнкция хну, то надо проверить х с выходом на минус-направление при х = г и с переходом к проверке р при х = а. Выходы от проверки у — те же, что и у х8с р (рис. 7.4, в). Заметим, что это правило опирается на аналогичные свойства конъюнкции гну=а, $йу=р.
торами программы. Сам предикат при этом становится просто логической формулой. Поскольку формула составляется из переменных с помощью логических операций, естественно и вопрос расчленения предиката услрвия выяснять, подвергая анализу главные логические операции. Соответствующие правила обнаруживаются немедленно: () О т р и ц а н и е. Коли условием является отрицание ) х„ то, чтобы проверять х, нужно в операторе поменять местами плюс- и минус-направления (рис. 7.4, а).
гл. ъ Опгеделенке схем яновА 4) И и и ли к а ц и я. Если условием является импликация х:э у, то надо проверить х с выходом на плюс-направление при х $ и с переходом к проверке у при х =- Ф. Выходы от проверки у — те же, что и у х ~ у (рис. ?А, г)). Здесь работают следующие свойства импликации: $~ у=г, $ ~ у = у. СФормулировав зги правила, мы легко обнаруживаем, что они зависимы друг от друга: можно взять за основу правила отрицания УУ ч хау г г (1хч1у) г~~ |хч1у г~ '1 У г ф , ТХ ч и у 'г~~ ч х чу г~~ Рис. ?.5. Получение выводимых правил. е) Правило для коиъюивции.
о) Правило для импликации. (ТЗ вЂ” тождествен ' ная вемена условия, р — применение правила для операции р). и дизъюнкции и вывести из них правила конъюнкции, исполв зуя соотношение х8су= ~( ~х)/ 1у),' и импликации, используя тождество х:~ у = ) х ~/ у. Этот вывод показан на рис. ?.5. $7Л. НАЧАЛЬНЫЕ НАБЛЮДЕНИЯ Очевидно, что применяя эти правила, можно совершенно формально расчленить произвольный логический оператор, используя дерево разбора логической формулы, образующей уоловне. Мы порекомендуем читателю проделать таков расчленение для 'условия в «машине голосования» н сравнить результат о программой, показанной на рис.
7.6, а). Посмотрим внимательно на то, что у нас получилось. Естественно, программа очень далека от элегантной схемы голосования с рис. 7.3, б). Однако именно бросающаяся в глаза несуразность программы (каждое условие проверяется четырежды) подсказывает нам, что здесь что-то можно сделать. Проведем содержательный анализ программы на рис.
7.6, а).' Она состоит из четырех «этажей», на каждом из которых есть«коридор» с выходом в конце и с четырьмя «лестницами» на начало нижнего этажа. Двигаясь по коридору от начала, мы последовательно проверяем значения элементарных предикатов и в зависимости от комбинации их значений либо попадаем на концевой выход, чтобы сказать ДА, либо спускаемся по лестнице наначало коридора в нижнем этая7е. Шансы на улучшение программы состоят в том, что, попав на какой-то этаж Р по лестнице, идущей сверху, мы уже знаем значения некоторых предикатов и могли бы на этаже Р и далее сразу выбрать нужное направление, не спрашивая дорогу. Проверим эту идею более внимательно, начав о нижних зтажей программы.
Перед этим, чтобы не загромождать чертежи, еще более схематизируем изображение программы, заменив переменные на их номера, сократив ДА и НЕТ до Д иНи невырисовывая детально части программы, выходящие в' данный момент за поле зрения (см. рис. 7.6, б)). Если при начале движения по второму этажу х, окажется ложным, то, попав по минус-стрелке от х» на первый этаж, мы обнаруживаем, что условие х» с первого этажа обязательно нас переадресует на Н.
По если так, то мы можем в нашей программе перенести минус-стрелку, идущую от второэтажного хм прямо на Н, устраняя повторную проверку того же условия (рис. 7.6, в)). Если мы попадем на первый этаж от второэтажного условия х», то зто будет возможно только при х««и л« * $. Однако прн движении по первому этажу вта комбинация значений непременно переадресует нас на Н. Выяснив это, мы опять-таки можем перенести минус-стрелку от второэтажного и» прямо на Н (рис. 7.6, г)). Рассуждая аналогично для случая попадания на первый этан» от второэтажного л„мы переносим плюс-стрелку от него прямо на Н и получаем программу, покааанную на рис.
7.6, д). Мы обнаруживаем два интересных момента. На первый этаж теперь яе ведет ни одна лестница. Таким образом, на эту часть 2ЗЕ Гл.т. Онведеленне схем янОВА в) ' г) е) Рис. 7.е. систематическое упРовтеиие амашииы толосоваиии». $7.Ь НАЧАЛЬНЫЕ НАБЛЮДЕНИЯ 237 программы нельзя ниоткуда попасть и, стало быть, ее можно просто устранить из программы. В логическом операторе с условием х, на втором этаже плюс- и минус-направления совпадают и поэтому выполнение проверки не Нужно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
