программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 2. Азы языка Паскаль 8. Начиная с календаря Папы римского Грегориуса (1752 г.) сохраняется сле- дующее правило для високосных годов (годы с 366 днями): год, делимый на 4, — високосный год (например, 1972); но если он делится на 100, это не високосный год (например, 1900); но если он делится на 400, это — висо- косный год (например, 2000). Запишите на Паскале отношение, истинное когда n — високосный год, и ложное в противном случае. 9. Пусть n — натуральное число. Напишите программу, которая печатает сле- дующие числа в указанном расположении на экране. n 2 n n 2 n 3 n 2 n 10. Запишите указанное действие в виде одного условного оператора: известно, что из четырех чисел a 1 , a 2 , a 3 и a 4 одно отлично от трех других, раных между собой; присвоить номер этого числа переменной n. 11. Сколько раз будет выполняться тело следующего оператора цикла? k := 0; for i:=1 to k+3 do k:= k+1; Рекомендуемая литература к главе 2 [1] Немнюгин С. А. Turbo Pascal / С. А. Немнюгин. — СПб. : Питер, 2001. — 496 г. [2] Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с. [3] Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. : Мир, 1985. — 405 с. Глава 3 ПРОЦЕДУРНОЕ ПРОГРАММИРОВАНИЕ Перейдем к изучению процедурного программирования — когда большая про- грамма представлялась совокупностью подпрограмм (процедур и функций). Одна из подпрограмм являлась главной, и с нее начиналось выполнение программы. 3.1 Синтаксис подпрограмм 3.1.1 Понятие подпрограммы Представление программы как совокупности (иерархии) относительно обособ- ленных фрагментов со строгими и явно определенными интерфейсами способству- ет большей ясности и модифицируемости программы, легко проверяемой, и, как следствие, влечет повышение качества и эффективности программы. Современный подход к разработке программ поощряет явное оформление в ви- де подпрограммы любого достаточно самостоятельного и законченного программ- ного фрагмента. Подпрограмма — обособленная именованная часть программы со своим соб- ственным локальным контекстом имен. Вызов подпрограммы — выполнение действий, заданных в подпрограмме, мо- жет быть произведен в некоторой точке программы посредством указания имени этой подпрограммы. Понятие подпрограммы — элементарное средство повышения «уровня» языка. Сосредоточив в одном месте программы подробное описание некоторых «тех- нических» аспектов, мы получаем возможность, что в остальной программе доста- точно указывать имена этих действий («операций», введенных подпрограммами), не конкретизируя семантику. Подпрограмма содержит описание некоторой совокупности локальных объек- тов: констант, типов, переменных и т. п. Эти объекты предназначены для органи- зации действий в подпрограмме и имеют смысл («доступны», «видимы») только внутри подпрограммы. 56 Глава 3. Процедурное программирование Подпрограмма может быть разработана для различных случаев применения. Следовательно, перед выполнением подпрограммы можно передать ей некоторую информацию из точки вызова («настроив» ее соответствующим образом). Это осу- ществляется с помощью понятия параметров подпрограммы и приводит к большей гибкости и универсальности подпрограммы, уменьшению взаимной зависимости подпрограммы и точки вызова. Некоторые примеры подпрограмм вам уже известны: функции и стандартные процедуры чтения и записи. 3.1.2 Общая структура подпрограмм Структура подпрограммы почти буквально повторяет структуру всей Паскаль- программы — «часть подобна целому», демонстрирует «регулярный характер по- строения языка». При описании подпрограммы в общем случае необходимо задать три основные компоненты: • интерфейс подпрограммы, т. е. информацию, необходимую для ее вызова (активизации); • локальный контекст подпрограммы: совокупность описаний (рабочих) объ- ектов, с которыми осуществляются действия; • собственно действия (операторы), составляющие смысл подпрограммы. Интерфейс подпрограммы или, иными словами, та информация, которая «пред- ставляет» подпрограмму и достаточна для корректного ее вызова, сосредоточена в заголовке. Для уточнения двух остальных компонент подпрограммы нам понадобится определение такой синтаксической категории, как блок. Синтаксическое определение программы в БНФ: <программа> ::= <необязательный заголовок программы><блок>. <необязательный заголовок программы> ::= program <идентификатор>; <блок> ::= <описания типов, переменных, подпрограмм и т. п.> begin <операторы> end Описание локальных объектов и операторы (алгоритм) подпрограммы состав- ляют внутреннюю ее часть и, как правило, имеют синтаксис блока. Можно сказать, что заголовок содержит информацию о том, что делает подпрограмма, а тело подпрограммы (блок) описывает, как она это делает. Два вида подпрограмм — процедуры и функции — имеют одинаковый смысл и аналогичную структуру, но различаются в назначении и способе их использования. Функции служат для определения алгоритма вычисления нового значения неко- торого простого типа, и вызов функции должен быть операндом в выражении. Процедуры служат для задания совокупности действий, направленных на из- менение внешней по отношению к ним программной обстановки и, как следствие, определение новых значений переменных в программе. Вызов процедуры играет роль оператора. 3.1 Синтаксис подпрограмм 57 Синтаксис <описание процедуры> ::= <заголовок процедуры>; <тело процедуры>; <описание функции> ::= <заголовок функции>; <тело функции>; <заголовок процедуры> ::= procedure <идентификатор> | procedure <идентификатор> <список формальных параметров> <заголовок функции> ::= function <идентификатор> : <тип> | function <идентификатор> <список формальных параметров> : <тип> 3.1.3 Тело подпрограммы. Области действия имен Следующий пример-схема будет использоваться в качестве иллюстрации. Тело подпрограммы = блок (на схеме представлено три вложенных блока). Имена объектов, описанных в блоке подпрограммы, считаются известными в пределах данного блока. Это же относится и к именам формальных параметров. Формальные параметры и объекты, описанные в блоке, образуют собственный локальный контекст данного блока. В описании блока может содержаться описания процедур и функций, следова- тельно, возможны вложенные подпрограммы. 58 Глава 3. Процедурное программирование Правила для доступа к объектам, описанным в разных блоках (правила види- мости): • Имена объектов, описанных в блоке, считаются известными в пределах данного блока, включая и все вложенные блоки. • Имена объектов, описанных в блоке, должны быть уникальны в пределах данного блока и могут совпадать с именами объектов в других блоках. • Если в некотором блоке описан объект, имя которого совпадает с именем объекта, описанного в объемлющем блоке, т. е. это последнее имя стано- вится недоступным в данном блоке. Говорят, что имя, описанное в блоке, экранирует (закрывает, делает недоступным) одноименные объекты из блоков, объемлющих данный. Локальный контекст имен — локальные объекты блока вместе с видимыми в нем объектами объемлющих блоков. На схеме для блока процедуры out ло- кальный контекст имен образуют формальные вещественнее переменные a и c, вещественная переменная b, целые переменные e и f, процедура into. Для блока процедуры into локальный контекст имен образуют целые переменные e и f, формальный вещественный параметр a процедуры out, вещественная перемен- ная b, переменная c типа digits. Глобальный контекст имен — совокупность объектов, описанных в самом внешнем блоке (на схеме: целые переменные a, b и процедура out). 3.2 Семантика подпрограмм 3.2.1 Использование процедур и функций Разбиение программ на процедуры и функции повышает качество и эффектив- ность программирования. Важно владеть различными приемами использования подпрограмм. Задача. Дан четырехугольник с вершинами A, B, C и D. Известны длины сторон AB, AD, BC, CD и длина диагонали BD. Требуется найти площадь четырехугольника. Приведем различные примеры подпрограмм для решения этой задачи. При- веденная ниже подпрограмма без параметров не выдерживает никакой критики, единственное ее достоинство в том, что с помощью процедуры str1 явно выде- ляются похожие действия при вычислении площади треугольника. var AB,BC,CD,AD,BD:real; S1,S,a,b,c,p:real; procedure str1; {Вычисление площади треугольника со сторонами a, b и c. Длины этих сторон заданы в виде значений глобальных переменных.} begin p:=(a+b+c)/2; S:=sqrt(p*(p-a)*(p-b)*(p −c)) end; 3.2 Семантика подпрограмм 59 begin read(AB,BC,CD,AD,BD); a:=AB;b:=AD;c:=BD; str1; S1:=S; a:=BC;b:=CD;c:=BD; str1; S1:=S1+S; writeln( 'площадь=',S1) end. 1. Версия, приведенная ниже, процедуры для вычисления площади треуголь- ника (теперь она называется str2) основывается на наблюдении, что перемен- ная p в главной программе не используется и поэтому может быть сделана ло- кальной. По-прежнему предложенная процедура обладает существенным недостат- ком — слишком сложно ее вызывать. procedure str2; {Вычисление площади треугольника со сторонами a, b и c. Длины этих сторон заданы в виде значений глобальных переменных.} var p:real; begin p:=(a+b+c)/2; S:=sqrt(p*(p −a)*(p−b)*(p−c)) end; Из описания переменных в главной программе можно удалить переменную p, но можно и оставить (в последнем случае она совершенна бесполезна). 2. Процедура с параметрами значительно облегчает ее вызов. var AB,BC,CD,AD,BD:real; S1,S2:real; procedure str3(a,b,c:real;var S:real); {Вычисление площади S треугольника со сторонами a, b и c} {a,b,c,S — формальные параметры} var p:real; begin p:=(a+b+c)/2; S:=sqrt(p*(p −a)*(p−b)*(p−c)) end; begin read(AB,BC,CD,AD,BD); str3(AB,AD,BD,S1); {AB,AD,BD,S1 — фактические параметры} str3(BC,CD,BD,S2); {BC,CD,BD,S2 — фактические параметры} writeln( 'площадь=',S1+S2) end. 3. Выходной параметр S у процедуры str3 имеет простой тип, поэтому луч- шим решением является использовать не процедуру, а функцию. 60 Глава 3. Процедурное программирование var AB,BC,CD,AD,BD:real; function str4(a,b,c:real):real; {функция вычисляет площадь треугольника со сторонами a, b и c} var p:real; begin p:=(a+b+c)/2; S:=sqrt(p*(p −a)*(p−b)*(p−c)) end; begin read(AB,BC,CD,AD,BD); writeln( 'площадь=',str4(AB,AD,BD)+str4(BC,CD,BD)); end. 3.2.2 Механизм параметров Имеется два различных способа передачи фактических параметров в подпро- граммы. Если в описании формального параметра ему предшествует var, то этот способ называется передачей параметра по ссылке, а сам параметр называется параметром-переменной. Если var отсутствует, то такой параметр называется параметром-значением, а способ — передача параметра по значению. Синтаксис списка параметров: <список формальных параметров> ::= (<описание параметров> {;<описание параметров>}) <описание параметров> ::= <идентификатор> {,<идентификатор>} : <идентификатор типа> | var <идентификатор> {,<идентификатор>} : <идентификатор типа> Параметры-значения Формальный параметр в этом случае считается обычной локальной перемен- ной подпрограммы. Фактический параметр может быть произвольным выражением того же типа, что и формальный параметр. Внутри подпрограммы возможны произвольные действия с данным формаль- ным параметром, но любые изменения его значения никак не отражаются на значениях переменных вне подпрограммы. Следующая программа демонстрирует поведение значений локальных и гло- бальных переменных при передаче параметров по значению. 3.2 Семантика подпрограмм 61 Пример procedure SumSquare (x,y:real); begin x:=x*x; y:=y*y; writeln( 'Сумма квадратов = ',x+y) end; var a,b:real;x,y:real; begin SumSquare(2,3); печать: 13 a:=0;b:=1; SumSquare(a,b); печать: 1 x:=2;y:=3; SumSquare(x,y); печать: 13 writeln(x, ' ',y); печать: 2 3 SumSquare(x*y,x+y); печать: 61 end. Параметры-переменные Параметры, передаваемые по ссылке, используются для передачи некоторых значений, вычисленных в подпрограмме наружу в программу. Пример Сумма и разность квадратов двух чисел: procedure Draft1(x,y:real); var Sum, Sub:real; begin Sum:=x*x+y*y; Sub:=x*x-y*y end; Выполнение процедуры Draft1 не имеет никаких последствий. Локальные переменные Sub, Sum известны только в пределах текущего блока, после выпол- нения процедуры исчезают. 62 Глава 3. Процедурное программирование Пример procedure Draft2(x,y:real;Sum,Sub:real); begin Sum:=x*x+y*y; Sub:=x*x-y*y end; Что произойдет? var SumAB,SubAB:real; begin Draft2(2,3,SumAB,SubAB); end. Присваивание любых значений Sum и Sub не приведет к получению этих значений переменными SumAB и SubAB. При передаче параметра по ссылке изменение в теле подпрограм- мы формального параметра приводит к аналогичному изменению фактического параметра. Пример procedure SumSub(x,y:real;var Sum,Sub:real); begin Sum:=x*x+y*y; Sub:=x*x-y*y end; Здесь формальные параметры Sum и Sub считаются синонимами соответству- ющих фактических параметров (указывают на одно и тоже место в памяти). Фактические параметры при передаче по ссылке должны быть только переменными того же типа, что и формальные параметры. Пример procedure swap(var x,y:real); {обмен значениями} var t:real; begin t:=x; x:=y; y:=t end; 3.2 Семантика подпрограмм 63 После вызова процедуры swap(A, B) переменные A и B поменяются своими значениями. Пример Следующая программа демонстрирует поведение значений локальных и гло- бальных переменных при передаче параметров по ссылке. var a,b:integer; procedure h(x:integer;var y:integer); begin x:=x+1; y:=y+1; writeln(x, ' ',y); end; begin a:=0;b:=0; h(a,b); {печать: 1 1} writeln(a, ' ',b) {печать: 0 1} end. Пример Умелое использование процедур с параметрами-переменными приводит к пре- красным результатам. В качестве примера приведем решение следующей задачи. Пусть процедура reduction(a, b, p, q) от целых параметров (b ≠ 0) приводит дробь a/b к несократимому виду p/q. Описать данную процедуру и использовать ее для приведения дроби 1 + 1/2 + 1/3 + . . . + 1/20 к несократимому виду. procedure reduction(a,b:integer;var p,q:integer); var a1,b1,f:integer; begin a1=abs(a);b1=abs(b); while (a1<>0) and (b1<>0) do if a1>b1 then a1:=a1 mod b1 else b1:=b1 mod a1; if a1=0 then f:=b1 else f:=a1; p:=a div f; q:=b div f; end; {следующий фрагмент главной программы приводит дробь 1+1/2+1/3+. . .+1/20 к несократимому виду} c:=0; d:=1; {c/d=0} for i:=1 to 20 do reduction(c*i+d,i*d,c,d); {c/d+1/i=(ci+d)/(di)} 64 Глава 3. Процедурное программирование 3.2.3 Побочный эффект В императивных языках (в том числе и в Паскале) функции могут ссылаться на глобальные данные, и разрешается применять деструктивное (разрушающее) присваивание, что может привести к изменению значения функции при повторном ее вызове. Такие динамические изменения в величине данных часто именуются побочными эффектами. Благодаря им значение функции может изменяться, даже если ее аргументы и остаются без изменения всякий раз, когда к ней обращаются. Пример var flag: boolean; function f (n:integer):integer; begin if flag then f:=n else f:= 2*n; flag:=not flag end; begin flag:=true; writeln(f(1)+f(2); {будет напечатано 5} writeln(f(2)+f(1); {будет напечатано 4} end. В функции f имеется оператор присваивания, изменяющий значение перемен- ной flag, описанной в объемлющем блоке, и поэтому значение суммы, использу- ющей вызов функции f, зависит от порядка следования слагаемых. Функция f не является математической («чистой», в терминологии функционального програм- мирования) функцией. Операции, подобные этой, в математике не разрешены, по- скольку математические рассуждения базируются на идее равенства и возможности замены одного выражения другим, означающим то же самое, т. е. определяющим ту же величину. Побочный эффект приводит к трудноуловимым программным ошибкам и, следовательно, крайне нежелателен. 3.2.4 Распределение памяти для переменных Все глобальные переменные распределяются в памяти статически. Локальные переменные размещаются в памяти динамически, при активизации подпрограммы их содержащей; после выполнения подпрограммы память, отведенная для локаль- ных переменных, освобождается. Контрольные вопросы по главе 3 65 В некоторый момент выполнения программы в памяти может присутствовать несколько групп локальных переменных, соответствующих цепочке вызванных и не завершенных подпрограмм. В случае очередного вызова новая область памяти связывается с последней группой в цепочке; при завершении подпрограммы ее локальные переменные уда- ляются из хвоста цепочки. Этот принцип отведения и освобождения памяти соот- ветствует понятию стека (см. раздел 8.2.6). Слишком длинная цепочка вызовов — возникает ошибка «переполнения стека». Контрольные вопросы по главе 3 1. Пусть процедура maxmin(x, y) присваивает параметру x большее из ве- щественных чисел x и y, а параметру y — меньшее. А) Какие из параметров этой процедуры обозначают исходные данные, а какие — результаты? Какие параметры следуют объявить параметра- ми-значениями, а какие — параметрами-переменными? Б) Допустимы ли обращения maxmin (5.2, sin(z)) и maxmin(z, k), где z — вещественная переменная, а k — целая? В) Описать данную процедуру и использовать ее для перераспределения значений вещественных переменных a, b и c так, чтобы стало a ⩾ b ⩾ c. 2. Задача var a, b: real; t: boolean; Переменной t присвоить значение true, если уравнения x 2 + 6.2x + a 2 = 0 и x 2 +ax+b−1 = 0 имеют вещественные корни и при этом оба корня первого уравнения лежат между корнями второго, и присвоить значение false во всех остальных случаях. Какую подзадачу приходится решать в этой задаче несколько раз? Как сле- дует описать решение этой подзадачи — как функцию или как процедуру? Сколько у этой подпрограммы параметров? Каков их смысл? Какие из этих параметров — параметры-значения, а какие — параметры-переменные? |