Для чего используются подпрограммы. Понятие подпрограммы

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

Подпрограмма - именованная, логически законченная группа операторов языка, которую можно вызвать для выполнения любое количество раз из различных мест программы. В языке Free Pascal существуют два вида подпрограмм: процедуры и функции. Главное отличие процедуры от функции заключается в том, что результатом исполнения операторов, составляющих тело функции , всегда является некоторое значение , поэтому функцию можно использовать непосредственно в выражениях, наряду с переменными и константами.

4.1 Общие сведения о подпрограммах. Локальные и глобальные переменные

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

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

Для правильного определения области действия идентификаторов (переменных) необходимо придерживаться следующих правил:

каждая переменная, константа или тип должны быть описаны перед использованием;
областью действия переменной, константы или типа является та подпрограмма, в которой они описаны;
все имена в пределах подпрограммы, в которой они объявлены, должны быть уникальными и не должны совпадать с именем самой подпрограммы;
одноимённые локальные и глобальные переменные - это разные переменные, обращение к таким переменным в подпрограмме трактуется как обращение к локальным переменным (глобальные переменные недоступны);
при обращении к подпрограмме доступны объекты, которые объявлены в ней и до её описания.

4.2 Формальные и фактические параметры. Передача параметров в подпрограмму

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

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

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

Формальные параметры процедуры можно разделить на два класса: параметры-значения и параметры-переменные.

При передаче данных через параметры-значения в подпрограмму передаются значения фактических параметров, и доступа к самим фактическим параметрам из подпрограммы нет. При передаче данных параметры-переменные заменяют 1Реально в подпрограмму передаются адреса фактических параметров. формальные параметры, и, следовательно, в подпрограмме есть доступ к значениям фактических параметров. Любое изменение параметров-переменных в подпрограмме приводит к изменению соответствующих им формальных параметров. Следовательно, входные данные следует передавать через параметры-значения, для передачи изменяемых в результате работы подпрограммы данных следует использовать параметры-переменные.

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

4.3 Процедуры

Описание процедуры имеет вид:

procedure имя_процедуры(список_формальных_параметров); label список_меток; const список_констант; type список_типов; var список_переменных; begin //Тело процедуры. end;

Описание начинается с заголовка процедуры, где procedure - ключевое слово языка, имя_процедуры - любой допустимый в языке Free Pasacal идентификатор , список_формальных_параметров - имена формальных параметров и их типы, разделённые точкой с запятой. Рассмотрим примеры заголовков процедур с параметрами-значениями:

procedure name_1(r: real ; i: integer ; c: char );

Однотипные параметры могут быть перечислены через запятую:

procedure name_2(a, b: real ; i, j, k: integer );

Список формальных параметров необязателен и может отсутствовать:

procedure name_3;

Если в заголовке процедуры будут применяться параметры-переменные, то перед ними необходимо указывать служебное слово var :

procedure name_4(x, y: real ; var z: real );

//x, y - параметры-значения,

//z - параметр - переменная .

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

Для обращения к процедуре необходимо использовать оператор вызова:

имя_процедуры(список_фактических_параметров);

Фактические параметры в списке оператора вызова отделяются друг от друга запятой:

a: = 5. 3; k: = 2; s:= ’ a ’;

name_1(a, k, s);

Если в описании процедуры формальные параметры отсутствовали, то и при вызове их быть не должно:

ЗАДАЧА 4.1. Найти действительные корни квадратного уравнения .

Алгоритм решения этой задачи был подробно описан в задаче 3.3 (рис. 3.14). Однако там не была рассмотрена ситуация некорректного ввода значений коэффициентов. Например, если пользователь введёт , то уравнение из квадратного превратится в линейное. Алгоритм решения линейного уравнения тривиален: , при условии, что . Чтобы не усложнять уже составленный алгоритм решения квадратного уравнения, запишем его в виде подпрограммы-процедуры. Далее приведён фрагмент программы с комментариями:

