В. Ю. Наумов Введение в информатику
 Скачать 2.05 Mb.
|
|
mov, add и т. д. Но, как правило, мнемоническое 36 правило перемещения выражения справа в переменную слева всегда сохраняется. ПРИМЕР A = 2 // A←2 (A=2) C = A // C←A (C=2) Pokazatel = 6–3 //Pokazatel←6–3 (Pokazatel=3) B = A Pokazatel // B←2 3 (B=8) A=A 2 +B+2*C // A←2 2 +8+2*2 (A=16) Приведенный выше пример показывает правила использования операции присваивания. Далее приведем пример неправильного использования операции присваивания. ПРИМЕР 2=A //Ошибка!!! (нельзя изменять системную константу) A+B=6 // Ошибка!!! (слева записано выражение) 5–4=3+B 2 // Ошибка!!! (слева константное выражение) 1 A // Ошибка!!! (слева записано выражение) 2.4. Основы алгебры логики Любая машина при решении алгоритмических задач выполняет некий вычислительный процесс, который называют машинной логикой. Только в отличие от логики человеческой, она чрезвычайно жесткая, поскольку подчиняется определенному набору правил. Эти правила возведены в ранг математических и носят соответствующее название: математическая логика, или машинная логика. В основе алгебры логики находится так называемый предикат. Предикат – это высказывание, относительно которого можно сказать истинно оно или ложно. Слово образовано от английского Predicate (утверждение). Примеры предикатов: «Земля – третья планета от Солнца», «По календарю сейчас лето» и т. д. 37 Часто логику предикатов называют булевой 11 алгеброй, а выражения, принимающие всего два значения, – булевыми (bool). Для того чтобы научить ЭВМ «мыслить» логикой предикатов, нужно эти самые предикаты перевести на понятный машине язык. В случае языка программирования Pascal в качестве предиката могут быть логические константы и логические выражения. Логическими выражениями будем называть выражения, состоящие из операций отношения и логических констант, связанных логическими операциями. Операция отношения – операция сравнения результатов вычисления двух алгебраических выражений и/или числовых констант. Под операциями отношения понимают набор из шести операций сравнения: <, >, =, ≤, ≥, ≠ (в языке С они записываются так: <, >, ==, <=, >=, !=). Результатом операции отношения всегда являются логические константы TRUE (ИСТИНА) или FALSE (ЛОЖЬ). Результат TRUE получается тогда, когда операция отношения записана верно, а FALSE – в противном случае. Например, пусть 7 x , тогда операция отношения 0 x даст результат TRUE, т. е. истинно, что 7 0 . А при том же значении x операция 5 x даст ответ FALSE, что означает ложность утверждения 7 5 Для простоты понимания, особенно студентам, ранее не изучавшим основы алгебры логики, нужно читать операции отношения с вопросительной интонацией и пытаться дать на заданный вопрос ответ ДА (TRUE) или НЕТ (FALSE). То есть, приведенный выше пример необходимо прочесть так: « 0? x », и в зависимости от значения x дать на него ответ TRUE или FALSE. 11 Джордж Буль (1815–1864) – английский математик и логик. Разработал алгебру логики и основы функционирования цифровых компьютеров. 38 Предикаты бывают простыми (содержащими единственное утверждение) и сложными (содержащими комбинацию утверждений). Комбинирование предикатов происходит по определенным правилам. Для предикативных конструкций, записанных на естественном языке, связками выступают союзы «И» и «ИЛИ». Вот примеры: «Земля – третья планета от Солнца ИЛИ Земля – четвертая планета от Солнца» – ИСТИНА; «Марс – первая планета от Солнца И Земля третья планета от Солнца» – ЛОЖЬ. Комбинация предикатов образует новый предикат. Кроме этого, по отношению к предикатам применяют модифицирующий предлог «НЕ», который отрицает предикат, переводя истинное утверждение в ложное, и наоборот. Например, «В одном километре 1000 метров» – ИСТИНА, а отрицание «В одном километре НЕ 1000 метров» – ЛОЖЬ. Вообще, для составления сколь угодно сложных логических конструкций трех описанных выше операций достаточно. В языке же C++ по умолчанию используют три логических операции: &&, || и !, что можно перевести как, соответственно, И, ИЛИ и НЕ. Логические операции делят на бинарные и унарные. Бинарными называют операции, для выполнения которых необходимо два операнда, унарными – один. Примерами бинарных математических операций являются операции умножения, деления, сложения и вычитания, т. е. умножить можно только одно число на другое; знак умножения теряет смысл, если стоит перед отдельным числом без второго множителя. С другой стороны, из математики известно понятие унарного минуса, который превращает положительное число в отрицательное. Это типичный пример унарной операции, так как унарный минус записывается перед одним числом. 39 Таблица 2.2 Таблица истинности логических операций A B A && B A || B ! A ! B 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 Операции && – логическое И, называемое так же логическим умножением или конъюнкцией и обозначаемое «&» или « », || – логическое ИЛИ (логическое сложение или дизъюнкция, обозначается « »), являются бинарными, то есть для получения с их помощью результата необходимо иметь два операнда. Операция ! – логическое НЕ (логическое отрицание, обозначается линией-надчеркиванием над константой или выражением, например, P , или префиксным значком « ») является унарной операцией. Для того чтобы пользоваться этими операциями, необходимо знать так называемые таблицы истинности. Таблицы истинности – таблицы, в которых описаны правила использования логических операций (т. е. результаты, получаемые при различных комбинациях операндов). Таблицы истинности являются своеобразными «таблицами умножения» для алгебры логики. При помощи этих элементарных правил составляются логические комбинации для выражений любой сложности. Для упрощения записи этих таблиц вводят обозначения: TRUE≡1 (логическая единица), FALSE≡0 (логический нjль). Операнды обозначим A и B. Обратим внимание на унарные операции ! над операндами A и B (табл. 2.2). Вообще, для двух операндов можно составить 16 различных элементарных функций алгебры логики. Однако, все их обычно не записывают, поскольку существует возможность комбинации некоторого базового набора логических операций, которая приводит к 40 эквивалентности таблиц истинности. Наиболее часто используются операции ||, && и !. Будучи записанными в сложном выражении, логические операции применяются в строгой последовательности, согласно установленному приоритету (подобно тому как операция умножения всегда выполняется раньше, чем операция сложения). Приоритет выполнения логических операций следующий (в порядке его убывания): ! && || Операции отношения ПРИМЕР Для 5 x , 0 y получим результат следующего логического выражения: ( 0 x ) && ( 2 y ). Результатом первой операции отношения ( 0 x ) будет значение TRUE, так как истина, что 5 0 . Результатом операции отношения ( 2 y ) будет значение FALSE, так как ложь, что 0 2 . Осталось определить результат такого логического выражения: TRUE && FALSE, что эквивалентно 1 && 0. Из таблицы истинности следует, что это выражение равно 0 или FALSE, т. е. ( 0 x ) && ( 2 y ) = FALSE. Для иллюстрации логических выражений часто применяют диаграммы, взятые из теории множеств (рис. 2.1). Заштрихованная площадь означает истинность того, что некоторая точка принадлежит этой области. 41 2.5. Правила использования логических выражений При доказательстве в алгебре логики применяют набор правил и законов: 1) законы идемпотентности: A = A && A, A = A || A; 2) законы коммутативности: A && B = B && A, A || B = B || A; 3) законы ассоциативности: A && (B && C) = (A && B) && C, A || (B || C) = (A || B) || C; 4) законы дистрибутивности: A && (B || C) = (A && B) || (A && C), A || (B && C) = (A || B) && (A || C); 5) законы нуля и единицы: A && A = FALSE, A && TRUE = A, A B A B A || B ! A A && B A Рис. 2.1 Связь теории множеств и булевой алгебры 42 A || A = TRUE, A || FALSE = A; 6) правила поглощения: A || (A && B) = A, A && (A || B) = A; 7) правила де Моргана: (A || B) (A B) & & , (A && B) (A B) || ; 8) правила склеивания: (A || B) (A B) A & & || , (A && B) (A B) A || & & 2.6. Базовые алгоритмические конструкции Любой сколь угодно сложный алгоритм можно представить в виде комбинации трех базовых алгоритмических управляющих структур: следование, развилка и цикл. Данный тезис был высказан Дейкстрой 12 в конце 70-х годов ХХ века и впоследствии только подтверждался. Этот подход носит название структурного программирования, одним из его основных достоинств является отказ от оператора безусловного перехода (GOTO), что многократно повышает наглядность и надежность программного кода. Каждой из трех управляющих конструкций соответствует свой тип 12 Эдгер Вайб Дейкстра (1930 − 2002) – голландский математик, основопо- ложник метода структурного программирования, занимался вопросами применения математической логики к компьютерным программам. ШАГ A ШАГ Б Рис. 2.2. Управляющая структура «следование» 43 вычислительного процесса, соответственно: линейный, разветвляющийся и циклический. Рассмотрим последовательно каждый из них. Линейным вычислительным процесссам соответствует алгоритмическая управляющая структура следование. В данном случае вычислительные шаги следуют один за другим без пропусков и возвратов, т. е. отсутствуют различного рода ветвления алгоритма – развилки и циклы. Блок-схема данной алгоритмической управляющей структуры имеет вид, показанный на рис. 2.2. Для простоты обозначения шаги заключены в прямоугольники, но на месте прямоугольников могут быть блоки обработки данных (собственно прямоугольники), блоки ввода/вывода (параллелограммы), блоки вызова подпрограмм или иные управляющие конструкции (цикл или развилка). Разветвляющимся вычислительным процессам соответствует алгоритмическая управляющая структура развилка. Во многих алгоритмах реализованы структуры с двумя альтернативными ветвями, одна из которых выполняется в том случае, если проверка некоторого логического выражения (в частном случае условия, например, 0 x ) L дает положительный результат (TRUE – «ИСТИНА»), а другая – отрицательный (FALSE – «ЛОЖЬ»). Эта структура и называется развилкой. На блок-схемах развилки обозначают в виде ромба (предикатного узла) с одним входом и парой выходов (рис. 2.3). Причем выходы направляют влево и вправо, а не вниз (чтобы иметь возможность отличать развилки от циклов). 44 L Действие 1 Действие 2 TRUE FALSE Рис. 2.3. Полная развилка Возможна структура развилки с одной ветвью. То есть, если проверка логического выражения L дает положительный результат, то выполняется одна ветвь развилки, иначе эта ветвь игнорируется (рис. 2.4). L Действие 1 TRUE FALSE Рис. 2.4. Неполная развилка Здесь показана развилка с одной ветвью – ветвью TRUE; развилка же только с ветвью FALSE, хотя и существует, но ею редко пользуются. Дело в том, что для ее реализации достаточно инвертировать логическое выражение L (применить операцию отрицания !), и мы придем к обычной структуре с непустой положительной ветвью (рис. 2.5). 45 Часто вместо слов TRUE и FALSE на блок-схемах пишут «T» и «F», или «Да» и «Нет», или «+» и «–», или «1» и «0» и т. д. ПРИМЕР Рассмотрим более сложный пример. Построим блок-схему алгоритма с использованием развилок (рис. 2.6). Пусть это будет блок-схема алгоритма решения квадратного уравнения 2 0 ax bx c , описанного выше, в разделе 2.2. «Алгоритмизация» с помощью естественного языка. Номера шагов расставим согласно словесному описанию, приведенному ранее. Если сравнить два способа записи одного и того же алгоритма, можно заметить, что на блок-схеме отсутствуют шаги с номерами 7, 11, 14 и 16. Это связано с тем, что действие «выполнить шаг 18» во всех этих пунктах описано стрелками, направленными к шагу 18, соответственно, от 6-го, 10-го, 13-го и 15-го шагов. L TRUE FALSE Действие NOT L TRUE FALSE Действие Рис. 2.5. Преобразование развилки с пустой положительной ветвью в развилку с непустой положительной ветвью 46 Начало Ввод a,b,c Конец Вырожденные случаи квадратного уравнения Рассмотрение невырожденного случая квадратного уравнения a==0 3 18 1 2 8 Рис. 2.6. Общая блок-схема решения квадратного уравнения Еще одной особенностью изображения блок-схемы (рис. 2.6) является ее дробление на более мелкие части, поскольку она достаточно сложная и может не помещаться целиком на странице. Кроме того, возникает наглядное представление о характере решаемой задачи. А именно, сначала рассматриваем проблему в общем (говорим что нужно ввести коэффициенты уравнения , , a b c и далее; в зависимости от введенных данных, решаем один или другой вид уравнения (рис. 2.7 и 2.8). После этого каждый из шагов детализируем до уровня, достаточного для понимания устройством, с помощью которого данная задача будет решаться (ЭВМ). Такой подход отлично соотносится с концепцией структурного программирования и носит название проектирования сверху вниз. То есть от общего мы постепенно переходим к частностям. Существует и иной подход, называемый проектирование снизу вверх (когда решаются сначала частные случаи, а далее все они объединяются в общий алгоритм решения задачи). 47 Вывод x c==0 b==0 18 8 12 следовательно, решений нет’ следовательно, решений бесконечное множество’ 13 15 9 10 Рис. 2.7. Шаг 2–18: алгоритм решения вырожденного случая уравнения Рис. 2.8. Шаг 3–18: алгоритм решения невырожденного уравнения Циклические вычислительные процессы – это многократно повторяющиеся последовательности действий. Таким процессам 48 соответствуют алгоритмические управляющие структуры – циклы. Собственно последовательность действий, которую необходимо многократно повторить, называется телом цикла. Циклы могут быть вложенными. Цикл, находящийся в теле другого цикла, называется внутренним, а охватывающий его – внешним. Вообще, в основе любого цикла лежит итеративность, т. е. многократное повторение одних и тех же действий. Итерация – однократное исполнение алгоритма тела циклического процесса. Iteratio – повторение (лат.). Рассмотрим три основных вида циклов: «с предусловием», «с постусловием», «цикл-счетчик». Цикл с предусловием, или цикл «Пока» (цикл выполняется, пока логи- ческое выражение L дает результат TRUE). Его блок-схема изображена на рис. 2.9. В С++ этот цикл называется «while». Его тело будет выполняться, пока верно логическое выражение (L=TRUE) 13 . Как только результат логического выражения L изменится на |