Підпрограми

Поява таких послідовностей імітується за допомогою підпрограми, що називається генератором псевдовипадкових чисел. Кожне нове число утворюється застосуванням рекурентного співвідношення до попереднього. Очевидно, що така послідовність не випадкова, але вона "виглядає, як випадкова". Лише перше число можна вважати випадковим, тому що воно надходить від одного з зовнішніх пристроїв комп'ютера. У реальних генераторах це, як правило, таймер (машинні часи), а тут це буде клавіатура.

У багатьох генераторах використовується множина цілих чисел від 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;