//Процедура для вычисления действительных //корней квадратного уравнения. procedure korni (a, b, c: real; var x1, x2: real; var pr: boolean); //Входные параметры процедуры: //a,b,c - коэффициенты квадратного уравнения; //Выходные параметры процедуры: //x1,x2 - корни квадратного уравнения, //pr - логическая переменная, //принимает значение "ложь", если в уравнении нет корней, //и значение "истина" в противном случае. var d: real; begin d:=b * b-4 * a * c; if d<0 then pr:= false else begin pr:= true; x1:=(-b+sqrt (d)) / 2 / a; x2:=(-b-sqrt (d)) / (2 * a); end end; //Конец подпрограммы //Основная программа var a_, b_, c_, x1_, x2_, x_ : real; pr_ : boolean; begin write (’a_:= ’); readln (a_); write (’b_:= ’); readln (b_); write (’c_:= ’); readln (c_); if a_=0 then //Если а=0, то уравнение //квадратным не является. begin //Решение линейного уравнения bx+c=0. if b_<>0 then begin x_:=-c_/b_; writeln (’ x= ’,x_); end else writeln (’Нет корней ’); end else //Решение квадратного уравнения ax^2 + bx + c = 0. begin korni (a_, b_, c_, x1_, x2_, pr_); //Вызов процедуры. if pr_=false then writeln (’Нет корней ’) else writeln (’ x1= ’,x1_, ’ _x2= ’,x2_); end; end.

ЗАДАЧА 4.2. Вводится последовательность из целых положительных чисел. В каждом числе найти наибольшую и наименьшую цифры.

Для решения задачи создадим процедуру max_min , результатом работы которой будут два значения: минимальная и максимальная цифры в заданном числе.

Текст программы:

//Процедура возвращает //max наибольшую и min наименьшую цифры в числе M. //В списке параметров: //M параметр-значение (входной параметр), //max и min параметры-переменные (выходные параметры). procedure max_min(M: longint; var max: byte; var min: byte); var i: byte; begin i: = 1; while M div 10>0 do begin if i =1 then begin //Предположим, что первая цифра является max:=M mod 10; //наибольшей или min:=M mod 10; //наименьшей. i:= i +1; end; //Поиск цифры больше max или меньше min. if M mod 10 > max then max:=M mod 10; if M mod 10 < min then min:=M mod 10; M:=M div 10; end; end; var X: longint; N, i,X_max, X_min: byte; begin //Количество элементов в последовательности. write (’N= ’); readln (N); for i:=1 to N do begin write (’X= ’); readln (X); //Элемент последовательности. if X>0 then //Если элемент положительный, то begin max_min(X,X_max, X_min); //вызов процедуры. //Печать результатов. writeln (’ max= ’,X_max, ’ min= ’,X_min); end; end; end.

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

Подпрограмма — это фрагмент кода, который имеет свое имя и создается в случае необходимости выполнять этот код несколько (много) раз. Подпрограмма описывается единожды перед началом основной программы (до begin). Компилятор пропускает данный фрагмент кода, пока в основной программе не встретит «вызов» подпрограммы, который выглядит как обращение к ней по имени (возможно, имени с аргументами, указанными в скобках).

Во многих языках программирования подпрограммы существуют только в виде функций. Однако в Паскале подпрограмма — и функция и процедура . Разница между ними станет очевидна в данном уроке.

Итак, рассмотрим синтаксис объявления и описания процедуры в Паскале

var …;{область объявления глобальных переменных} procedure название (параметры); {начало процедуры} var …;{объявление локальных переменных} begin … {тело процедуры} end;{конец процедуры} begin … {основная программа} end.

Пример: Процедура без параметров, которая печатает 60 звездочек, каждую с новой строки

procedure pr; var i:integer; begin for i:=1 to 60 do begin {тело подпрограммы} write("*"); writeln; end; end; {конец подпрограммы} begin pr; {вызов процедуры} end.

