Учебное пособие 97

Лабораторная работа №2.

Тема: Решение практических задач с помощью алгоритмического языка. Цель: познакомиться с использованием выражений в алгоритмическом

языке, научиться решать задачи с его использованием

2.1 Выражения в алгоритмическом языке

Выражение называют арифметическим, если после его вычисления получено значение числового типа (целого, натурального или вещественного).

Всостав арифметического выражения могут входить:

•константы числовых типов;

•переменные числовых типов;

•обращения к функциям числовых типов;

•служебные слова и знаки для указания арифметических операций;

•круглые скобки, регулирующие порядок выполнения операций.

Среди функций, используемых в выражениях, различают стандартные

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

Вотличие от известных процедурных языков программирования алгоритмически язык не запрещает использовать в качестве стандартных любые известные математические функции из числа тех, которые имеют собственные имена. Например:

•тригонометрические функции Sin(x), Cos(x), Tg(x), Ctg(x);

•обратные тригонометрические функции ArcSin(x), ArcCos(x), ArcTg(x), ArcCtg(x);

•логарифмические функции Lg(x), Ln(x) и многие другие. Каких-либо иных специальных обозначений функций, в том числе и с

использованием верхних или нижних индексов, в АЯ не предусмотрено. Поэтому в ряде случаев AЯ предлагает для общеизвестных стандартных функций искусственные имена или способ представления:

•квадратный корень x записывают в виде Sqrt(x);

•модуль |x| записывают в виде Abs(x);

•логарифм Logax можно записать в виде Ln(x)/Ln(a) или Lg(x)/Lg(a);

•экспоненциальную функцию ех записывают как Ехр(х).

ВАЯ использование имен для обозначения распространенных числовых констант правилами не предусмотрено. Поэтому в подобных случаях возможно применение тех или иных искусственных способов:

•при обычных требованиях к точности число π можно записывать приближенно к 3.14;

•в ответственных случаях в отношении точности число π можно представить в виде*ArcTg(l);

•основание натуральных логарифмов число е можно записывать точно как Ехр(1) или приближенно как 2.72.

Варифметических выражениях могут быть использованы следующие

11

обозначения арифметических операций:

знак бинарной операции возведения в степень "^";

знаки бинарных операций умножения "*" и деления "/";

служебные слова div и mod для указания целочисленного деления и определения остатка от целочисленного деления соответственно;

знаки бинарных операций сложения и вычитания "+" и " – ";

знаки унарных операций указания знака "+" и "—".

Операция возведения в степень имеет статус функции, и поэтому при вычислении выражений имеет приоритет, следующий за приоритетом функции.

Синтаксис АЯ не допускает указания подряд двух или более бинарных операций. Несколько унарных операций могут быть указаны подряд, в том числе и вместе с бинарными.

2.2 Общие понятия о построении алгоритмов

Существуют две основные формы записи алгоритмов на АЯ: алгоритмы в виде процедур (алгоритмы-процедуры) и алгоритмы в виде функций (алгоритмы-функции). Как алгоритм-процедура может быть оформлен любой алгоритм. Форма записи алгоритма-процедуры в общем виде такова:

алг <имя> (арг <перечень аргументов>; рез <перечень результатов>) дано <комментарий к аргументам> надо <комментарий к результатам>

нач <перечень промежуточных переменных> <последовательность команд>

кон

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

Служебное слово алг используется для выделения имени (названия) алгоритма. Имя алгоритма выбирается произвольно. Чаще всего это единое обозначение, которое в сокращенной форме или в виде аббревиатуры передает содержание алгоритма. Например, КвУр — название для алгоритма решения квадратного уравнения, НОД — название для алгоритма определения наибольшего общего делителя. На выбор имен алгоритмов действуют те же ограничения, что и на выбор имен любых других именованных объектов.

После названия алгоритма в круглых скобках указывается перечень имен его параметров с распределением на аргументы (арг) и результаты (рез). Параметром алгоритма может быть только переменная. Для каждого параметра в отдельности указывается его тип. В случае наличия группы однотипных параметров тип может быть указан для всей группы в целом. Перечень параметров алгоритма не является обязательным элементом заголовка, так как могут существовать алгоритмы и без параметров.

Тот или иной параметр алгоритма может являться одновременно и аргументом, и результатом. В этом случае он обозначается как результат, а на-

12

поминание об этом может быть сделано в комментарии к алгоритму. Иначе говоря, параметры алгоритма, указанные как результаты, могут быть использованы как аргументы, но не наоборот.

