В даній програмі, якщо множина не надавати початкового значення, то вона приймається пустою, тому попередньо до Формування множини с їй потрібно надати початкове значення, що рівне повній множині.

ТЕМА: Підпрограми

Структурне програмування передбачає представлення програм у вигляді послідовності викликів підпрограм. В свою чергу останні теж можуть структуруватися на елементарні підпрограми.

Поняття підпрограми означає логічно-завершальну програму компоненту, що виконує деяку частину алгоритму.

Ford-RAN були звичайними частинами програми. Вони не мали механізму передачі параметрів і користувалися загальновживаними змінними.

Використання механізму передачі параметрів (МПП) дозволило зробити окремі підпрограми більш незалежними. Це полегшило використанні програми та її відланку.

В Pascal є два види підпрограм:

1. Процедури являють собою дію, тому їх можна використовувати в якості окремого оператора в розділі операторів програми.

2. Функції являють собою значення певного типу, крім цього вони можуть використовувати деяку дію, але значення їх є головним. Тому функції використовують як окремі оператори у виразах.

Оголошуються процедури і функції у розділі оголошень, причому оголошення

Формальне оголошення процедур має вигляд:

PROCEDURE <ім’я> (<список формальних параметрів>);

<розділ оголошень>;

<тіло процедури>;

Ім’я процедури формується згідно з правилами побудови ідентифікаторів у Pascal.

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

Розділ оголошень містить описи всіх об’єктів, що використовуються лише у цій підпрограмі.

Тіло підпрограми містить оператори, що об’єднуються операторними дужками.

FUNCTION (<список формальних параметрів>:)<тип результату>;

<розділ оголошень>;

<тіло функції>;

На відмінну від процедур у функції обов’язково задається тип її значення. В якості типу результату можуть бути скалярні типи, рядки, множини, вказівники.

В розділі операторів обов’язково повинен бути присутній хоча б один оператор присвоєння ідентифікатору функції деякого значення, що і буде результатом функції.

Наприклад

Процедура і функція, що обчислюють суму елементів масиву цілих чисел.

CONST n=5;

TYPE

masiv=array[1..n] of integer;

PROCEDURE P_SUMA(a: masiv; m:integer; var suma: integer);

VAR

i: byte;

BEGIN

suma:=0;

for i:=1 to m do

suma:=suma+a[i]

END;

FUNCTION F_SUMA(a:masiv; m:integer): integer;

VAR

i: byte;

s: integer;

BEGIN

s:=0;

for i:=1 to m do

s:=s+a[i];

F_SUMA:=s;

END;

 

Процедура має три параметри: два вхідні – масив а і кількість т і один вихідний – сума.

Розділ оголошень локальних містить і типу byte.

Тіло процедури складається з двох операторів

Через значення функції типу integer локальне оголошення містить дві змінних. Тіло функції містить оператор присвоєння.

При фактичному виклику оголошених підпрограм результат можна отримати таким чином.

VAR

aa: masiv;

c, j: integer;

BEGIN

for j:=1 to n do

readln(aa[i]);

P_SUMA (aa, n, c);

c:= F_SUMA(aa,n);

Механізм передачі параметрів

При звернені до підпрограми, їм можуть передувати в якості вхідних даних деякі значення, крім того деякі вхідні дані можуть змінювати своє значення в тілі підпрограми і можуть повертатися в якості вихідних.

В Pascal використовується три види параметричних підпрограм;

1. Параметри-значення.

2. Параметри-змінні.

3. Без типові параметри.

Задання виду параметрів здійснюється формальним оголошенням заголовку підпрограм.

1. Параметри-значення

Параметри-значення виступають в якості вхідних параметрів, тобто їх значення передається у підпрограму і в процесі її виконання не може змінюватися.

Оголошуються такі параметри шляхом переліку формальних ідентифікаторів та заданням їхнього параметру.

Оскільки значення таких параметрів не змінюється, то при фактичному виклику підпрограми в якості фактичних параметрів-значень можуть бути змінні, константи, зображення певного типу.

Наприклад

Програма, що реалізує операції над комплексними числами.

TYPE

Complex=record

Re, Im:real;

END;

PROCEDURE SUMA (a, b: complex; var c:complex);

BEGIN

c:=a.Re +b.Re;

c:=a.Im+b.Im;

END;

BEGIN

…