В данном примере работы с процедурой в Паскале очевидно, что компилятор пропустит блок описания процедуры и дойдет до основной программы (9 строка кода). И только после того, как встретится вызов процедуры (10 строка), компилятор перейдет к ее выполнению, вернувшись к строке 1.

Процедуры с параметрами. Фактические и формальные параметры

Рассмотрим пример необходимости использования процедуры.

Пример:
Построить фигуру

Особенность: Три похожие фигуры.

общее: размеры, угол поворота

отличия: координаты, цвет

Алгоритм решения:

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

Решение на паскале:
Процедура:

Программа:

uses GraphABC; procedure Tr( x, y: integer ; color: system. Drawing . Color ) ; begin MoveTo(x, y) ; LineTo(x, y- 60 ) ; LineTo(x+ 100 , y) ; LineTo(x, y) ; FloodFill(x+ 20 , y- 20 , color) ; end ; begin SetPenColor(clBlack) ; Tr(100 , 100 , clBlue) ; Tr(200 , 100 , clGreen) ; Tr(200 , 160 , clRed) ; end .

uses GraphABC; procedure Tr(x, y: integer; color:system.Drawing.Color); begin MoveTo(x, y); LineTo(x, y-60); LineTo(x+100, y); LineTo(x, y); FloodFill(x+20, y-20,color); end; begin SetPenColor(clBlack); Tr(100, 100, clBlue); Tr(200, 100, clGreen); Tr(200, 160, clRed); end.

Рассмотрим синтаксис объявления и описания процедуры с параметрами в Паскале.

var …;{область объявления глобальных переменных} procedure pr(параметр1, параметр2: integer; параметр3:char); {начало процедуры} var …;{объявление локальных переменных} begin … {тело процедуры} end;{конец процедуры} begin … {основная программа} pr (параметр1, параметр2, параметр3); {вызов процедуры} end.

Задание procedure 1: N вертикальных линий. N задается параметром процедуры.

Задание procedure 2: Написать процедуру рисования N окружностей, сдвинутых по горизонтали. N , радиус R и отступ O задаются параметрами процедуры (всего 3 параметра).

Пример: Написать процедуру, которая печатает 60 раз указанный символ (введенный с клавиатуры), каждый с новой строки

Параметры процедуры (в некоторых языках они называются аргументами) указываются в скобках после ее имени (в объявлении).

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14

var s: char ; procedure pr(a: char ) ; {a - формальный параметр} var i: integer ; begin for i: = 1 to 60 do begin write (a) ; writeln ; end ; end ; begin writeln ("simvol" ) ; readln (s) ; pr(s) ; {s - фактический параметр} end .

var s:char; procedure pr(a:char); {a - формальный параметр} var i:integer; begin for i:=1 to 60 do begin write(a); writeln; end; end; begin writeln("simvol"); readln(s); pr(s); {s - фактический параметр} end.

В данном примере при вызове процедуры компилятор заменит формальный параметр a фактическим параметром s , т.е. тем символом, который будет введен с клавиатуры. Оба параметра имеют тип данных char .

Задача procedure 3. Написать процедуру, которая складывает два любых числа (два параметра).

Процедуры с параметрами. Параметр-переменная

способ:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

var x, y, m, n: integer ; procedure MaxNumber(a, b: integer ; var max: integer ) ; {a и b - параметры значения, max - параметр-переменная} begin if a>b then max: = a else max: = b; end ; begin write ("vvedite x,y" ) ; readln (x, y) ; MaxNumber(x, y, m) ; {фактические параметры} writeln ("max=" , m) end .

var x,y,m,n:integer; procedure MaxNumber(a,b:integer;var max:integer); {a и b - параметры значения, max - параметр-переменная} begin if a>b then max:=a else max:=b; end; begin write("vvedite x,y"); readln(x,y); MaxNumber(x,y,m); {фактические параметры} writeln("max=",m) end.

