Як ми вже говорили в підрозділі 7.1, локальні імена, означені в підпрограмах, можуть збігатися з іменами в програмі та інших підпрограмах, оскільки вони позначають цілком різні об'єкти в різних областях пам'яті. Тому на локальні імена в підпрограмах немає ніяких обмежень. Зрозуміло, те саме ім'я в межах тіла підпрограми не повинно позначати різні об'єкти, наприклад, локальну змінну та іншу підпрограму. Не можна також означати ім'я самої підпрограми в її ж блоці.
Звернімо увагу на таблицю, що відбиває імітацію програми з прикладу 8.1. Спочатку виділяється локальна пам'ять функції f, потім – функції g, але звільнення відбувається в зворотнім порядку.
Виділення та звільнення ділянок пам'яті при виконанні викликів підпрограм відбувається за принципом "останнім зайнятий – першим звільнений". Подібно тому, як заштовхують патрони в магазин автомата й вистрілюють. Останній із них вистрілюється першим, а перший, що на самому дні магазина, – останнім. Можна вистрілити один патрон із магазина і додати згори новий. Цьому відповідає закінчення виклику підпрограми, записаного в тілі деякої підпрограми, і початок виконання наступного виклику з цього ж тіла.
Якщо складати аркуші паперу в стопку і брати їх тільки згори, то лист, що потрапив у стопку останнім, забирається першим. По-англійському така стопка називається stack (стек), а кладуться і забираються аркуші за принципом "LastIn – FirstOut" (LIFO), тобто "першим у – останнім із". Тому автоматична пам'ять програми називається програмним стеком. Таблиця в прикладі 8.1 показує, як зростає й зменшується програмний стек при виконанні викликів підпрограм.
6. Зберігання локальних змінних між викликами підпрограми
У деяких задачах необхідно використовувати змінні, які означені й доступні в підпрограмі, але зберігають своє значення від її попереднього виклику до наступного.
Ці змінні не можна розміщати в автоматичній пам'яті, оскільки вона недоступна після виконання виклику підпрограми. Ці змінні не можна означати в програмі, оскільки тоді вони доступні не тільки в потрібній підпрограмі. Де і як їх означати?
Виходом є означення цих змінних у підпрограмі як статичних. Саме такі змінні розміщаються в статичній пам'яті програми разом із змінними програми, але доступні тільки під час виконання виклику тієї підпрограми, у якій означені. Вони називаються локальнимистатичними змінними. Розглянемо задачу, у якій використовуються такі змінні.
Приклад 2. У багатьох задачах, від моделювання природних або соціальних процесів і до розкладання карт, потрібні послідовності чисел, що належать деякій множині, але більше ніяк не пов'язані одне з одним. Такі числа називаються випадковими.
Поява таких послідовностей імітується за допомогою підпрограми, що називається генератором псевдовипадкових чисел. Кожне нове число утворюється застосуванням рекурентного співвідношення до попереднього. Очевидно, що така послідовність не випадкова, але вона "виглядає, як випадкова". Лише перше число можна вважати випадковим, тому що воно надходить від одного з зовнішніх пристроїв комп'ютера. У реальних генераторах це, як правило, таймер (машинні часи), а тут це буде клавіатура.
У багатьох генераторах використовується множина цілих чисел від 0 до m-1, де m – достатньо велике число. Нове число визначається за попереднім застосуванням рекурентного співвідношення вигляду
Vi+1=( a*Vi + c ) modm.
Цей дуже простій у реалізації метод породження наступного числа називається лінійнимконгруентним. Ми не будемо тут досліджувати, при яких значеннях параметрів a, c і m і чому утворюється послідовність, схожа на випадкову. Про це написано дуже багато, і достатньо заглянути в книгу Д.Кнута [Кнут, т.2]. Для прикладу візьмемо m=1001, a=21, c=57.
Наша задача – написати функцію, що задає обчислення та повернення наступного елемента послідовності за умови, що відомий попередній. Дамо їй ім'я NextRand – скорочення від "Next Random", або "наступне випадкове".
Очевидною є функція, з якої повертається значення її параметра-змінної, а він змінюється так, як задано рекурентним співвідношенням. Проте в програмі з такою функцією необхідно означати змінну, що була б аргументом у викликах функції. Але ця змінна доступна для зміни в самій програмі й іншим її підпрограмам, і таке рішення не є задовільним.
Ту змінну, чиїми значеннями є послідовні псевдовипадкові числа, означимо в нашій функції як статичну. Те, що змінна статична, якимось чином треба указати в її означенні. Наприклад, у мові Сі та деяких діалектах мови Паскаль там записуються додаткові позначення, щось на зразок
staticvar V : integer.
У діалекті Турбо Паскаль локальну статичну змінну задає означення з ініціалізацією (п.2.3.6), записане в підпрограмі. Нагадаємо його дещо дивний вигляд:
constім'я : тип = ініціалізуюче-значення;
З ним наша функція виглядає так:
function NextRand : integer;
const V : integer = 0; const m=1001; a=21; c=57;
begin
V := ( a*V+ c ) mod m; NextRand := V
end;
Як видно, першим псевдовипадковим числом завжди буде 0. Але в задачі було потрібно, щоб перше число надходило "із зовнішнього світу". Змінимо функцію так, що при виконанні її першого виклику відбувається запит на введення першого числа з клавіатури, а при наступних – обчислення за рекурентним співвідношенням:
function NextRand : integer;
const V : integer = 0; First : Boolean = true;
const m=1001; a=21; c=57;
function Rand1: integer;
var t : integer;
begin
write('Задайте ціле від 0 до ', m-1, '>'); readln(t);
Rand1 := t
end;
begin
if First then
begin First := false; V := Rand1 end
else V := ( a*V+ c ) mod m;
NextRand := V
end;
Тепер можна записувати цю функцію та її виклики в програмах, де потрібно імітувати появу випадкових чисел. Проте краще помістити цю функцію в модуль (п.7.2 ) з ім'ям, наприклад, Randoms, транслювати його та у програмі вказувати лише його використання: uses Randoms.
Використання модулів дозволяє розв'язати нашу задачу взагалі без використання локальних статичних змінних. Справа в тім, що змінні, означені в модулі, як і змінні програми, є статичними. Тому модуль можна записати в такому вигляді:
Unit Randoms;
Interface
function NextRand : integer;
Implementation
const m=1001; a=21; c=57; var V : integer; First : Boolean;
function Rand1: integer;
var t : integer;
begin
write('Задайте ціле від 0 до ', m-1, '>'); readln(t);
Rand1 := t
end;
function NextRand;
begin
if First then
begin First := false; V := Rand1 end
else V := ( a*V+ c ) mod m;
NextRand := V
end;
Begin First := true
End.
Як бачимо, змінні V та First стали глобальними в модулі і доступними в його підпрограмах, але за його межами їх "не видно". Можна сказати, що їх означення локалізовані в модулі.
Задачі
2. Переробити модуль Randoms так, щоб він задавав породження псевдовипадкової послідовності
а) дійсних чисел з проміжку [0; 1]; б) дійсних чисел з проміжку [c; d].
3. Переробити модуль Randoms так, щоб зовні його можна було використовувати функцію Rand1. Написати програму обчислення середнього арифметичного значення M та дисперсії D псевдовипадкової послідовності дійсних чисел {Xi} з проміжку [0;1]. Дисперсія– це середнє арифметичне квадратів різниць між числами та M:
D = ( ( X1 - M )2 + … + ( XN - M )2 )/N,
де N – загальна кількість елементів. Добрий генератор має давати значення M і D, близькі до 1/2 та 1/12 відповідно. Але не всякий генератор, що дає такі середнє значення та дисперсію, є добрим.
4. Площу S двовимірної геометричної фігури обмежених розмірів можна обчислити в такий спосіб. Розташувати фігуру всередині іншої, площа S2 якої обчислюється досить просто за формулами. Нею, як правило, є прямокутник у декартовій системі координат. Вибрати довільно N точок із другої фігури, указуючи їхні координати, та обчислити кількість K тих із них, що належать першій фігурі. Відношення K/N буде наближенням до S/S2. Координати точок обчислюються за допомогою випадкових чисел, тому цей спосіб називається методом Монте-Карло – за назвою курорту, де грали в рулетку.
Написати програму обчислення за методом Монте-Карло наближення до площі кола, заданого координатами центру та радіусом.
5. Реалізувати генератор псевдовипадкових чисел, оснований на рекурентному співвідношенні Vi=(a*Vi-1+b*Vi-2+c) mod m. Перші два значення V1 і V2задаються випадково. Параметри підібрати самостійно. Використати генератор в задачах 8.3–8.4.
7. Підпрограми як параметри
У мові Паскаль параметрами підпрограм можуть бути не тільки змінні, але й підпрограми.
Розглянемо приклад. Нам потрібно надрукувати три таблиці значень трьох математичних функцій на заданому відрізку [a; b], де a>0, у точках, розташованих із заданим кроком h. Функції такі:
sh(x) = (ex-e-x)/2, ch(x) = (ex+e-x)/2,
th(x) = (ex-e-x)/(ex+e-x) = (e2x-1)/(e2x+1) .
У програмі можна записати функції з іменами sh, ch і th, що задають необхідні обчислення, та означити змінні a, b, h, n, k, x. Тоді оператори тіла програми можуть мати такий вигляд:
Readln(a, b, h);
n:= trunc((b-a)/h);
for k:=0 to n do
begin x:=a+k*h; writeln(x, ' ', sh(x)) end;
for k:=0 to n do
begin x:=a+k*h; writeln(x, ' ', ch(x)) end;
for k:=0 to n do