a.Re:=2;

a.Im:=2;

b.Re:=1;

b.Im:=-2;

SUMA (a,b,c);

END.

При формальному оголошенні процедури. Перші два параметри є параметрами-значеннями.

В тілі процедури описаний алгоритм у вигляді послідовності операторів. В програмі оголошено три змінні a, b, c, яким надаються двом із них.

При фактичному виклику процедури сума їй передаються в якості вхідних параметрів значення змінних a,b, результат змінна с.

В якості фактичних параметрів можуть використовуватися будь-які ідентифікатори типу complex.

Фактичні параметри можуть бути будь-які об’єкти програми, тип яких відповідає типу формальних параметрів.

2. Параметри-змінні

Виступають в якості вихідних параметрів. Це означає, що їх початкове значення може змінюватися у тілі підпрограми і ця зміна повертається в точку виклику підпрограми.

Таким чином при фактичному виклику підпрограми в якості фактичних параметрів змінних можуть використовуватися лише змінні.

Оголошуються парамерти змінних при допомозі var і переліку ідентифікаторів та задання їх типу, якщо підпрограма має декілька параметрів змінних при формальному оголошенні, кожному з них повинен передувати var.

В попередньому прикладі параметром змінної була змінна с.

Наприклад

сумування дійсних чисел.

PROCEDURE SUMA_RITH (a, b:real; var s:real; var r:real);

BEGIN

s:=a+b;

r:=a-b;

END;

VAR x, y, z, t:real;

BEGIN

x:=5; y:=2;

SUMA_RETH(x,y,z,t);

SUMA_RITH(4,3,z,t);

END;

В одному прикладі є два параметри змінних, які формально позначенні s та r, при фактичному виклику їх використовують як змінні t, z.

Параметри змінних можуть виконувати функцію вхід і вихід параметрів одночасно. Результат суми зберігається в першому аргументі, а різниця в другому.

PROCEDURE P (var a:real; var b:real);

var x:real;

BEGIN

x:=a;

a:=a+b;

b:=x-b

END;

VAR x,y:real;

BEGIN

x:=5; y:=3;

P(x,y);

END;

Якщо параметр-змінна виконує функцію вхідного параметра, то при фактичному виклику можна використовувати лише змінні.

В даній процедурі оголошена своя змінна х для тимчасового збереження одного із вхідних даних, така змінна – локальна і використовується лише у межах даної підпрограми.

Час її існування при виконані програми теж є тимчасовим, лише під час виконання підпрограми.

В зовнішній підпрограмі x,y – глобальні змінні. Вони доступні в межах всієї програми і всіх для її підпрограм.

Якщо в підпрограмі є однойменні локальні і глобальні змінні, то уникнення конфлікту імен здійснюється завдяки так званому екрануванню ідентифікаторів, тобто в межах кожної підпрограми доступним є лише свій локальний об’єкт. Він перекриває однойменні глобальні об’єкти, а глобальної змінної х доступу немає, хоча легко доступна глобальна змінна y.

1. Без типові параметри

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

Такі параметри використовують тоді, коли розміри ділянки пам’яті, де зберігається значення параметрів є невизначеним наперед. В цьому випадку передається не вся комірка, а адреса її початку, тобто вказівник на неї.

Оголошуються без типові параметри при допомозі var, після якого іде перелік ідентифікаторів без вказання типу.

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

Цими параметрами можуть бути лише змінні.

Механізмвикликупідпрограм

Кожна підпрограма є окремою командою в головній програмі. При зверненні до підпрограми відбувається передача управління в частину виконуваного коду програми, який відноситься до цієї підпрограми. Після завершення підпрограми відбувається повернення в основну програму.

Для цього спеціальному сегменту підпрограми, який називається сегментом стеку, записуються адреси точок повернення після виконання програми.

В цьому сегменті розміщуються всі локальні змінні даної підпрограми, а також її фактичні параметри. Це означає, що звертання до багатьох підпрограм з деякою кількістю фактичних параметрів змінних вичеркує сегмент стеку, тому потрібно контролювати цю ситуацію, бо програма перерве своє виконання при переповненому стеку.

Два байти на адресу сегменту і два байти на зміщення в ньому.

Рекурсія

Використання підпрограми із механізмом передачі параметрів дозволяє реалізувати такий спосіб повторення як рекурсія деякого алгоритму за рахунок звернення до самого себе.