В примере формальные параметры a и b служат для помещения в них сравниваемых чисел, а параметр-переменная max — для сохранения в ней максимального из двух чисел. Параметр-переменная или выходной параметр передает свое значение в основную программу (фактическому параметру m), т.е. возвращает значение, тогда как формальные параметры-значения (входной параметр), наоборот, принимают значения из основной программы (из фактических параметров x и y). Для параметра-переменной (max) используются те ячейки памяти, которые отведены под соответствующий параметр при вызове процедуры (ячейка m).

Таким образом, сформулируем понятия:

Если в качестве формального параметра указана обычная переменная с указанием ее типа, то такой параметр есть параметр-значение или входной параметр (a и b в примере). Тип данных формального параметра-значения должен соответствовать типу данных его фактического параметра (a и b должны попарно соответствовать типу данных x и y).

Если перед именем формального параметра в объявлении процедуры стоит служебное слово var , то такой параметр называется параметром-переменной или выходным параметром (max в примере). Для него используются те ячейки памяти, которые отведены под соответствующий параметр при вызове процедуры (m). Фактический параметр, соответствующий параметру-переменной, может быть только переменной (не константой, не литералом и не выражением).

способ:

Использование параметров-переменных позволяет тратить меньше памяти

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

var x, y: integer ; procedure exchange(a: integer ; var b: integer ) ; {b - параметр-переменная или выходной параметр} var c: integer ; begin if a>b then begin c: = a; a: = b; b: = c; {второй параметр процедуры - b - всегда будет максимальным} end ; end ; begin writeln ("введите два числа" ) ; readln (x, y) ; exchange (x, y) ; writeln ("max=" , y) end .

var x,y:integer; procedure exchange(a: integer;var b:integer); {b - параметр-переменная или выходной параметр} var c:integer; begin if a>b then begin c:=a; a:=b; b:=c; {второй параметр процедуры - b - всегда будет максимальным} end; end; begin writeln("введите два числа"); readln(x,y); exchange (x,y); writeln("max=",y) end.

Используя данный способ решения задачи, мы обошлись без третьего параметра. Для этого в процедуре мы использовали еще одну локальную переменную c . Процедура меняет значения переменных a и b таким образом, чтобы b всегда была максимальной. Поэтому в 15 строке программы в качестве максимальной выводится второй параметр (y), соответствующий формальному параметру b .

Задача procedure 4.

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

Словесный алгоритм:

Вводятся a и b (например, 18 и 24 )
В цикле повторяем действия:
Если а < b , то меняем переменные местами (1 шаг: a=24 , b=18 ; 2 шаг: a=18 , b=6 )
Переменной a присваиваем остаток от деления a на b (1 шаг: a=6 , b=18 ; 2 шаг: a=0 , b=6 )
Когда остаток равен 0 , выводится результат (значения переменной b ) (b=6 )

Алгоритм решения поиска НОД:

Задача procedure 5. Используя процедуры, построить фигуру:

Задача procedure 6. Даны 3 различных массива целых чисел (размер каждого 15 элементов). В каждом массиве найти и среднее арифметическое значение.
Для формирования элементов массива и подсчета суммы и среднего арифметического использовать одну процедуру (среднее арифметическое и сумму оформить как параметры-переменные).

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

Пример: Создать процедуру для вывода десяти элементов массива (два параметра: количество элементов, массив)

Показать решение:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

const n = 10 ; var i: integer ; a, b: array [ 1 .. n ] of integer ; procedure arr_out (k: integer ; arr: array [ 1 .. n ] of integer ) ; var i: byte ; begin write ("вывод массива: " ) ; for i : = 1 to k do write (arr[ i] : 4 ) ; writeln ; end ; begin for i: = 1 to n do a[ i] : = random(10 ) ; arr_out (n, a) ; end .

