Розглянемо задачу, у якій використовуються такі змінні.
Приклад 2. У багатьох задачах, від моделювання природних або соціальних процесів і до розкладання карт, потрібні послідовності чисел, що належать деякій множині, але більше ніяк не пов'язані одне з одним. Такі числа називаються випадковими.
Поява таких послідовностей імітується за допомогою підпрограми, що називається генератором псевдовипадкових чисел. Кожне нове число утворюється застосуванням рекурентного співвідношення до попереднього. Очевидно, що така послідовність не випадкова, але вона "виглядає, як випадкова". Лише перше число можна вважати випадковим, тому що воно надходить від одного з зовнішніх пристроїв комп'ютера. У реальних генераторах це, як правило, таймер (машинні часи), а тут це буде клавіатура.
У багатьох генераторах використовується множина цілих чисел від 0 до m-1, де m – достатньо велике число. Нове число визначається за попереднім застосуванням рекурентного співвідношення вигляду
Vi+1=( a*Vi + c ) mod m.
Цей дуже простій у реалізації метод породження наступного числа називається лінійним конгруентним. Ми не будемо тут досліджувати, при яких значеннях параметрів a, c і m і чому утворюється послідовність, схожа на випадкову. Про це написано дуже багато, і достатньо заглянути в книгу Д.Кнута [Кнут, т.2]. Для прикладу візьмемо m=1001, a=21, c=57.
Наша задача – написати функцію, що задає обчислення та повернення наступного елемента послідовності за умови, що відомий попередній. Дамо їй ім'я NextRand – скорочення від "Next Random", або "наступне випадкове".
Очевидною є функція, з якої повертається значення її параметра-змінної, а він змінюється так, як задано рекурентним співвідношенням. Проте в програмі з такою функцією необхідно означати змінну, що була б аргументом у викликах функції. Але ця змінна доступна для зміни в самій програмі й іншим її підпрограмам, і таке рішення не є задовільним.
Ту змінну, чиїми значеннями є послідовні псевдовипадкові числа, означимо в нашій функції як статичну. Те, що змінна статична, якимось чином треба указати в її означенні. Наприклад, у мові Сі та деяких діалектах мови Паскаль там записуються додаткові позначення, щось на зразок
static var 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.