Необязательные комментарии дано и надо содержат разъяснения к отдельным параметрам алгоритма. При необходимости, комментарий в сжатой форме может раскрывать содержание алгоритма и формулировать ограничения на его использование.

2.3. Условия использования алгоритмов в виде процедур и функций

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

Параметры алгоритма, представленные в его заголовке, будем называть формальными. Считается, что формальные параметры алгоритма доступны извне. Это значит, что именно через их посредство алгоритм может получить значения исходных данных и выдать значения результатов.

Реализация процесса решения задачи в соответствии с описанным алгоритмом ее решения называется исполнением данного алгоритма.

Чтобы исполнение алгоритма стало возможным, необходимо, во-первых, задать какие-то конкретные значения для его аргументов, а во-вторых, указать конкретные переменные, которые должны получить значения его результатов.

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

Таким образом, чтобы исполнить данный алгоритм, следует записать обращение к нему. Иначе говоря, к алгоритму следует обратиться. При этом говорят, что путем обращения к алгоритму осуществляют передачу ему значений аргументов и прием от него значений результатов.

В процессе исполнения алгоритма может оказаться невозможным выполнение той или иной команды. Кроме того, после исполнения алгоритма полученные значения результатов могут оказаться ошибочными. Такие ситуации являются следствием неправильного построения алгоритма. И соответствующие ошибки носят название алгоритмических. Характерной особенностью любой алгоритмической ошибки есть то, что она может быть обнаружена посредством исполнения алгоритма.

К алгоритмам можно обращаться не только с целью их исполнения, но и с целью их использования для построения других, более сложных алгоритмов. В таком случае алгоритм, к которому обращаются, условно называют вспомогательным. В роли вспомогательного может выступать любой алгоритм, в том числе и тот, который сам использует какие-то другие вспомогательные алгоритмы. Тотжеалгоритм, которыйобращаетсяквспомогательным, называютосновным.

Если вспомогательный алгоритм оформлен в виде алгоритма-

13

процедуры, то обращение к нему имеет вид отдельной команды. Такая команда называется командой обращения к алгоритму-процедуре (командой вызова алгоритма-процедуры).

Однако во многих случаях значительно целесообразнее иметь возможность включать обращения к вспомогательным алгоритмам непосредственно в состав тех или иных выражений. При этом основной алгоритм становится более компактнымипонятным, уменьшаетсяколичествоиспользованныхпеременных.

Чтобы обращения к некоторому алгоритму можно было включать в состав выражений, этот алгоритм должен быть оформлен как алгоритм-функция. Обращение к алгоритму-функции называют также вызовом функции.

Как алгоритм-функция может быть оформлен не любой алгоритм, а только тот, который имеет единственный результат простого типа. Это значит, вопервых, что перечень результатов алгоритма должен содержать не более одной переменной, а во-вторых, что тип функции может быть только простым, то есть результат алгоритма-функции должен представлять собой отдельное значение.

Не следует путать знак присваивания ":=" со знаком "=". Знак ":=" указывает исполнителю алгоритма на необходимость выполнения вполне определенного "физического" действия (присвоения переменной значения выражения). В то же время знак "=" никаких реальных действий не предусматривает и является всего лишь знаком операции сравнения величин. Таким образом, если с математической точки зрения запись А=А+1 является бессмысленной, то запись вида А:=А+1 в алгоритмах встречается чрезвычайно часто. Смысл ее состоит в том, что значение переменной А необходимо увеличить на единицу.

Команда присваивания оказывается важнейшей командой АЯ. Действительно, если мы принимаем, что алгоритм описывает процесс преобразования значений аргументов в значения результатов, то единственным средством реализации таких преобразований является именно команда присваивания.

2.4 Линейные алгоритмы

Линейным алгоритмом с точки зрения АЯ будем называть такой алгоритм, значения результатов которого можно получить путем однократного выполнения каждой из последовательности его команд. Сразу отметим, что линейный алгоритм в чистом виде — явление достаточно редкостное, поэтому чаще имеет смысл говорить о линейных фрагментах алгоритмов.

Из определения линейного алгоритма следует, что он может быть построен только из простых команд. Исключение составляет команда выхода из алгоритма, которая применяется в разветвляющихся алгоритмах. Таким образом, для построения линейных алгоритмов будем использовать исключительно команды присваивания и команды обращения к алгоритмам-процедурам.

Для удобства изучения распределим базовые линейные алгоритмы на две группы:

•алгоритмы с результатами числового типа;

•алгоритмы с результатами логического типа.

14

В свою очередь, среди базовых линейных алгоритмов с результатами числового типа будем рассматривать:

•алгоритмы, использующие арифметику вещественных чисел;

•алгоритмы, использующие арифметику целых чисел.

Сформулируем основное условие невозможности построения именно линейного алгоритма решения некоторой задачи.

Для данной задачи невозможно построение линейного алгоритма ее решения, если такой алгоритм не является исполнимым в целом при любых допустимых значениях его аргументов.

Алгоритм будем называть исполнимым в целом, если возможно беспрепятственное выполнение любой его команды. При этом допустимость тех или иных значений аргументов должна определяться только условием самой задачи, а не ее свойствами.

2.5. Алгоритмы, использующие арифметику вещественных чисел

"Вычисление функции". Для произвольных заданных значений переменных х и а построить алгоритм вычисления значения функции

алг ЗначФункции (а, х: вещ): вещ дано произвольные значения а, х надо значение функции

нач n, m: вещ n:=2+а^2

m:=n+Sin(x)

n:=n*Tg(2) ЗначФункции=Sqrt(m)/n-Lg(m)

кон

Алгоритм ЗначФункции (Значение Функции) демонстрирует основные приемы алгоритмизации вычисления выражений.

При построении линейного алгоритма вычисления выражения важно предварительно убедиться в возможности этого. Поскольку условие задачи говорит о допустимости произвольных значений исходных данных, то необходимо сначала исследовать, всегда ли будут возможны соответствующие вычисления. Несложный анализ показывает, что при любых а и х под корнем никогда не появится отрицательное значение, знаменатель всегда будет отличен от нуля, а под знаком логарифма будут только положительные значения. О таких математических функциях говорят, что они непрерывны и определены (существуют) при любых значениях своих аргументов.

Именно поэтому для решения данной задачи возможно построение линейного алгоритма. А поскольку результатом вычисления должно быть единственное вещественноезначение, тоцелесообразнооформлениеалгоритмаввидефункции.

15

При внимательном рассмотрении заданного выражения обращает на себя внимание наличие совпадающих фрагментов. При этом трижды встречается фрагмент а2+2 и дважды — фрагмент Sin(x)*a2+2. Поэтому лучше вычисление указанных фрагментов выполнить отдельно. Это позволит, с одной стороны, избежать повторения одних и тех же вычислений, а с другой стороны, сократить текст алгоритма.

Для этого используются промежуточные переменные n и m. Переменной n присваивается значение фрагмента а2+2. Переменной m присваивается значение фрагмента Sin(x)+a2+2. Обратите внимание, что переменная m получает свое значение с использованием ранее вычисленной переменной n. Так удается сократить количество вычислений.

Теперь при вычислении всего выражения в целом переменная m нам понадобится дважды (из нее нужно будет извлечь корень и вычислить логарифм). А вот переменная n нам понадобится всего один раз (в знаменателе).

Последнее дает нам возможность выполнить так называемое переназначение переменной n. Используем переназначение вот для чего. В целях упрощения целесообразно записать вычисление знаменателя отдельно. Поэтому третья команда алгоритма присваивает переменной n значение знаменателя выражения, используя при этом предыдущее ее значение. Так нам удалось избежать использования лишней промежуточной переменной.

Последняя команда алгоритма вычисляет окончательное значение функции с использованием переменных n и m. При этом выражение для вычисления оказывается весьма простым, не смотря на то, что исходное выражение было достаточно сложным и громоздким.

Таким образом, явно просматривается еще один прием, часто используемый при алгоритмизации вычислений: разбиение большого, сложного и громоздкого выражения на отдельно вычисляемые части через использование промежуточных переменных. Возможные возражения в таких случаях могут быть связаны с использованием "лишних" переменных. Однако более важными здесь оказываются преимущества упрощения и уменьшения вероятности допустить ошибку.

Мы дали нашему алгоритму имя ЗначФункции, чтобы подчеркнуть этим смысл решаемой задачи. Однако в задачах, подобных данной, имеется интересная возможность выбрать имя алгоритма, совпадающее с переменной, которая была использована непосредственно в условии задачи для обозначения самой функции. При этом получим заголовок алгоритма в виде алг у (а, х: вещ): вещ. Благодаря этому, обращения к данной функции мы будем получать в естественном математическом виде у (а, х).

2.6 Решение комбинированных задач

Рассмотренные далее задачи мы называем комбинированными, потому что при их решении предусмотрено обязательное использование каких-либо из базовых алгоритмов в качестве вспомогательных.

16

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