const n = 10; var i:integer; a, b: array of integer; procedure arr_out (k:integer; arr: array of integer); var i: byte; begin write ("вывод массива: "); for i:= 1 to k do write (arr[i]:4); writeln; end; begin for i:=1 to n do a[i]:=random(10); arr_out (n, a); end. integer ; procedure arr_rand (k: integer ; var arr: array [ 1 .. n ] of integer ) ; var i: byte ; begin write ("Заполнение массива случайными числами " ) ; randomize; for i : = 1 to k do arr[ i] : = random(100 ) ; end ; begin arr_rand (n, a) ; end .

const n = 10; var a, b: array of integer; procedure arr_rand (k:integer; var arr: array of integer); var i: byte; begin write ("Заполнение массива случайными числами "); randomize; for i:= 1 to k do arr[i]:=random(100); end; begin arr_rand (n, a); end.

Задача procedure 7. Объедините обе решенные задачи (для заполнения и вывода массива).

Задача procedure 8. Добавьте в задачу процедуру для заполнения значений массива пользователем (ввод значений с клавиатуры). Оформите вывод двух разных массивов: один — со значениями, сформированными случайным образом, другой — со значениями, введенными пользователем.

Задача procedure 9. Составить программу с процедурой для вычисления (входные параметры: число и степень). Для вывода результата использовать параметр-переменную.

Самостоятельная работа

1 вариант: для 5 одномерных массивов определять произведение элементов каждого массива, используя процедуру с двумя параметрами - число элементов массива и параметр-переменная для вывода произведения.

2 вариант: для 5 одномерных массивов определять минимальный элемент каждого массива, используя процедуру с двумя параметрами - число элементов массива и параметр-переменная для вывода минимального элемента.

* сложное С помощью процедуры формировать случайным образом одномерные массивы из 10 элементов (значения от -20 до +20). Вызывать процедуру до тех пор, пока среди значений не появится ноль.

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

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

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

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

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

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

Подпрограмма с параметрами используется для записи многократно повторяющихся действий при разных исходных данных. Подпрограммы с параметрами можно разделить на два типа: подпрограммы-функции и просто подпрограммы с параметрами (их называют процедурами).

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

2) процедура из основной программы вызывается командой вызова, которая по форме ничем не отличается от вызова команды исполнителя. Результат присваивается одной или нескольким переменным, которые находятся в списке формальных параметров. Но результатом могут быть, конечно, не только значения переменных, но какое либо действие, выполненное ЭВМ.

Пример 1. Используем алгоритм нахождения наибольшего общего делителя двух натуральных чисел в качестве вспомогательного при решении задачи: составить программу вычитания дробей (a, b, c, d - натуральные числа). Результат представить в виде обыкновенной несократимой дроби.

Подпрограмма.

1) Ввести натуральные числа M, N.

2) Если M=N, перейти к п. 5, иначе к следующему пункту.

3) Если M>N, то M:=M-N, иначе N:=N-M.

4) Перейти к п. 2.

5) Передать значение M в основную программу.

6) Конец подпрограммы.

Основная программа.

1) Ввести значения A, B, C, D.

2) E:=A*D - B*C.

4) Если E=0, вывести значение E и перейти к п. 9, иначе перейти к следующему пункту.

5) M:=|E|, N:=F, перейти к подпрограмме вычисления НОД.

7) E и F нацело разделить на G.

8) Вывести значения E и F на печать.

9) Конецпрограммы.

Var A, B, C, D, G, E, F: Integer;

Procedure Nod(M, N: Integer; Var K: Integer);

While M <> N Do

If M >

Write("Введите числители и знаменатели дробей:");

ReadLn(A, B, C, D);

E:= A * D - B * C;

If E = 0 Then WriteLn(E)

Nod(Abs(E), F, G);

WriteLn("Ответ: ", E, "/", F)

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

Вызов процедуры осуществляется следующим образом:

<Идентификатор (имя) процедуры>(<список фактических параметров>);

Например,

Nod(Abs(E), F, G);

По способу передачи фактических значений в подпрограмму в Turbo Pascal 7.0 выделяют параметры-переменные, параметры-значения, параметры-константы и массивы открытого типа, строки открытого типа, параметры-процедуры, параметры-функции (подробности - в литературе).

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

