Курс лекций для специальности «Прикладная математика» Первый семестр
| Вид материала | Курс лекций |
- Курс лекций для специальности Прикладная математика и информатика, 774.04kb.
- Календарный план лекций по курсу «математический анализ» Для специальности «Математика», 39.98kb.
- Рабочая программа, 160.99kb.
- Рабочая программа, 182.62kb.
- Цифровая обработка сигналов, 137.86kb.
- Курс лекций (28 часов) канд филос наук О. В. Аронсон Курс лекций «Математика и современная, 27.49kb.
- Урс «Численное решение обыкновенных дифференциальных уравнений» читает кафедра фн-2, 24.78kb.
- Курс IV семестр 8 Всего аудиторных занятий 52 Лекций, 117.53kb.
- Курс лекций в электронной форме содержит все лекции предусмотренные программой дисциплины, 32.88kb.
- Календарный план учебных занятий по обязательной дисциплине «Дискретная математика, 109.62kb.
Лекция 10
10.1 Процедуры и функции
При записи алгоритма на алгоритмическом языке высокого уровня (в том числе и на ТР) пользователю предоставляется возможность создавать в рамках разрабатываемой программы свои собственные операторы (процедуры) и операции (функции).
Процедуры и функции (подпрограммы) представляют собой записи на алгоритмическом языке частей алгоритма (подалгоритмов). В разделе описаний процедур и функций секции описаний программы помещаются тексты описания процедур и функций, в секции действий программы осуществляется обращение к процедурам и функциям программы (вызов процедур и функций).
Тексты описания подпрограмм устроены так же, как и сами программы – начинается описание с заголовка, затем идет секция описаний подпрограммы, затем секция действий подпрограммы. Причем в секции описаний подпрограммы могут быть описаны свои подпрограммы, обращение к которым осуществляется в секции действий подпрограммы. Поэтому было бы правильнее говорить не о программах и подпрограммах, а о вызывающих и вызываемых подпрограммах.
procedure <имя>(<формальные параметры>);{заголовок процедуры}
<секция описаний процедуры>
begin
<секция действий процедуры>
end;
function <имя>(<формальные параметры>):<тип>;{заголовок функции}
<секция описаний функции>
begin
<секция действий функции>
end;
Заголовок подпрограммы служит для организации обмена данными (параметрами) между программой и подпрограммой (исходные данные для работы подпрограммы и результаты работы подпрограммы). В функции один из результатов работы подпрограммы приписывается ее имени, тип результата (и функции) – <тип> – указывается в заголовке. В качестве типа <тип> может использоваться любой простой, строковой или ссылочный. В секции описаний подпрограммы приводятся описания локальных (внутренних) меток, констант, типов данных, переменных и подпрограмм, в секции действий подпрограммы записывается алгоритм работы подпрограммы. При обращении к подпрограмме указывается ее имя и фактические параметры.
Формальные параметры представляют собой список через «точку с запятой» предложений вида:
[var/const]<список переменных>:<имя типа>
Необязательные параметры var и const указывают способ передачи данных. Ключевое слово var означает, что данные передаются по адресу. Такие данные называются параметрами-переменными. Ключевое слово const означает, что данные передаются по адресу, но с защитой от изменения их значений. Такие данные называются параметрами-константами. Если перед списком переменных ключевое слово отсутствует, то данные передаются по значению. Такие параметры называются параметрами-значениями.
Обращение к подпрограммам осуществляется по следующей схеме:
Вызов процедуры (как самостоятельного оператора):
<имя>(<список фактических параметров>)
Вызов функции (в выражении, где допустим тип функции):
…<имя>(<список фактических параметров>)…
В качестве фактических параметров могут использоваться переменные, константы, выражения, в зависимости от способа передачи данных.
| Тип передачи | Ключевое слово | Фактический параметр |
| По значению | - | Любые выражения соответствующего типа |
| По адресу | var | Имена переменных |
| По адресу | const | Любые выражения соответствующего типа |
Между формальными (в описании подпрограммы) и фактическими (при обращении к подпрограмме) параметрами должно быть согласование по количеству, типам и порядку следования. (!)
Интерпретируя подпрограммы как подалгоритмы, можно считать параметры-значения исходными данными подалгоритма, а параметры-переменные результатами работы подалгоритма. Под параметры-значения подпрограммы отводится память в подпрограмме, в которую заносятся значения фактических параметров при вызове подпрограммы. Все действия подпрограммы над параметрами-переменными осуществляются непосредственно над переменными, являющимися фактическими параметрами. Поэтому значения, полученные параметрами-переменными в подпрограмме, будут доступны в вызывающей программе.
Параметры-константы целесообразно использовать в случаях, если требуется передавать структуры данных, занимающие большой размер памяти, но изменять исходные значения параметров с алгоритмической точки зрения недопустимо. В результате экономно используется оперативная память и одновременно гарантируется целостность исходных данных.
Вот примеры использования подпрограмм (процедур и функций) в Паскале:
1. Программа вычисляет величину y=max(min(x1,x2,x3),max(min(x3,x5,x4),x4))
program minmax;
var y,x1,x2,x3,x4,x5:real;
function max(a,b:real):real;
begin if a>b then max:=a else max:=b end;
function min(a,b:real):real;
begin if a
begin
readln(x1,x2,x3,x4,x5);
y:=max(min(x1,min(x2,x3)),max(min(x3,min(x5,x4)),x4));
writeln(y)
end.
Обратите внимание на порядок обращений к подпрограммам!
2. Программа подсчитывает количество символов ‘A’,’B’ и ‘C’ в введенной пользователем строке:
program ABC;
var s:string; i:integer;
procedure kolABC(s:string; var kolA,kolB,kolC:integer);
begin
kolA:=0; kolB:=0; kolC:=0;
for i:=1 to length(s) do
case s[i] do
‘A’: kolA:=kola+1;
‘B’: kolB:=kolB+1;
‘C’: kolC:=kolC+1;
end;
end;
begin
readln(s);
kolABC(s,kolA,kolB,kolC);
writeln(kolA,kolB,kolC);
end.
Функция ввода данного типа integer с защитой:
function enter_integer(s:string):integer;
var i,n:integer;
begin
repeat
readln(s);
val(s,n,i);
if i=0 then enter_integer:=n
until i=0;
end;
10.2 Передача параметров в процедуры и функции
Как было сказано выше (!), список фактических параметров должен соответствовать списку формальных параметров по количеству (очевидно), порядку следования (очевидно), по типу (как это?).
Если передача данных осуществляется по значению, то значение фактического параметра должно быть присвоено переменной, являющейся формальным параметром. Если передача данных осуществляется по адресу, то переменной, являющейся фактическим параметром, должно быть присвоено «новое» значение в подпрограмме. В любом случае необходима совместимость по присваиванию. Например, легко понять, что при описании формального параметра массива не может использоваться описатель массива вида array [Ind] of type, поскольку в вызывающей программе, в этом случае, невозможно описать переменную того же типа, то есть, совместимую с формальным параметром. Вот как следует поступать:
program factich_par;
type mass=array [1..10] of real;
var i:integer;
m:mass;
procedure pr_mass(m:mass);
var i:integer;
begin
for i:=1 to 10 do write(m[i]:10:5); writeln
end;
begin
for i:=1 to 10 do read(m[i]);
pr_mass(m)
end.
Указанный механизм передачи данных в подпрограмму позволяет обрабатывать в подпрограмме только массивы, определенного в вызывающей программе типа. Это хорошее «паскалевское» решение. В качестве некоего послабления (и отклонения от принципов строгой типизации данных) в ТР (не в стандарте!) можно воспользоваться следующим механизмом передачи массивов в подпрограмму, называемым «открытым массивом». При описании открытого массива указывается лишь базовый тип, в качестве фактического параметра может использоваться любой массив с тем же базовым типом, в качестве индексного типа используется диапазон 0..N, где N – номер максимального элемента индексного типа фактического параметра:
program Open_array;
var i:integer;
m:array [0..10] of real
procedure pr_mass(m:array of real;{Open array});
var i:integer;
begin
for i:=0 to 10 do write(m[i]:10:5); writeln
end;
begin
for i:=0 to 10 do read(m[i]);
pr_mass(m)
end.
10.3 Глобальные переменные. Перекрытие (экранирование)
Текст программы представляет собой блок, содержащий секцию описаний и секцию действий. Блоком можно считать и текст описания подпрограммы. Таким образом, можно текст программы на Паскале рассматривать как иерархию вложенных блоков.
Каждый объект (константа, тип данных, переменная или подпрограмма), описанный в программе на Паскале, имеет свою область «видимости» (соответствующее описание имеет свою область действия). Область действия описания начинается с места описания и заканчивается концом блока (оператором end), в котором выполнено описание. Для программы, структура которой условно изображена на схеме, подпрограмма А «видна» в любой части программы после ее описания. Подпрограмма В определена для секции действий программы. Подпрограммы А1 и А2 могут использоваться в секции действий подпрограммы А, причем подпрограмма А1 может быть использована в подпрограмме А2. Ни подпрограмма А1, ни подпрограмма А2 не могут выть использованы вне описания подпрограммы А. Подпрограмма А может быть вызвана в описании подпрограммы В (в секции действия В, или в секциях действия В1, В2, В21 и В22).
Аналогично определяется область действия описания типов данных, констант и переменных. Объект (подпрограмма, константа, тип данных или переменная) «виден» в тексте программы с места описания, до конца блока, в котором находится описание. Объект, использованный в блоке, входящем в область «видимости» его описания, называется глобальным по отношению к этому блоку. Использование глобальных объектов для обмена данными между программой и подпрограммой является альтернативой для механизма формальных и фактических параметров. Выбор способа передачи данных (для каких данных использовать механизм глобальных параметров, а для каких механизм формальных и фактических параметров) является одним из важнейших вопросов разработки проекта программы (не зависимо от того, на каком языке программирования будет реализован проект).
Внутри блока могут использоваться как глобальные, так и локальные объекты. К локальным объектам относятся формальные параметры и параметры, описанные внутри блока. Если локальный параметр совпадает по имени с одним из глобальных параметров, то глобальный параметр в данном блоке недоступен (правило экранирования). Внутреннее описание более сильное, оно перекрывает описание внешнего блока.
Program prog;
var i,x:integer; {глобальные переменные}
procedure p1(u:integer; var v:integer);
var i,y:integer; {локальные переменные}
begin
x:=1;
i:=2; y:=3;
writeln(x,i,y,u,v);
u:=7; v:=8;
end;
Begin
x:=0; i:=0;
writeln(x,i);
p1(i,i);
writeln(x,i);
end.
Результат работы программы:
00
12300
18
10.4 Процедурные типы
В TP можно использовать переменные процедурного типа. Переменные процедурного типа позволяют передавать в подпрограмму имена процедур и функций. Вот примеры описаний процедурных типов:
Type Proc1 = Procedure (a,b,c:real; var d:real);
Proc2 = Procedure (var a,b:real);
Func1 = Function: string;
Proc3 = Function (var s:string):real;
PROC = procedure; { процедура без параметров }
PROC4 = procedure (var x : real; y : integer);
FUN2 = function (x, y : real) : real;
var f : FUN2;
Переменную f можно использовать, например, так:
{$F+}{Использование дальней адресации}
function deg(a,b:real):real;
begin {вычисляем степень: a**b}
deg:=exp(ln(a)*b);
end;{deg}
{$F-}
begin {программа}
f := deg; writeln('2**15=',f(2,15));
end.
10.6 Рекурсия. Косвенная рекурсия
Функция вычисления факториала:
1. Рекуррентное определение
function Factor(n:integer):integer;
var i,f:integer;
begin
f:=1;
for i:=2 to n do f:=f*i;
Factor:=f;
end.
2.Рекурсивное определение
function Fact(n:integer):integer;
var f:integer;
begin
if n=0 then f:=1 else f:=Fact(n-1)*n
end.
При описании рекурсивной процедуры или функции используется сама процедура или функция. Для корректности такого описания необходимо выполнение двух условий:
- В алгоритме существует нерекурсивная ветка.
- Необходимо убедиться, что последовательность рекурсивных обращений к подпрограмме, выведет на нерекурсивную ветку алгоритма.
Работа рекурсивной функции вычисления факториала показано на слайдах (прилагаются).
Если при описании процедуры А используется процедура В, а при описании процедуры В используется процедура А, то такая ситуация называется косвенной рекурсией. Чтобы избежать синтаксических проблем при описании таких функций используют опережающее описание. Сначала приводят заголовок процедуры В с директивой FORWARD, а затем описывают тела процедур А и В, соответственно.