Но главное, что использование вспомогательных алгоритмов при построении алгоритмов решения сложных задач является очень хорошим способом развития алгоритмического мышления учащегося, формирует у него более глубокое понимание идей структурного программирования, стимулирует сознательное использование метода последовательного уточнения.

Задача. Построить алгоритм, определяющий, на сколько изменится значение заданной функции (см. алгоритм ЗначФункции), если значение аргумента х увеличить вдвое.

Для вычисления заданной функции в нашем распоряжении имеется базовый алгоритм ЗначФункции (а, х: вещ): вещ. Если записать обращение к этому алгоритму в виде ЗначФункции (а, х), то будет получено значение функции для некоторых заданных переменных а и х. Обращение к этому алгоритму в виде ЗначФункции (а, 2*х) дает значение, соответствующее удвоенному значению аргумента х при том же значении аргумента а.

Поскольку алгоритм ЗначФункции оформлен в виде функции, то оба обращения должны быть указаны в составе общей формулы в правой части команды присваивания.

алг Разность (а, х: вещ): вещ

нач

Разность = ЗначФункции (а, 2*х) — ЗначФункции (а, х)

кон

2.7. Применение метода последовательного уточнения

Как известно, процесс разработки алгоритма методом последовательного уточнения состоит в том, что сначала алгоритм решения задачи в целом представляется на уровне использования некоторых сложных укрупненных объектов, в частности, команд и функций. На каждом очередном уровне применения метода каждый из сложных укрупненных объектов уточняется путем использования более простых, но опять же таки укрупненных объектов. На самом последнем уровне все простые укрупненные объекты должны быть представлены элементарными объектами (стандартными командами и функциями) АЯ. Основным средством представления укрупненных объектов любого уровня сложности является язык обращения к вспомогательным алгоритмам.

Задача. В круг радиусом R вписан квадрат. Построить алгоритм вычисления, на сколько увеличится площадь вписанного квадрата, если радиус круга увеличить вдвое.

Для решения задачи необходимо дважды вычислить площадь вписанного квадрата: первый раз — при заданном значении радиуса R, второй раз — при удвоенном значении радиуса. Поэтому на начальном этапе целесообраз-

17

но предположить, что в нашем распоряжении имеется алгоритм вычисления площади квадрата, вписанного в круг некоторого произвольного радиуса R:

алг ПлКв (R: вещ): вещ.

С учетом наличия вспомогательного алгоритма ПлКв алгоритм решения основной задачи выглядит так:

алг Увеличение (R: вещ): вещ

нач

Увеличение: = ПлКв (2*R)-mKB (R)

кон

Осталось выполнить уточнение вспомогательного алгоритма ПлКв. Этот алгоритм должен быть составлен для решения следующей более простой вспомогательной задачи.

Вспомогательная задача. В круг радиусом R вписан квадрат. Построить алгоритм вычисления площади этого квадрата.

алг ПлКв (R: вещ): вещ

нач

ПлКв:=2*R^2

кон

Контрольные вопросы

1.Назовите две основных формы записи алгоритмов на алгоритмическом языке.

2.Какие две составляющие содержит запись алгоритма на алгоритмическом языке?

3.Как следует выбирать имя алгоритма?

4.Перечислите правила указания параметров алгоритма в его заголовке.

5.Как оформляется в заголовке алгоритма тот его параметр, который является одновременно и алгоритмом, и результатом?

6.Для чего нужны и каким образом оформляются комментарии в заголовке алгоритма?

7.Как оформляется основная часть алгоритма?

8.Чем отличается оформление алгоритма-функции от оформления ал- горитма-процедуры?

9.Что такое тип функции?

10.Что называется синтаксической ошибкой алгоритма?

11.Что такое формальные параметры алгоритма?

12.Что называется исполнением алгоритма?

13.Что такое фактические параметры алгоритма?

14.Вчемсостоитсмыслобращениякалгоритму?

15.Какиеошибкиназываютсяалгоритмическими?

16.Чтотакоеосновнойивспомогательныйалгоритмы?

18

17.В каком случае обращение к алгоритму должно быть записано в виде команды?

18.В каком случае обращение к алгоритму может быть указано в составе выражения?

19.Какиеалгоритмымогутбытьоформленыкакалгоритмы-процедуры?

20.Какиеалгоритмымогутбытьоформленыкакалгоритмы-функции?

21.Чтоявляетсяобязательнымэлементомосновнойчастиалгоритма-функции?

22.Длячегопредназначенакомандаприсваивания?

23.Сформулируйтеправиловыполнениякомандыприсваивания.

24.Вчемсостоитглавноеусловиесовместимостипоприсваиванию?