Покажем, как изменится подпрограмма из примера, если ее записать в виде функции.

Function Nod(M, N: Integer) : Integer;

While M <> N Do

If M > N Then M:= M - N Else N:= N - M;

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

Вызов функции будет следующим:

G:= Nod(Abs(E), F);

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

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

Пример 2. Дано натуральное число n. Переставить местами первую и последнюю цифры этого числа.

If Impossible(N)

Then WriteLn("Невозможно переставить цифры, возникнет переполнение")

WriteLn("Ответ: ", N)

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

Function Impossible(N: Integer) : Boolean;

If Number(N) < 5

Then Impossible:= False

Else Impossible:= (N Mod 10 > 3) Or

(N Mod 10 = 3) And

(N Mod 10000 Div 10 * 10 + N Div 10000 > MaxInt Mod 10000)

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

Function Number(N: Integer) : Integer;

Var Vsp: Integer;

While N > 0 Do

Vsp:= Vsp + 1; N:= N Div 10

Наконец, последняя процедура.

Procedure Change(Var N: Integer);

Var Kol, P, S, R: Integer;

Kol:= Number(N);

P:= N Mod 10; {последняяцифра}

If Kol > 1 Then

S:= N Div Round(Exp((Kol - 1) * Ln(10)))

Else S:= 0; {перваяцифра}

R:= N Mod Round(Exp((Kol - 1) * Ln(10))) Div 10;

N:= P * Round(Exp((Kol - 1) * Ln(10))) + R * 10 + S

Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными. Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.

Пример 3. Найти максимальную цифру в записи данного натурального числа.

Program MaxDigit;

Type NaturLong = 1..(High(LongInt));

Function Maximum(N: LongInt) : Digit;

Then Maximum:= N

Else If N Mod 10 > Maximum(N Div 10)

Then Maximum:= N mod 10

Else Maximum:= Maximum(N Div 10)

Write("Введите натуральное число: ");

WriteLn("Максимальнаяцифраравна ", Maximum(A))

При создании функции Maximum было использовано следующее соображение: если число состоит из одной цифры, то она является максимальной, иначе если последняя цифра не является максимальной, то ее следует искать среди других цифр числа. При написании рекурсивного алгоритма следует позаботиться о граничном условии, когда цепочка рекурсивных вызовов обрывается и начинается ее обратное «раскручивание». В нашем примере это условие N < 10.

Более подробно о рекурсии говорится в следующей статье.

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

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

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

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

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

При составлении подпрограмм с параметрами надо соблюдать следующие правила:

1) каждая подпрограмма имеет свое имя и список формальных параметров;

Пример 1. Используем алгоритм нахождения наибольшего общего делителя двух натуральных чисел в качестве вспомогательного при решении задачи: составить программу вычитания дробей (a , b , c , d натуральные числа). Результат представить в виде обыкновенной несократимой дроби.

Подпрограмма.

Ввести натуральные числа M, N.
Если M=N, перейти к п. 5, иначе к следующему пункту.
Если M>N, то M:=M-N, иначе N:=N-M.
Перейти к п. 2.
Передать значение M в основную программу.
Конец подпрограммы.

Основная программа.

Ввести значения A, B, C, D.
E:=A*D - B*C.
F:= B*D.
Если E=0, вывести значение E и перейти к п. 9, иначе перейти к следующему пункту.
M:=|E|, N:=F, перейти к подпрограмме вычисления НОД.
G:= M.
E и F нацело разделить на G.
Вывести значения E и F на печать.
Конец программы.

Как видно из примера, объявление подпрограммы-функции находится в разделе описаний прототипов функций, а реализация после основной функции main . В заголовке подпрограммы содержится список формальных параметров с указанием их типа, которые условно можно разделить на входные и выходные (перед ними стоит &). Вообще при обращении к функции со списком параметров без &, внутри функции используются копии параметров, которые после выполнения удаляются. Знак & указывает компилятору что необходимо использовать саму переменную, а не ее копию. При обращении к функции указывается ее имя и список фактических параметров. Формальные и фактические параметры должны соответствовать по количеству и по типу.