Рекурсія – такі підпрограми, які в самому тілі містять фактичний виклик самої себе.

«А этот глист страдал глистами, которые глистами мучались сами».

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

Наприклад

PROCEDURE P1;

BEGIN

Writeln(‘hello’);

P1;

END;

Це приклад необмеженої рекурсії, за рахунок процедури без параметрів.

VAR

n: integer;

PROCEDURE P2;

BEGIN

n:=n+1;

writeln(‘hello’);

if n<=3276 then P2 else writeln(‘stop”)

END;

BEGIN

…

n:=0;

P2;

…

END.

Дана процедура реалізує скінчену рекурсію з лічильником у вигляді глобальної змінної.

PROCEDURE P3 (n: integer);

BEGIN

Writeln(‘hello’);

If n<=3767 then P3(n+1) else writeln(‘stop’)

END;

BEGIN

P3(0)

END;

Цей приклад процедури з параметром.

Класичний приклад рекурсивного прикладу – це функція факторіал.

PROCEDURE p_fact(n: integer: var f: integer);

VAR f1: longint;

BEGIN

If n=0 then f:=1 else

begin

P_fact (n-1, f1);

F:=n*f1

end;

END.

FUNCTION f_fact(n:integer):longint;

BEGIN

If n=0 then f_fact:=1 else f_fact:=n*f_fact

END;

Розглянемо послідовність викликів для процедури. Нехай потрібно обчислити 3!.

 

При допомозі рекурсії можна реалізувати будь-який повторювальний алгоритм. Головне, щоб мали місце дві умови:

1. Наявність умови зупинки, при якій деякому параметру рекурсії передається деяке значення рекурсії.

2. чітко визначений алгоритм, при обчисленні кожного вищого рівня рекурсії через попередній рівень.

В загальному випадку рекурсивну систему можна описати так:

Нехай f(x,y), x, y – вхідні параметри алгоритму, реалізує повторювальний алгоритм. І є ще дві алгоритмічні функції з строго визначеним алгоритмом, тоді ця рекурсивна функцію можна побудувати так.

Таким чином, якщо вдасться певним чином побудувати алгоритм g(x) ma h(x, y, z), то на основі останнього співвідношення реалізується будь-який рекурсивний алгоритм. Для алгоритму обчислення факторіалу

g(x)=1

h(x, y, z) = y*f(y-1).

Підпрограми в якості параметрів інших підпрограм

Розглянуті раніше процедури та функції отримували в якості фактичних параметрів величини стандартних типів або структурованих, в ряді випадків виникає потреба передавати в якості параметра не лише дані, а й інші підпрограми.

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

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

Тіло кожної із функцій або процедур може бути відмінним, але всі вони повинні мати однакову кількість, порядок, тип параметрів, а для функцій тип результату.

Оголошуються функціональні (процедурні) типи в розділі type через службові слова procedure, function.

TYPE

<ім’я типу>=FUNCTION(<список формальних параметрів>):<тип результату>;

<ім’я типу>= PROCEDURE (<список формальних параметрів>);

Наприклад

TYPE

funct1= function(x:real): real;

func2=function(x, y:integer): boolean;

proc1=procedure(p:integer; var f:longint);

Перший тип являє собою сукупність всіх дійсних функцій від одного дійсного аргументу. Другий тип – множина логічних функцій від двох цілочисельних аргументів. Третій – множина всіх процедур з одним параметром змінної типу longint. Тепер можна оголосити змінні функціонального (процедурного типу. Їм можна присвоїти будь-яку функцію чи процедуру відповідного типу.

VAR

f1: funct1;

f2: funct2;

p1:proc1;

Присвоєння виду f1:=sin(x) не є коректним, оскільки змінна має тип function, а змінна х real.

ТЕМА: ФАЙЛИ

Файловізмінні

Розглянуті раніше способи структурування даних мають суттєвий недолік: після завершення роботи програми всі дані пропадають в оперативній пам’яті, крім цього обмеження розміру статичної частини оперативної пам’яті, де зберігаються всі змінні, які обмежені в програмі (менше 64 кбайт), накладається обмеження на кількість структурованих даних.

Наприклад

Для бази даних про студентів з попереднього прикладу можна використати масив, розмір якого k визначається із співвідношення k*321<=65530, k<=204.