25.Вчемсостоитотличиезнакаприсваиванияотзнакаравенства?

26.Вчемсостоятпреимуществаиспользованиявспомогательныхалгоритмов?

27.Вчемсостоитназначениекомандыобращениякалгоритму-процедуре?

28.Опишитевидкомандыобращениякалгоритму-процедуре.

29.Сформулируйте требования к списку фактических параметров коман- дыобращениякалгоритму-процедуре.

30.В чем состоит отличие формальных параметров-аргументов от фор- мальныхпараметров-результатов при замене их фактическими?

31.Сформулируйте правило исполнения команды обращения к алго- ритму-процедуре.

32.Назовите особенности совместимости по присваиванию команды об- ращениякалгоритму-процедуре.

Задания

1.Построить алгоритм, определяющий, на сколько изменится значение заданной функции (см. алгоритм ЗначФункции), если значение аргумента х увеличить вдвое.

2.Построить алгоритм, определяющий сторону квадрата, равновеликого кругу с радиусом R, а также сторону квадрата, равновеликого двум кругам

срадиусами R/2.

3.Заданы длины диагоналей ромба X и Y. Построить алгоритм для определения периметра и площади ромба.

4.Построить алгоритм обмена значений трех переменных А, В и С так, чтобы переменная А приобретала значение переменной В, переменная В приобретала значение переменной С, а переменная С приобретала значение переменной А.

5.Построить алгоритм вычисления площади треугольника по заданным координатам его вершин (хА, уА), (хв, ув), (хс, ус).

6.Заданы стороны треугольника а, b, с. Построить алгоритм вычисления котангенса угла, лежащего против стороны а.

7.Задано прямоугольное отверстие со сторонами а, b. Построить алгоритм определения, можно ли просунуть через это отверстие цилиндр с радиусом основания R и высотой L при условии, что ось цилиндра или парал-

19

лельна противоположным сторонам отверстия, или перпендикулярна плоскости отверстия.

8.Кольцо образовано двумя концентрическими окружностями радиусами R1 и R2 с центрами в начале координат. Построить алгоритм, определяющий, принадлежит ли кольцу заданная точка с координатами (х, у). Считать, что расстояние заданной точки от начала координат не совпадает ни с одним из радиусов.

9.Известно, что продолжительность года равна 365 или 366 суткам. Построить алгоритм, определяющий, верно ли, что суммарная длительность двух заданных лет превышает 730 суток.

10.Известны два момента времени одних и тех же суток, выраженные в часах и минутах (41, Ml и 42, М2 соответственно). Построить алгоритм, определяющий промежуток времени между этими двумя моментами, выразив его также в часах и минутах.

11.От начала суток прошло К полных секунд. Построить алгоритм вычисления значений обоих углов между часовой и минутной стрелками.

12.Часовая стрелка за некоторый интервал времени повернулась на угол F градусов. Построить алгоритм, выражающий этот интервал времени в полных сутках, часах и минутах.

13.В круг радиусом R вписан квадрат. Построить алгоритм вычисления, на сколько увеличится площадь вписанного квадрата, если радиус круга увеличить вдвое.

14.Из заготовки, имеющей форму куба с ребром А, выточили шар наибольшего возможного радиуса. Потом из такой же заготовки выточили шар вдвое меньшего радиуса. Построить алгоритм, определяющий, на сколько процентов увеличились потери материала.

15.Построить алгоритм, который, во-первых, вычисляет диаметр большой трубы, заменяющей по пропускной способности две малых трубы

диаметрами D1 и D2, a во-вторых, вычисляет диаметр огромной трубы, заменяющей две больших.

Библиографический список

1.Абрамов, С.А. Задачи по программированию / С.А. Абрамов [и др.]. — М.: Наука, гл. ред. физ.-мат. лит., 1988.

2.Есаян, А. Р.Информатика: учеб. пособие для пед. спец. высш. учеб. заведений / А. Р. Есаян [и др.]. — М.: Просвещение, 1991.

3.Заварыкин, В. М.Техника вычислений и алгоритмизация: вводный курс: учеб. пособие для студентов пед. ин-тов по физ.-мат. спец./ В. М. Заварыкин [и др.]. — М.: Просвещение, 1987.

4.Кушниренко, А. Г. Программирование для математиков: Учеб. пособие для вузов / А. Г.Кушниренко, Г. В. Лебедев. — М.: Наука, гл. ред. физ.-мат. лит., 1988.

5.Лапчик, М. П. Вычисления. Алгоритмизация. Программирование: пособие для учителя / М. П. Лапчик — М.: Просвещение, 1988.

20