Описание функции в С++ осуществляется следующим образом:

Тип_возвращаемого_значения ();

Например,

Void Nod(int e, int f, int &k); int f1(float a); long f2();

Функция всегда возвращает единственное значение. Как видно из примера 1, мы использовали тип void в качестве возращаемого типа. Т.е. указали компилятору, что наша функция не возвращает никакого значения.

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

Int Nod(int m, int n) { while (m!=n) if (m > n) m -=n; else n -= m; return (n); }

Итак, в теле функции хотя бы один раз встречается команда return, которая указывает, какое значение вернуть в качестве значения функции.

Вызов функции в основной будет следующим:

G = Nod(fabs(e), f);

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

При решении задач целесообразно проанализировать условие, записать решение в крупных блоках (не являющихся операторами C++), детализировать каждый из блоков (записав в виде блоков, возможно, по-прежнему не операторов C++), и т.д., продолжать до тех пор, пока каждый из блоков не будет реализован с помощью операторов языка.

Пример 2. Дано натуральное число n . Переставить местами первую и последнюю цифры этого числа.

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

Возможны также подпрограммы, которые вызывают сами себя. Они называются рекурсивными . Создание таких подпрограмм является красивым приемом программирования, но не всегда целесообразно из-за чрезмерного расхода памяти ЭВМ.

Пример 3. Найти максимальную цифру в записи данного натурального числа.

Более подробно о рекурсии говорится в следующей статье .

Контрольные вопросы и задания

Какие алгоритмы называют вспомогательными?
Какое количество вспомогательных алгоритмов может присутствовать в основном алгоритме?
Можно ли вспомогательные алгоритмы, написанные для решения данной задачи, использовать при решении других задач, где их применение было бы целесообразно?
Какие параметры называют формальными? фактическими?
Какое соответствие должно соблюдаться между формальными и фактическими параметрами?
Может ли фактических параметров процедуры (функции) быть больше, чем формальных? А меньше?
Существуют ли подпрограммы без параметров?
Существуют ли ограничения на число параметров подпрограмм? Если нет, то чем же всё-таки ограничивается это количество в С++?
В каком разделе объявляются и в каком реализуются подпрограммы в С++?
Какого типа может быть значение функции?
Расскажите о методе последовательной детализации при разработке программ.
Какие подпрограммы называют рекурсивными?
Что такое граничное условие при организации рекурсивной подпрограммы?

Глава 17. Команды вызова процедур

Что такое подпрограмма

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

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

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

На рис. 17.1а показан пример использования подпрограммы. В данном примере имеется основная программа, которая размещена в оперативной памяти, начиная с адреса 4000. В основной программе существует вызов подпрограммы PROC1, которая размещена в оперативной памяти, начиная с адреса 4500. Когда в процессе выполнения основной программы ядро процессора дойдет до этой команды, оно прервет выполнение основной программы и перейдет на выполнение подпрограммы PROC1, поместив ее начальный адрес 4500 в счетчик команд. В теле подпрограммы PROC1 есть две команды вызова подпрограммы PROC2, которая размещена в оперативной памяти, начиная с адреса 4800. Дойдя до каждой из этих команд, ядро процессора прекратит выполнять подпрограмму PROC1 и перейдет на выполнение подпрограммы PROC2. Встретив в подпрограмме команду RETURN, ядро процессора вернется в вызывающую программу и продолжит ее выполнение с команды, следующей за командой CALL, которая вызвала переход на только что завершенную подпрограмму. Этот процесс схематически показан на рис. 17.1.6.

Необходимо обратить внимание на следующие моменты:

подпрограмма может быть вызвана из любого места других программных
модулей. Таких вызовов может быть сколько угодно.

одна подпрограмма может быть вызвана из другой, которая, в свою очередь, вызвана третьей. Это называется вложенностью (nesting) вызовов. Глубина вложенности теоретически может быть произвольной.

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

