Сёмов Основы разработки алгоритмов и программ. Учебное пособие для студентов факультета дистанционных форм обучения миигаик москва 2020 2 Рецензенты
 Скачать 391.34 Kb.
|
|
> больше < меньше >= больше или равно <= меньше или равно = равно <> не равно В операциях сравнения должны участвовать однотипные операнды. Исключение сделано в отношении REAL и INTEGER, которые могут сравниваться друг с другом. Результат применения операции отношения к любым операндам имеет тип BOOLEAN. Сравнение двух строк осуществляется следующим образом. Символы строк сравниваются попарно друг с другом так, что первый символ первой строки сравнивается с первым символом второй строки, второй символ первой строки - со вторым символом второй и т.д. Символы сравниваются путем сравнения их кодов во внутреннем представлении. Если одна строка короче другой, недостающие коды символов заменяются нулми. Отношение первой несовпадающей друг с другом пары кодов символов и принимается за отношение двух строк. Если в выражении присутствуют арифметические операции и операции отношения, то сначала выполняются арифметические операции, а затем операции отношения. В логических выражениях, используются следующие логические операции: операция OR (ИЛИ), операция XOR (исключающее ИЛИ)операция AND (И), операция NOT (НЕ), причем операции OR, XOR и AND связывают между собой два логических выражения, а операция NOT воздействует на одно логическое выражение. Как работают логические операции, показывает таблица “ истинности ”(Табл. 8). 37 Таблица 8 Логическая операция Логическое выражение А Логическое выражение B Результат логической операции NOT True False OR True True True True False True False True True False False False AND True True True True False False False True False False False False XOR True True False True False True False True True False False False При вычислении выражений любого типа приоритет вычислений определяется расставленными скобками, а при их отсутствии в порядке убывания приоритета логических операций (Табл. 9). Таблица 9 Приоритет операций Операция 1 высший not 2 ниже and 3 еще ниже or 4 еще ниже xor 5 еще ниже =, < >, <, >, <=, > = Рассмотрим примеры записи логических выражений: 1. (x>0) and ( x <= 1); 38 2.( not (sin( x ) < 1/3) and (x >0)) or ((sqr ( y ) < 3) and ( y >0)). Поскольку логические операции имеют более высокий приоритет, чем операции отношения, в сложных логических выражениях обычно необходимо расставлять скобки. 4.8. Оператор ветвления В языке Паскаль имеется оператор ветвления. Другое его название — условный оператор. Формат полного оператора ветвления следующий: if <логическое выражение> then <оператор1> else <оператор2> ; Здесь if — если, then — то, else — иначе. Сравните запись алгоритма БИД1 (см. стр.20) с соответствующей программой.BID1 на Паскале (Табл. 10). Таблица 10 алг БИД1 вещ a, b, нач Ввод a, b если a > b то c := a иначе c := b кв вывод с кон. program BID1; var a, b, c: real; begin readln (a, b); if a > b then c := a else c := b; writeln ( c ): end. Очень похоже на перевод с русского языка на английский. Обратите внимание на следующее отличие: в программе нет специального служебного слова, обозначающего конец ветвления. Здесь признаком конца оператора ветвления является точка с запятой. Поэтому перед else точка с запятой не ставится. Простой формой логического выражения является операция отношения. Как и в Алгоритмическом языке, в Паскале допускаются все виды отношений (ниже указаны их знаки): < - меньше; <= -меньше или равно; > -больше; >= -больше или равно; = -равно; <> -не равно 39 А теперь запрограммируем на Паскале алгоритм «БИД2» (см. стр.21), в котором использовано неполное ветвление (Табл. 11). Таблица 11 алг БИД2 program BID2; вещ a,b,c var a, b, c: нач begin Ввод a, b readln (a, b); c:=a c:= a; если b > a то if b > a then с := b c:=b; кв вывод с writeln ( c ); кон. end. Опять все очень похоже. Ветвь else («отрицательная» ветвь») в операторе ветвления может отсутствовать. Составим программу упорядочения значений двух переменных (Таблица 12). Таблица 12 алг сортировка program BID2; вещ x, y, c var x, y, c; нач begin Ввод x, y readln ( x, y); если x > y то if x > y then с := x begin x := y с := x; y := c x := y; y := c; кв end; вывод x,y writeln ( c ): кон. end. 40 Этот пример иллюстрирует следующее правило Паскаля: если на какой-то из ветвей оператора ветвления находится несколько последовательных операторов, то их нужно записывать между служебными словами begin и end. Конструкция такого вида: begin <последовательность операторов> end называется составным оператором. Следовательно, в описанной выше общей форме ветвления <оператор1> и <оператор2> могут быть простыми или составными операторами. Обратите внимание на то, что перед словом else нельзя ставить точку с запятой. Алгоритмы ветвления могут иметь вложенную ветвящуюся структуру, которая программируется с помощью вложенных условных операторов. Например: 1) If <логическое выражение1 > then <оператор 1> else if <логическое выражение 2> then <оператор2> else <оператор 3>; или 2) If <логическое выражение1 > then If <логическое выражение2 > then <оператор 1> else <оператор 2> else if <логическое выражение3> then <оператор 3> else <оператор 4>; 41 или 3) If <логическое выражение1 > then Begin If <логическое выражение2 > then <оператор 1>; If <логическое выражение3 > then <оператор 2> else <оператор 3>; end else if <логическое выражение4> then <оператор 4> else If <логическое выражение5 > then <оператор 5> else <оператор 6>; В качестве обязательного упражнения нарисуйте блок-схемы трех вложенных ветвлений, приведенных выше. 4.9. Оператор выбора Оператор выбора является обощением условного оператора для случаев произвольного числа альтернатив. Оператор выбора позволяет выбрать для выполнения один из нескольких возможных операторов программы. Параметром, по которому осуществляется выбор, служит так называемый ключ выбора - выражение перечисляемого типа.(INTEGER, CHAR, BOOLEAN). Структура оператора выбора такова: СASE <ключ выбора > OF < список выбора > ELSE <оператор- альтернатива» END. Здесь CASE, OF, ELSE, END - зарезервированные слова. <ключ выбора > – выражение перечисляемого типа; 42 <список выбора > – одна или более конструкций вида – <константа выбора – значение ключа выбора > : < оператор >; < константа выбора > – константа того же типа, что и выражение ключа выбора; < оператор > - произвольный оператор ТП. Оператор выбора работает следующим образом: сначала вычисляется значение выражения <ключ выбора>, а затем в последовательности операторов < список выбора> отыскивается такой, которому предшествует константа, равная вычисленному значению ключа выбора. Найденный оператор выполняется, после чего оператор выбора завершает свою работу. Если в списке выбора не будет найдена константа, соответствующая вычисленному значению ключа выбора, управление передается оператору, стоящему за кодовым словом ELSE. Рассмотрим простейший пример оператора выбора Case Color of Red : x := y + 2; Yellow : x := y – 2; Green : x := y Else Writeln(‘Значение ключа выбора не совпадает с константами из списка выбора’) End; Если значение переменной Color равно константе Red, то выполняется оператор x := y + 2 оператор выбора завершается. Аналогичные действия выполняются при значении переменной Color, равной Yellow или Green. Если значение Color не совпадает со списком (Red, Yellow, Green), то будет выполняться оператор, расположенные после слова ELSE. Часть ELSE < оператор > можно опускать. Тогда при отсутствии в списке выбора нужной константы оператор выбора просто завершит свою работу. Любому из операторов списка выбора может предшествовать не одна, а несколько констант выбора, разделенных запятыми. Например, следующая программа при вводе одного из символов у или Y выведет на экран слово "Да", а при вводе n или N - слово "Нет": Var ch : char; Begin readln(ch); case ch of ‘n’,’N’ : writeln(‘Нет’); ‘y’,’Y’ : writeln(‘Да’); 43 end; End. 4.10. Вопросы и упражнения 1. Как программируется на Паскале полное и неполное ветвление? 2. Что такое составной оператор? В каких случаях составной оператор используется в операторе ветвления? 3. Что обозначает понятие «диалоговый характер программы»? 4. Какими средствами программируется диалог между пользователем и компьютером? 5. Что обозначает понятие «дружественный интерфейс»? 6. Составьте программы в соответствии с алгоритмами БИТ1 и БИТ2 из подраздела последовательные и вложенные ветвления. 7. Составьте программы в соответствии с алгоритмами БИД1 и БИД2 из раздела Алгоритмы с ветвящейся структурой 8. Постройте алгоритм и составьте программу, по которой будет реализован следующий сценарий: компьютер запрашивает номер дня недели, после ввода компьютер сообщает название этого дня. Например, если ввели 1, то выведется фраза «Это понедельник» и т.д. 4.11. Технология решения задач на ЭВМ. Программирование циклов Вы научились составлять линейные и ветвящиеся программы на Паскале. Теперь нужно освоить программирование циклов. Снова будем учиться на примере конкретной задачи. Но, в отличие от предыдущих примеров, начнем с изложения общего подхода к программированию с целью решения конкретной задачи. Часто задача, которую требуется решить, сформулирована не на математическом языке. Для решения на компьютере ее сначала нужно привести к форме математической или логической задачи, а потом уже программировать. Работа по решению таких задач с использованием компьютера проходит через следующие этапы: 1. Постановка задачи. 44 2. Математическая формализация, 3. Построение алгоритма. 4. Составление программы на языке программирования. 5. Отладка и тестирование программы. 6. Проведение расчетов и анализ полученных результатов. Эту последовательность называют технологической цепочкой решения задачи на ЭВМ. В чистом виде программированием, то есть разработкой алгоритма и программы, здесь являются лишь 3-й, 4-й и 5-й этапы, На этапе постановки задачи должно быть четко определено, что дано и что требуется найти. Второй этап — математическая формализация. Здесь задача переводится на язык математических формул, уравнений, отношений. Далеко не всегда эти формулы очевидны. Нередко их приходится выводить самому или отыскивать в специальной литературе. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующей математической модели. Третий этап — построение алгоритма. Вы знаете два способа описания алгоритмов: блок-схемы и Алгоритмический язык. Первые три этапа – это работа без компьютера. Дальше следует программирование на определенном языке в определенной системе программирования и этап отладки и тестирования программы. Последний (шестой) этап- это использование уже разработанной программы в практических целях. Проследим все этапы технологической цепочки на примере конкретной задачи. • Постановка задачи. Дано N кубиков, на которых написаны разные буквы. Сколько различных N-буквенных слов можно составить из этих кубиков (слова не обязательно должны иметь смысл)? Искомую целочисленную величину обозначим буквой F, Тогда постановка задачи выглядит так ДАНО: N кубиков, на каждом – только одна буква, все буквы разные. НАЙТИ: F • Математическая формализация. Получим расчетную формулу. При составлении слова в первую позицию можем поставить N вариантов буквы. Во вторую позицию для каждого варианта заполнения 1 – ой позиции можем поставить (N – 1) вариант буквы (любую букву, из оставшихся после заполнения первой позиции). Таким образом, первые две позиции 45 можно заполнить Nx(N - 1) способами. В третью позицию можем выбрать (N - 2) варианта буквы (любую букву, из оставшихся после заполнения первых двух позиций). Таким образом первые три позиции можно заполнить Nx(N - 1)x (N-2) способами и так далее. Для последней N – ой позиции останется ровно одна буква. Таким образом, формула для F имеет вид: F = Nx(N - 1)x(N-2)x(N-3)x….x3x2x1. Произведение N последовательных натуральных чисел, начиная с 1, носит название факториал числа N и обозначается N! Теперь вернемся к формулировке задачи. Если N обозначает количество букв, a F — количество слов из этих букв, то расчетная формула такая: F = N!=lx2x..xN. • Построение алгоритма. Поскольку алгоритм должен быть независимым от данного значения N, то его нельзя сделать линейным. Дело в том, что для разных N надо выполнить разное число умножений. В таком случае с изменением N линейная программа должна менять длину. Алгоритм решения данной задачи будет циклическим. С циклическими алгоритмами вы уже познакомились, Цикл — это команда исполнителю многократно повторить указанную последовательность команд. Рассмотрим алгоритм на АЯ. алг СЛОВА цел F,N,R нач ввод N F:=l R:=1 пока R <= N, повторять нц F := F * R R := R + 1 кц вывод F кон 46 Здесь применена знакомая вам алгоритмическая структура «цикл с предусловием». Выполняется она так: пока истинно условие повторения цикла, повторяется выполнение тела цикла. Тело цикла составляют две команды присваивания, заключенные между служебными словами нц и кц. Условие цикла — это отношение R<=N (R меньше или равно N). В данном алгоритме переменная R выполняет роль множителя, значение которого меняется от 1 до N через единицу. Произведение накапливается в переменной F, начальное значение которой равно 1. Цикл заканчивается, когда R станет равно N+1. Это значение в произведение уже не попадет. Для проверки правильности алгоритма построим трассировочную таблицу. Следующая трассировочная таблица (Табл.13) составлена для случая N=3 Таблица 13 Шаг Операция N F R Условие 1 ввoд N 3 - - 2 F:=1 1 - 3 R:=1 1 4 R 5 F:=FxR 1 6 R:=R+1 2 7 R<=N 2<=3. да 8 F:=FxR 2 9 R:=R+1 3 10 R<=N 3<=3.да 11 F:=FxR 6 12 R:=R+1 4 13 R<=N 4<=3 нет 14 вывод F 6 15 конец Из этой таблицы хорошо видно, как менялись значения переменных. Новое значение, присвоенное переменной, стирает ее старое значение (здесь не повторяется запись значения переменной, если оно не изменяется; в таком виде таблица менее загромождена числами). 47 Последнее значение F равно 6. Оно выводится в качестве результата, Очевидно, что результат верный: 3!=6. Составление программы. Чтобы составить программу решения нашей задачи, нужно научиться программировать циклы на Паскале. 48 4.12. Операторы циклов Основной циклической структурой является цикл с предусловием (цикл-пока). С помощью этой структуры можно построить любой циклический алгоритм. Оператор цикла с предусловием в Паскале имеет следующий формат: while <логическое выражение> do <оператор>. Служебное слово while означает «пока», do — делать, выполнять. Оператор, стоящий после слова do, называется телом цикла. Тело цикла может быть простым или составным оператором, т.е. последовательностью операторов между служебными словами begin и end. А теперь запрограммируем на Паскале алгоритм решения нашей задачи (добавим к нему организацию диалога). Program Words; var F, N, R: integer; begin write('Bведите число букв: '); readln(N); F := l; R := l; while R<=N do begin F := F * R; R := R + 1; end; writeln('Количество слов = ', F); end. Снова бросается в глаза схожесть алгоритма на АЯ и программы на Паскале. Обратите внимание на то, что в Паскале нет специальных служебных слов для обозначения начала и конца цикла (так же как и конца ветвления). Во всех случаях, где это необходимо, используются слова |