Рис. 17.1. Вложенный вызов подпрограмм:

а - команды вызова и возврата; б - последовательность выполнения команд

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

регистр процессора;

начальный адрес подпрограммы;

верхняя ячейка стека.

Рассмотрим машинную команду CALL X, которая интерпретируется как "вызов подпрограммы, расположенной по адресу X". Если для хранения адреса возврата использовать регистр Rn, то выполнение команды CALL X должно проходить следующим образом (PC - счетчик команд ядра процессора):

В этой записи D - длина текущей команды. Затем адрес возврата оказывается в регистре Rn, откуда его может извлечь вызванная подпрограмма и сохранить где-либо в оперативной памяти для выполнения в дальнейшем возврата в вызывающую программу.

Если будет принято решение сохранять адрес возврата по начальному адресу вызываемой подпрограммы, то при выполнении команды CALL X ядру процессора нужно будет выполнять следующие операции:

Это довольно удобно, поскольку адрес возврата всегда сохраняется в месте, точно известном подпрограмме (точнее, ее разработчику).

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

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

Стеки

Стек - это список элементов данных, обычно слов или байтов, доступ к которым ограничен следующим правилом: элементы этого списка могут добавляться только в его конец и удаляться только из конца. Конец списка называется вершиной стека, а его начало - дном. Такую структуру иногда называют магазином. Представьте себе стопку подносов в столовой. Клиенты берут подносы сверху, работники столовой, добавляя чистые подносы, тоже кладут их на верх стопки. Этот механизм хранения хорошо описывается емкой фразой «последним вошел - первым вышел» (Last In First Out, LIFO), означающей, что элемент данных, помещенный в стек последним, удаляется из него первым. Операцию помещения нового элемента в стек часто называют его проталкиванием (push), а операцию извлечения последнего элемента из стека называют его выталкиванием (pop).

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

На рис. 17.2 показано, как располагается в памяти компьютера стек, элементы которого занимают по одному слову.

На «дне» он содержит числовое значение 43, а на вершине - 28. Для отслеживания адреса вершины стека используется регистр ядра процессора, называемый указателем стека (Stack Pointer, SP). Это может быть один из регистров общего назначения или же регистр, специально предназначенный для этой цели.

Рис. 17.2. Стек слов в оперативной памяти

Если предположить, что оперативная память адресуется побайтно и слово имеет длину 32 разряда, операцию проталкивания в стек можно реализовать так:

Move NEWITEM.(SP),

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

Эти две команды перемещают значение, хранившееся на вершине стека, в другое место оперативной памяти, по адресу ITEM, а затем уменьшают указатель стека на 4, чтобы он указывал на тот элемент, который теперь располагается на вершине стека. Результат выполнения каждой из этих операций для стека, показанного на рис. 17. 2, приведен на рис. 17.3.

Рис. 17.3. Результат выполнения операций со стеком

Если в архитектуре поддерживаются режимы автоинкрементной и автодекрементной адресации, для помещения нового элемента в стек достаточно команды

Move NEWITEM,-(SP),

а выталкивание элемента из стека можно выполнить посредством команды

Move (SP)+,ITEM.

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

Предположим, что стек заполняется, начиная с адреса 2000 (BOTTOM) до 1500 и далее. Первоначально в регистр, играющий роль указателя стека, загружается значение 2004. Напомним, что перед помещением в стек нового элемента данных из значения SP каждый раз вычитается 4. Поэтому начальное значение 2004 означает, что первый элемент стека будет иметь адрес 2000. Для предотвращения попыток помещения элемента в полный стек или удаления элемента из пустого стека нужно несколько усложнить реализацию операций проталкивания и выталкивания элемента. Для выполнения каждой из этих операций указаннойвыше команды недостаточно - ее нужно заменить последовательностью команд, приведенной в таблице 17.1.

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

Таблица 17.1

Метка

Команда

Операнды