Відмінності між версіями «Генератори випадкових чисел»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
 
(не показані 14 проміжних версій 3 учасників)
Рядок 1: Рядок 1:
−
== [['''Генерация случайных чисел и моделирование''']] ==
+
== Генерація випадкових чисел і моделювання ==
−
Последовательности случайных чисел используются в программировании в самых разнообразных случаях, начиная с моделирования (это наиболее частое применение) и кончая играми и другим развлекательным программным обеспечением. Турбо Паскаль содержит встроенную функцию, называемую Random, которая генерирует случайные числа. Как вы увидите в данной главе,  Random - это превосходный генератор случайных чисел, но для некоторых применений вам может потребоваться два или более различных генераторов для обеспечения различных наборов случайных чисел для различных задач. Кроме того, при моделировании требуется ассиметричный или дисбалансный генератор случайных чисел, который порождает последовательность, смещенную к одному из концов. Первая часть данной главы посвящена построению генераторов случайных чисел и оценке их качества.
+
Послідовності випадкових чисел використовуються в програмуванні в найрізноманітніших випадках, починаючи з моделювання (це найбільш часте застосування) і кінчаючи іграми і іншим розважальним програмним забезпеченням. Турбо Паскаль містить вбудовану функцію, звану Random, яка генерує випадкові числа. Як ви побачите в даному розділі,  Random - це чудовий генератор випадкових чисел, але для деяких застосувань вам може потрібно два або більш різних генераторів для забезпечення різних наборів випадкових чисел для різних завдань. Крім того, при моделюванні потрібний ассиметрічний або дісбалансний генератор випадкових чисел, який породжує послідовність, зміщену до одного з кінців. Перша частина даного розділу присвячена побудові генераторів випадкових чисел і оцінці їх якості.
−
Во второй части данной главы показывается, как вы можете использовать случайные числа при моделировании реальных ситуаций на двух примерах. В примерах иллюстрируются фундаментальные основы прогр
+
  
−
'''Генераторы случайных чисел'''
+
'''Генератор випадкових чисел''' (англ. Random number generator; часто скорочується як RNG, ГВЧ) — обчислювальний або фізичний пристрій, спроектований для генерації послідовності номерів чи символів, які не відповідають будь-якому шаблону, тобто є випадковими. Широко використовуються комп'ютерні системи для генерації випадкових чисел, але часто вони малоефективні. Ці функції, можливо, забезпечують достатньо випадковості для певних завдань (наприклад, для відеоігор), але є непридатними в тих випадках, коли потрібна «високоякісна випадковість», як, наприклад, у криптографічних програмах, статистиці або чисельному аналізі. Методи добування випадкових результатів існували здавна, зокрема, використання гральних костей, підкидання монети, тасування ігрових карт та ін.
−
Технически термин "генератор случайных чисел" - это абсурд; числа само по себе не являются случайными. Например,  100 - это случайное число?  А 25? Что в действительности означает этот термин, так это то, что создается последовательность чисел, появляющихся случайным образом. Это порождает более сложный вопрос: что такое последовательность случайных чисел?  Единственно правильный ответ: последовательность случайных чисел _ это последовательность, в которой все элементы являются несвязанными. Это определение приводит к такому парадоксу, что любая последовательность может быть как случайной, так и неслучайной в зависимости от того, как эта последовательность получена. Например, следующая строка чисел
+
 
−
1 2 3 4 5 6 7 8 9 0 была получена печатанием верхней строки клавиатуры по порядку, таким образом последовательность конечно не может рассматриваться как сгенерированная случайным образом. Но как быть, если вы получите ту же самую последовательность, вынимая пронумерованный теннисные шары из боченка. В данном случае это уже случайным образом сгенерированная последовательность. Данный пример показывает, что случайность последовательности зависит от того, как она была получена, а не от нее самой.
+
Існує багато різних методів отримання випадкових даних. Ці методи можуть відрізнятися тим, які непередбачувані чи статистично випадкові дані вони видають, а також як швидко вони можуть генерувати випадкові номери.
−
Помните, что последовательность чисел, сгенерированная компьютером, является детерминированной: каждое число, кроме первого, зависит от предшествующих чисел. Технически это означает, что компьютером может быть сгенерирована только квазислучайная последовательность чисел. Однако, этого достаточно для большинства задач и в данной книге такие последовательности для простоты будут называться случайными.
+
 
−
В общем случае считается хорошо, когда числа в последовательности случайных чисел распределены равномерно (не путайте это с нормальным распределением или колоколообразной кривой). При равномерном распределении все события равновероятны так, что диаграмма равномерного распределения стремится к прямой горизонтальной линии, а не к кривой.
+
До появи обчислювальних генераторів випадкових чисел, для отримання великої кількості достатньо випадкових номерів (важливо в статистиці) треба було багато роботи. Результати іноді узагальнювали й розповсюджували як таблиці випадкових чисел.
−
До широкого распространения компьютеров всякий раз, когда необходимы были случайные числа, они получались либо бросанием игральных костей, либо выниманием пронумерованных шаров из ящика. В 1955 году фирма RAND опубликовала таблицу из 1 миллиона случайных чисел, полученных с помощью вычислительной машины. На ранней стадии развития вычислительной техники было разработано много методов генерации случайных чисел, но большинство из них не нашло применения.
+
 
−
Один очень интересный метод был разработан Джоном фон Нейманом; его часто называют среднеквадратичным. В данном методе предыдущее случайное число возводится в квадрат, а затем из результата выделяются средние цифры. Например, если вы создаете числа из трех цифр, а предыдущее число было 121, то возведение в квадрат дает результат 14641. Выделение трех средних цифр дает следующее случайное число 464. Недостатком данного метода является то, что он имеет очень короткий период повторения, называемый циклом. По данной причине данный метод сегодня не используется.
+
'''Виділяють такі класи датчиків (генераторів) випадкових чисел:'''
−
В настоящий момент наиболее часто применяется метод генерации случайных чисел, основывающийся на использовании уравнения
+
 
 +
'''Табличний датчик випадкових чисел'''
 +
 
 +
Являє собою таблицю заповнену реалізаціями випадкової величини з заданим розподілом. Представлені у таких таблицях вибірки дуже якісні, та вони мають обмежений розмір. Та і кількість таких вибірок невелика, що суттєво обмежує їх використання.
 +
 
 +
'''Фізичний датчик випадкових чисел'''
 +
 
 +
Конструюється на основі певного електронного пристрою, на виході якого спостерігають потрібну реалізацію випадкової величини. Ці генератори дозволяють отримувати вибірку довільного обсягу, та вони мають інший недолік - кожна отримана вибірка унікальна, і її неможливо повторити. Зате наступний клас генераторів не має цього недоліку:
 +
 
 +
'''Програмний датчик випадкових чисел'''
 +
 
 +
будується на базі деякої програми, на виході якої формується потрібна реалізація. Ці програми зазвичай базуються на деякій рекурентній формулі. Задаючи однакові початкові члени послідовності можна щоразу отримувати однакові послідовності. Та ці генератори в свою чергу мають інший недолік - вони періодичні. Числа які вони генерують називають "псевдовипадковими" бо вони отримуються за чітким детермінованим алгоритмом.
 +
 
 +
== Генератори випадкових чисел ==
 +
Технічно термін "генератор випадкових чисел" - це абсурд; числа само по собі не є випадковими. Наприклад,  100 - це випадкове число?  А 25? Що насправді означає цей термін, так це те, що створюється послідовність чисел, що з'являються випадковим чином. Це породжує складніше питання: що таке послідовність випадкових чисел?  Єдино правильна відповідь: послідовність випадкових чисел _ це послідовність, в якій всі елементи є незв'язаними. Це визначення приводить до такого парадоксу, що будь-яка послідовність може бути як випадковою, так і невипадковою залежно від того, як ця послідовність отримана. Наприклад, наступний рядок чисел
 +
1 2 3 4 5 6 7 8 9 0 була отримана друкуванням верхнього рядка клавіатури по порядку, таким чином послідовність звичайно не може розглядатися як що згенерувала випадковим чином. Але як бути, якщо ви отримаєте ту ж саму послідовність, виймаючи пронумерований тенісні кулі з боченка. В даному випадку це вже випадковим чином послідовність, що згенерувала. Даний приклад показує, що випадковість послідовності залежить від того, як вона була отримана, а не від неї самої.
 +
Пам'ятаєте, що послідовність чисел, що згенерувала комп'ютером, є детермінованою: кожне число, окрім першого, залежить від попередніх чисел. Технічно це означає, що комп'ютером може згенерувати тільки квазівипадкова послідовність чисел. Проте, це досить для більшості завдань і в даній книзі такі послідовності для простоти називатимуться випадковими.
 +
У загальному випадку вважається добре, коли числа в послідовності випадкових чисел розподілені рівномірно (не плутайте це з нормальним розподілом або колоколообразной кривою). При рівномірному розподілі всі події рівноімовірні так, що діаграма рівномірного розподілу прагне до прямої горизонтальної лінії, а не до кривій.
 +
До широкого розповсюдження комп'ютерів всякий раз, коли необхідні були випадкові числа, вони виходили або киданням гральних кісток, або вийманням пронумерованих куль з ящика. У 1955 році фірма RAND опублікувала таблицю з 1 мільйона випадкових чисел, отриманих за допомогою обчислювальної машини. На ранній стадії розвитку обчислювальної техніки було розроблено багато методів генерації випадкових чисел, але більшість з них не знайшла застосування.
 +
Один дуже цікавий метод був розроблений Джоном фон Нейманом; його часто називають середньоквадратичним. У даному методі попереднє випадкове число зводиться в квадрат, а потім з результату виділяються середні цифри. Наприклад, якщо ви створюєте числа з трьох цифр, а попереднє число було 121, то зведення в квадрат дає результат 14641. Виділення трьох середніх цифр дає наступне випадкове число 464. Недоліком даного методу є те, що він має дуже короткий період повторення, званий циклом. З даної причини даний метод сьогодні не використовується.
 +
Зараз найчастіше застосовується метод генерації випадкових чисел, що грунтується на використанні рівняння
 
       R    = (aR +c)modm
 
       R    = (aR +c)modm
 
         n+1        n
 
         n+1        n
−
при выполнении следующих условий
+
при виконанні наступних умов
  
 
     R>0
 
     R>0
Рядок 19: Рядок 38:
 
     c>0
 
     c>0
 
     m>R , a и c
 
     m>R , a и c
−
Отметим, что R - это предыдущее число, а R - следующее. Данный метод иногда называют линейным сравнительным методом. Формула так проста, что вы можете подумать, что генерировать случайные числа просто. Однако, это ловушка: насколько хорошо работает данная формула, очень сильно зависит от значения а, с и m. Выбор значений иногда в большей степени искусство, нежели наука. Существуют сложные правила, которые могут помочь вам выбрать значения; однако, мы рассмотрим лишь несколько простых правил и примеров.
+
Відзначимо, що R - це попереднє число, а R - наступне. Даний метод іноді називають лінійним порівняльним методом. Формула така проста, що ви можете подумати, що генерувати випадкові числа просто. Проте, це пастка: наскільки добре працює дана формула, дуже сильно залежить від значення а, з і m. Вибір значень іноді більшою мірою мистецтво, ніж наука. Існують складні правила, які можуть допомогти вам вибрати значення; проте, ми розглянемо лише декілька простих правил і прикладів.
−
Модуль (m) должен быть довольно большим, так как он определяет область случайных чисел. Операция взятия по модулю порождает остаток от деления числа на модуль. Следовательно, 10 по модулю 4 равно 2. Таким образом, если модуль равен 12, то формулой порождаются числа от 0 до 11, а если модуль равен 21425, то порождаются числа от 0 до 21424. Выбор множителя а и приращения с является очень сложной задачей. В общем случае множитель может быть довольно большим, а приращение - маленьким. Множество попыток и проверок необходимо, чтобы создать хороший генератор.
+
Модуль (m) повинен бути досить великим, оскільки він визначає область випадкових чисел. Операція узяття по модулю породжує залишок від ділення числа на модуль. Отже, 10 по модулю 4 рівне 2. Таким чином, якщо модуль рівний 12, то формулою породжуються числа від 0 до 11, а якщо модуль рівний 21425, то породжуються числа від 0 до 21424. Вибір множника а і прирости з є дуже складним завданням. У загальному випадку множник може бути задоволене великим, а приріст - маленьким. Безліч спроб і перевірок необхідна, щоб створити хороший генератор.
−
В качестве первого примера здесь приведен один из наиболее часто используемых генераторов случайных чисел. Уравнение, показанное в Rаn1 используется как основа для генератора случайных чисел в ряде популярных языков.
+
Як перший приклад тут приведений один з найчастіше використовуваних генераторів випадкових чисел. Рівняння, показане в Rаn1 використовується як основа для генератора випадкових чисел у ряді популярних мов.
 
     var
 
     var
 
       a1: integer; { установка до первого вызова Ran1 }
 
       a1: integer; { установка до первого вызова Ran1 }
Рядок 32: Рядок 51:
 
       Ran1 := Abs(t/32749);
 
       Ran1 := Abs(t/32749);
 
     end; {Rea1}
 
     end; {Rea1}
−
Данная функция имеет три главные особенности. Во-первых, случайные числа в действительности являются целыми, хотя функция возвращает действительные числа. Данный метод работает с целыми числами, но генераторы случайных чисел, как это принято, должны возвращать числа в пределах от 0 до  1, что означает, что это должны быть числа с плавающей запятой.
+
Дана функція має три головні особливості. По-перше, випадкові числа насправді є цілими, хоча функція повертає дійсні числа. Даний метод працює з цілими числами, але генератори випадкових чисел, як це прийнято, повинні повертати числа в межах від 0 до  1, що означає, що це повинні бути числа з плаваючою комою.
−
Во-вторых, начальное значение задается через глобальную переменную а1. До первого вызова Ran1 переменная а1 должна быть установлена в 1.
+
По-друге, початкове значення задається через глобальну змінну а1. До першого виклику Ran1 змінна а1 повинна бути встановлена в 1.
−
В-третьих, в  Ran1 случайные числа делятся на модуль прежде, чем они будут возвращены функцией, для того, чтобы числа лежали в области от 0 до 1. Если вы поинтересуетесь значением глобальной переменной а1 до возврата строки, то оно должно лежать в области от 0 до 32748. Следовательно, когда а1 делится на 32749, полученное число будет больше или равно 0 и меньше 1.
+
По-третє, в  Ran1 випадкові числа діляться на модуль перш, ніж вони будуть повернені функцією, для того, щоб числа лежали в області від 0 до 1. Якщо ви поцікавитеся значенням глобальної змінної а1 до повернення рядка, то воно повинне лежати в області від 0 до 32748. Отже, коли а1 ділиться на 32749, отримане число буде більше або рівне 0 і менше 1.
−
Многие генераторы случайных чисел не применимы, так как они порождают не равномерное распределение или имеют короткий цикл повторения. Даже когда эти недостатки не очень бросаются в глаза, они могут породить смешанный результат, если такой генератор используется снова и снова. Решение заключается в том, чтобы создать различные генераторы и применять их индивидуально или совместно для получения более качественных последовательностей случайных чисел. Применение нескольких генераторов может сгладить распределение последовательности за счет уменьшения малых смешений отдельных генераторов. Далее приведена функция генерирования случайных чисел, называемая Ran2, которая порождает хорошее распределение:
+
Багато генераторів випадкових чисел не застосовні, оскільки вони породжують не рівномірний розподіл або мають короткий цикл повторення. Навіть коли ці недоліки не дуже впадають в очі, вони можуть породити змішаний результат, якщо такий генератор використовується знову і знову. Рішення полягає в тому, щоб створити різні генератори і застосовувати їх індивідуально або спільно для отримання якісніших послідовностей випадкових чисел. Застосування декількох генераторів може згладити розподіл послідовності за рахунок зменшення малих змішень окремих генераторів. Далі приведена функція генерування випадкових чисел, звана Ran2, яка породжує хороший розподіл:
 
     var
 
     var
−
       a2:integer; { установить в значение 203 до первого вызова
+
       a2:integer; { встановити в значення 203 до першого виклику
 
                     Ran2 }
 
                     Ran2 }
 
     function Ran2: real;
 
     function Ran2: real;
Рядок 47: Рядок 66:
 
       Ran2 := Abc(t/17417);
 
       Ran2 := Abc(t/17417);
 
     end; {Ran2}
 
     end; {Ran2}
−
Оба этих генератора случайных чисел порождают хорошие последовательности случайных чисел. Тем не менее остаются вопросы: достаточно ли "случайной" является последовательность?  Хороши ли данные генераторы?
+
Обидва цих генератора випадкових чисел породжують хороші послідовності випадкових чисел. Проте залишаються питання: чи достатньо "випадковою" є послідовність?  Чи хороші дані генератори?
  
−
'''Определение качества генераторов'''
+
== Визначення якості генераторів ==
−
Вы можете применить различные тексты для определения случайности последовательности чисел. Ни один из тестов не скажет, что последовательность является случайной, однако, он скажет, если она не является таковой. Тесты могут выявить не случайные последовательности, но, если тест не нашел недостатков, это не означает, что данная последовательность действительно случайная. Тесты, однако, повышают уверенность в генераторе случайных чисел, который породил последовательность. Теперь мы кратко рассмотрим несколько простых способов тестирования последовательностей.
+
Ви можете застосувати різні тексти для визначення випадковості послідовності чисел. Жоден з тестів не скаже, що послідовність є випадковою, проте, він скаже, якщо вона немає такій. Тести можуть виявити не випадкові послідовності, але, якщо тест не знайшов недоліків, це не означає, що дана послідовність дійсно випадкова. Тести, проте, підвищують упевненість в генераторі випадкових чисел, який породив послідовність. Тепер ми стисло розглянемо декілька простих способів тестування послідовностей.
−
Для начала рассмотрим способ определения того, насколько близко распределение чисел в последовательности соответствует ожидаемому. Например, вы пытаетесь генерировать последовательность случайных чисел от 0 до 9. Вероятность появления каждой цифры равна 1/10. Пусть была сгенерирована следующая последовательность
+
Спершу розглянемо спосіб визначення того, наскільки близький розподіл чисел в послідовності відповідає очікуваному. Наприклад, ви намагаєтеся генерувати послідовність випадкових чисел від 0 9. Вірогідність появи кожної цифри рівна 1/10. Хай згенерувала наступна послідовність
  
 
     9 1 8 2 4 6 3 7 5 2 9 0 4 2 4 7 8 6 2
 
     9 1 8 2 4 6 3 7 5 2 9 0 4 2 4 7 8 6 2
−
Если вы подсчитаете число появлений каждой цифры, то получите результат
+
Якщо ви підрахуєте число появ кожної цифри, то отримаєте результат
−
        Цифры          Число появлений
+
      Цифри            Число появ
 
         0                    1
 
         0                    1
 
         1                    1
 
         1                    1
Рядок 66: Рядок 85:
 
         8                    3
 
         8                    3
 
         9                    2
 
         9                    2
−
Далее вам следует ответить самому себе на вопрос, достаточно ли похоже данное распределение на ожидаемое вами. Помните: если генератор случайных чисел хороший, он генерирует последовательности случайно. В истинно случайном варианте все последовательности возможны. Действительно, как какая-то последовательность может быть не случайной, если любая последовательность возможна? Просто некоторые последовательности менее похожи на то, какой должна быть случайная последовательность, чем другие. Вы можете определить вероятность того, что данная последовательность является случайной, используя критерий хи-квадрат.
+
Далі вам слід відповісти самому собі на питання, чи достатній схоже даний розподіл на очікуване вами. Пам'ятаєте: якщо генератор випадкових чисел хороший, він генерує послідовності випадково. У істинно випадковому варіанті всі послідовності можливі. Дійсно, як якась послідовність може бути не випадковою, якщо будь-яка послідовність можлива? Просто деякі послідовності менш схожі на те, якою повинна бути випадкова послідовність, чим інші. Ви можете визначити вірогідність того, що дана послідовність є випадковою, використовуючи критерій хи-квадрат.
−
В критерии хи-квадрат ожидаемое количество вычитается из наблюдаемого количества встреч числа в сгенерированной последовательности. Этот результат называется V. Вы можете использовать Vдля нахождения процента в таблице значений хи-квадрат. Этот процент определяет вероятность того, что была порождена случайная последовательность. Малая таблица хи-квадрат приведена на рис.7-1; вы можете найти полные таблицы в большинстве книг по статистике
+
У критерії хи-квадрат очікувана кількість віднімається із спостережуваної кількості зустрічей числа в послідовності, що згенерувала. Цей результат називається V. Ви можете використовувати Vдля знаходження відсотка в таблиці значень хи-квадрат. Цей відсоток визначає вірогідність того, що була породжена випадкова послідовність. Мала таблиця хи-квадрат приведена на ріс.7-1; ви можете знайти повні таблиці в більшості книг за статистикою
  
 
     p=99%      p=95%    p=75%    p=50%    p=25%    p=5%
 
     p=99%      p=95%    p=75%    p=50%    p=25%    p=5%
Рядок 75: Рядок 94:
 
     n=20 8.260    10.85    15.45    19.34    23.83    31.41
 
     n=20 8.260    10.85    15.45    19.34    23.83    31.41
 
     n=30 14.95    18.49    24.48    29.34    34.80    43.77
 
     n=30 14.95    18.49    24.48    29.34    34.80    43.77
−
Выбранные значения хи-квадрат.
+
Вибрані значення хи-квадрат.
−
Для определения вероятности того, что последовательность не случайная, найдите строку в таблице, показанной на рис.7-1, с числом элементов последовательности; в данном случае это 20. Затем ищите число по строке, которое больше V. В данном случае это колонка 1. Это означает, что существует вероятность 99% того, что пример из 20 элементов будет иметь V больше 8,260. С другой стороны это означает, что существует вероятность только в 1%  того, что проверяемая последовательность была сгенерирована случайным образом. Чтобы пройти через критерий хи-квадрат, вероятность V должна снизиться до уровня от 25% до 75%.
+
Для визначення вірогідності того, що послідовність не випадкова, знайдіть рядок в таблиці, показаній на ріс.7-1, з числом елементів послідовності; в даному випадку це 20. Потім шукайте число по рядку, яке більше V. В даному випадку це колонка 1. Це означає, що існує вірогідність 99% того, що приклад з 20 елементів матиме V більше 8,260. З іншого боку це означає, що існує вірогідність тільки в 1%  того, що послідовність, що перевіряється, згенерувала випадковим чином. Щоб пройти через критерій хи-квадрат, вірогідність V повинна знизитися до рівня від 25% до 75%.
−
Однако вы можете противопоставить этому выводу вопрос: Так как все последовательности возможны, как может данная последовательность иметь только однопроцентный шанс быть законной?  Ответ такой: это всего лишь вероятность. Фактически, если вы применяете критерий хи-квадрат, вам следует получить несколько различных последовательностей и усредненный результат, чтобы избежать отвержения хорошего генератора случайных чисел. Любая единичная последовательность может быть отвергнута, но ряд различных последовательностей после усреднения должен давать хороший результат.
+
Проте ви можете протиставити цьому виводу питання: Оскільки всі послідовності можливі, як може дана послідовність мати тільки однопроцентний шанс бути законною?  Відповідь така: це всього лише вірогідність. Фактично, якщо ви застосовуєте критерій хи-квадрат, вам слід отримати декілька різних послідовностей і усереднений результат, щоб уникнути відкидання хорошого генератора випадкових чисел. Будь-яка одинична послідовність може бути знехтувана, але ряд різних послідовностей після усереднювання повинен давати добрий результат.
−
С другой стороны, последовательность может пройти через критерий хи-квадрат и не быть случайной. Например, последовательность      
+
З іншого боку, послідовність може пройти через критерій хи-квадрат і не бути випадковою. Наприклад, послідовність      
 
1 3 5 7 9 1 3 5 7 9  
 
1 3 5 7 9 1 3 5 7 9  
−
пройдет критерий хи-квадрат, но она выглядит не очень случайной. В данном случае сгенерирован пробег по диапазону значений. Пробег - это просто возрастающая или убывающая последовательность чисел с произвольным интервалом. В данном случае каждая группа из пяти цифр представляет собой возрастающую последовательность и как таковая не может считаться случайной последовательностью. Можно создать тест для обнаружения такой ситуации, но это выходит за рамки данной книги.
+
пройде критерій хи-квадрат, але вона виглядає не дуже випадковою. В даному випадку згенерував пробіг по діапазону значень. Пробіг - це просто зростаюча або убуваюча послідовність чисел з довільним інтервалом. В даному випадку кожна група з п'яти цифр є зростаючою послідовністю і як така не може вважатися випадковою послідовністю. Можна створити тест для виявлення такої ситуації, але це виходить за рамки даної книги.
−
Другой характеристикой, подлежащей оценке, является длина периода: то есть, как много чисел может быть сгенерировано до начала повторения последовательности. Все машинные генераторы случайных чисел всегда генерировали повторяющуюся последовательность. Чем длиннее период, тем лучше генератор. Даже если частота чисел внутри периода распределена равномерно, числа не образуют случайную серию, так как действительно случайная серия не может достаточно повторяться. В общем случае период в несколько тысяч чисел удовлетворяет большинству применений. Тест для выяснения периода может быть разработан.
+
Іншою характеристикою, належній оцінці, є довжина періоду: тобто, як багато чисел може згенерувати до початку повторення послідовності. Всі машинні генератори випадкових чисел завжди генерували послідовність, що повторюється. Чим довше період, тим краще генератор. Навіть якщо частота чисел усередині періоду розподілена рівномірно, числа не утворюють випадкову серію, оскільки дійсно випадкова серія не може достатньо повторюватися. У загальному випадку період в декілька тисяч чисел задовольняє більшості застосувань. Тест для з'ясування періоду може бути розроблений.
−
Различные другие тесты могут быть применены для определения качества генератора случайных чисел. Наверное, можно написать больше программ для проверки генераторов случайных чисел, чем создать самих генераторов. Рассмотрим еще один тест, который позволит вам проверить генератор случайных чисел  "визуально", используя диаграмму для демонстрации характеристик сгенерированной последовательности.
+
Різні інші тести можуть бути застосовані для визначення якості генератора випадкових чисел. Напевно, можна написати більше програм для перевірки генераторів випадкових чисел, чим створити самих генераторів. Розглянемо ще один тест, який дозволить вам перевірити генератор випадкових чисел  "візуально", використовуючи діаграму для демонстрації характеристик послідовності, що згенерувала.
−
В идеале диаграмма должна основываться на частоте каждого числа. Однако так как генератор может порождать тысячи различных чисел, это не выполнимо. Вместо этого будут создаваться диаграммы, сгруппированные до десяти цифрам. Например, так как порождаемые числа лежат в области от 0 до 1, число 0.9365783 будет включено в группу 9, а число 0.34523445 будет включено в группу 3. Это означает, что диаграмма вывода случайных чисел имеет 10 линий, каждая из которых представляет число попаданий в группу. Программа также выводит среднее значение последовательности, которое может быть использовано для обнаружения смешения. Как и все другие программы данной главы, следующая программа выполняется только на персональном компьютере IBM PC, который имеет адаптер цветного графического дисплея. Разработанные ранее функции Ran1 и Ran2, а также встроенная функция Турбо Паскаля Random, продемонстрированы рядом для сравнения.
+
У ідеалі діаграма повинна грунтуватися на частоті кожного числа. Проте оскільки генератор може породжувати тисячі різних чисел, це не здійснимо. Замість цього створюватимуться діаграми, згруповані до десяти цифрам. Наприклад, оскільки породжувані числа лежать в області від 0 до 1, число 0.9365783 буде включено в групу 9, а число 0.34523445 буде включено в групу 3. Це означає, що діаграма виведення випадкових чисел має 10 ліній, кожна з яких представляє число попадань в групу. Програма також виводить середнє значення послідовності, яке може бути використане для виявлення змішення. Як і всі інші програми даного розділу, наступна програма виконується тільки на персональному комп'ютері IBM РС, який має адаптер кольорового графічного дисплея. Розроблені раніше функції Ran1 і Ran2, а також вбудована функція Турбо Паскаля Random, продемонстровані поряд для порівняння.
−
     { программа, которая сравнивает три генератора случайных чисел }
+
     { програма, яка порівнює три генератори випадкових чисел }
 
     program RanGenerator;
 
     program RanGenerator;
 
     uses
 
     uses
Рядок 97: Рядок 116:
 
       y, x: integer;
 
       y, x: integer;
 
       GraphDriver, GraphMode: integer;
 
       GraphDriver, GraphMode: integer;
−
     {отображение графического вывода}
+
     { відображення графічного виводу}
 
     procedure Display;
 
     procedure Display;
 
     var
 
     var
Рядок 126: Рядок 145:
 
     end;  {Ran2}
 
     end;  {Ran2}
 
     begin
 
     begin
−
       { переключение на графический режим, используя режим 4 CGA/EGA }
+
       { перемикання на графічний режим, використовуючи режим 4 Cga/ega }
 
       GraphDriver := CGA;
 
       GraphDriver := CGA;
 
       GraphMode := CGAC1;
 
       GraphMode := CGAC1;
Рядок 170: Рядок 189:
 
       WriteLn('mean of Ran2 is: ', f3/COUNT);
 
       WriteLn('mean of Ran2 is: ', f3/COUNT);
 
     end.
 
     end.
−
В данной программе каждая функция генерирует 1000 чисел и на основе этого создаются таблицы частот. Процедура Display  рисует все три матрицы частот на экране после генерации каждого случайного числа так, что вы можете наблюдать рост частот. На рис.7-2 показан вывод каждого генератора случайных чисел после генерации 1000 чисел. Средние значения равны 0,489932 у Ran1,  0,4858311 y
+
У даній програмі кожна функція генерує 1000 чисел і на основі цього створюються таблиці частот. Процедура Display  малює всі три матриці частот на екрані після генерації кожного випадкового числа так, що ви можете спостерігати зростання частот. На ріс.7-2 показано виведення кожного генератора випадкових чисел після генерації 1000 чисел. Середні значення рівні 0,489932 у Ran1,  0,4858311 у
−
Ran2 и 0,494014 у Random. Это приемлемо.
+
Ran2 і 0,494014 у Random. Це прийнятно.
 
-----------------------------------------------------------
 
-----------------------------------------------------------
−
             Сравнение генераторов случайных чисел
+
             Порівняння генераторів випадкових чисел
  
  
Рядок 187: Рядок 206:
 
     ----------------------------------------------------------.
 
     ----------------------------------------------------------.
 
   
 
   
−
Вывод из программы отображения работы генераторов
+
Вивід з програми відображення роботи генераторів
−
             случайных чисел.
+
             випадкових чисел.
−
Для эффективного использования программы вы должны наблюдать как за формой диаграммы, так и за динамикой роста, чтобы выявить короткие повторяющиеся циклы. Например,  Ran2 генерирует значительно меньше чисел в области от 0,9 до 0,999999, чем Random и Ran1.
+
Для ефективного використання програми ви повинні спостерігати як за формою діаграми, так і за динамікою зростання, щоб виявити короткі цикли, що повторюються. Наприклад,  Ran2 генерує значно менше чисел в області від 0,9 до 0,999999, чим Random і Ran1.
−
Конечно данный текст не является всеобъемлющим, но он поможет вам понять способ, которым генератор порождает числа, и ускорит процесс анализа генераторов.
+
Звичайно даний текст не є всеосяжним, але він допоможе вам зрозуміти спосіб, яким генератор породжує числа, і прискорить процес аналізу генераторів.
  
−
'''Использование нескольких генераторов'''
+
== Використання декількох генераторів ==
−
Один простой метод, который улучшает свойства случайных последовательностей, порождаемых тремя генераторами, заключается в комбинировании их под управлением одной главной функции. Данная функция выбирает между двумя из них, основываясь на результате третьей. С помощью этого метода вы можете получить очень длинный период и уменьшить влияние циклов и смещений. Функция, называемая CombRandom, показанная здесь, осуществляет комбинирование выводов генераторов Ran1, Ran2, Random:
+
Один простий метод, який покращує властивості випадкових послідовностей, що породжуються трьома генераторами, полягає в комбінуванні їх під управлінням однієї головної функції. Дана функція вибирає між двома з них, грунтуючись на результаті третьої. За допомогою цього методу ви можете отримати дуже довгий період і зменшити вплив циклів і зсувів. Функція, звана Combrandom, показана тут, здійснює комбінування виводів генераторів Ran1, Ran2, Random:
−
     {данная функция использует три генератора для возврата одного случайного числа}
+
     { дана функція використовує три генератори для повернення одного випадкового числа}
 
     function CombRandom: real;
 
     function CombRandom: real;
 
     var
 
     var
Рядок 203: Рядок 222:
 
       else CombRandom := Ran1; { случайный выбор генератора }
 
       else CombRandom := Ran1; { случайный выбор генератора }
 
     end; {CombRandom}
 
     end; {CombRandom}
−
Результат Ran2 используется для того, чтобы решить, Ran1 или Random выдаст значение главной функции CombRandom. При таком методе период главной функции равен или больше суммы периодов Random и Ran1. Таким образом, данный метод делает возможным порождение последовательности с очень длинным периодом. Можно легко изменять смесь Random и Ran1 изменением константы в операторе if, чтобы получить желаемое вами распределение между этими двумя генераторами. Кроме того, вы можете добавить дополнительные генераторы и осуществлять выбор между ними для получения еще более длинного периода.
+
Результат Ran2 використовується для того, щоб вирішити, Ran1 або Random видасть значення головної функції Combrandom. При такому методі період головної функції рівний або більше суми періодів Random і Ran1. Таким чином, даний метод робить можливим породження послідовності з дуже довгим періодом. Можна легко змінювати суміш Random і Ran1 зміною константи в операторові if, щоб отримати бажаний вами розподіл між цими двома генераторами. Крім того, ви можете додати додаткові генератори і здійснювати вибір між ними для отримання ще довшого періоду.
−
Далее следует программа для отображения диаграммы CompRandom и ее среднего значения. На рис.7-3 показана финальная диаграмма после генерации 1000 чисел. Среднее значение CombRandom равно
+
Далі слідує програма для відображення діаграми Comprandom і її середнього значення. На ріс.7-3 показана фінальна діаграма після генерації 1000 чисел. Середнє значення Combrandom рівне
 
0,493361.
 
0,493361.
−
     { данная программа демонстрирует комбинированный вывод трех генераторов случайных чисел }
+
     { дана програма демонструє комбіноване виведення трьох генераторів випадкових чисел }
 
     program MultiRandom;
 
     program MultiRandom;
 
     uses
 
     uses
Рядок 278: Рядок 297:
 
     end.
 
     end.
 
----------------------------------------------------.
 
----------------------------------------------------.
−
Вывод, полученный комбинированием трех генераторов случайных чисел.
+
Вивід, отриманий комбінуванням трьох генераторів випадкових чисел.
 
                 ¦ ¦
 
                 ¦ ¦
 
                 ¦ ¦ ¦  ¦
 
                 ¦ ¦ ¦  ¦
Рядок 288: Рядок 307:
 
                 L++++++++
 
                 L++++++++
 
     ------------------------------------------------------
 
     ------------------------------------------------------
−
Финальное отображение функции CombRandom
+
Фінальне відображення функції Combrandom
  
−
'''Моделирование'''
+
== Моделювання ==
−
Оставшаяся часть данной главы посвящена применениям генераторов случайных чисел для моделирования на компьютерах. Промоделировать можно все; успех моделирования зависит главным образом от того, насколько хорошо программист понял ситуацию, которую надо моделировать. Так как реальные ситуации часто имеют тысячи переменных, многие вещи с трудом поддаются моделированию. Однако, существуют ситуации, которые очень хорошо подходят для моделирования.
+
Частина даного розділу, що залишилася, присвячена застосуванням генераторів випадкових чисел для моделювання на комп'ютерах. Промоделіровать можна все; успіх моделювання залежить головним чином від того, наскільки добре програміст зрозумів ситуацію, яку треба моделювати. Оскільки реальні ситуації часто мають тисячі змінних, багато речей насилу піддаються моделюванню. Проте, існують ситуації, які дуже добре підходять для моделювання.
−
Моделирование важно по двум причинам. Во-первых, оно позволяет вам изменять параметры моделирования для проверки и наблюдения возможных результатов в то время, как в реальности такие эксперименты могут быть и дорогими и опасными. Например, моделирование атомной электростанции может быть использовано для проверки влияния различных типов отказов без какой-либо опасности. Во-вторых, моделирование позволяет нам создавать ситуации, которые не могут произойти в реальной жизни. Например, психологи могут захотеть изучить влияние непрерывного роста интеллекта мыши до человеческого, чтобы определить, когда мышь будет проходить лабиринт наиболее быстро. Хотя это не может быть сделано в реальной жизни, моделирование может помочь проникновению в природу соотношения интеллекта и инстинкта. Далее разберем первый из двух примеров, в которых используются генераторы случайных чисел.
+
Моделювання важливе по двох причинах. По-перше, воно дозволяє вам змінювати параметри моделювання для перевірки і спостереження можливих результатів в той час, як в реальності такі експерименти можуть бути і дорогими і небезпечними. Наприклад, моделювання атомної електростанції може бути використане для перевірки впливу різних типів відмов без якої-небудь небезпеки. По-друге, моделювання дозволяє нам створювати ситуації, які не можуть відбутися в реальному житті. Наприклад, психологи можуть захотіти вивчити вплив безперервного зростання інтелекту миші до людського, щоб визначити, коли миша проходитиме лабіринт найшвидше. Хоча це не може бути зроблено в реальному житті, моделювання може допомогти проникненню в природу співвідношення інтелекту і інстинкту. Далі розберемо перший з двох прикладів, в яких використовуються генератори випадкових чисел.
  
−
'''Моделирование очередей обслуживания'''
+
== Моделювання черг обслуговування ==
−
В первом примере моделируется обслуживание в бакалейной лавке. Предположим, что лавка открыта 10 часов в день с пиковыми часами с 12 до 13 и с 17 до 18 часов. Период с 12 до 13 часов имеет нагрузку в два раза, а с 17 до 18 - в три раза больше обычной. При моделировании один генератор "порождает" покупателей, второй генератор определяет время обслуживания покупателя, а третий решает, в какую очередь пойдет покупатель. Цель моделирования состоит в том, чтобы помочь управляющему найти оптимальное число очередей, которые должны работать в обычный день при условии, что число людей в очереди в любое время не превышало бы 10 и кассиры не ожидали бы покупателей.
+
У першому прикладі моделюється обслуговування в бакалійній лавці. Припустимо, що лавка відкрита 10 годин в день з піковим годинником з 12 до 13 і з 17 до 18 годин. Період з 12 до 13 годин має навантаження в два рази, а з 17 до 18 - в три рази більше звичайною. При моделюванні один генератор "породжує" покупців, другий генератор визначає час обслуговування покупця, а третій вирішує, в яку чергу піде покупець. Мета моделювання полягає в тому, щоб допомогти керівникові знайти оптимальне число черг, які повинні працювати в звичайний день за умови, що число людей в черзі у будь-який час не перевищувало б 10 і касири не чекали б покупців.
−
Ключ к данному типу моделирования состоит в создании многих процессов. Хотя Турбо Паскаль непосредственно не поддерживает параллельности, вы можете моделировать с помощью множества процессов или с помощью главной программы с циклами. Далее показана программа с ее глобальными данными для моделирования очередей без поддержки процедур и функций:
+
Ключ до даного типу моделювання полягає в створенні багатьох процесів. Хоча Турбо Паскаль безпосередньо не підтримує паралельності, ви можете моделювати за допомогою безлічі процесів або за допомогою головної програми з циклами. Далі показана програма з її глобальними даними для моделювання черг без підтримки процедур і функцій:
 
     var
 
     var
 
       gueues, count: array[0..9] of integer;
 
       gueues, count: array[0..9] of integer;
Рядок 343: Рядок 362:
 
       RestoreCrtMode;
 
       RestoreCrtMode;
 
     end.
 
     end.
−
Элемент Graph.P включен, чтобы программа могла использовать графические функции.
+
Елемент Graph.P включений, щоб програма могла використовувати графічні функції.
−
Главный цикл управляет всем моделированием:
+
Головний цикл управляє всім моделюванням:
 
     repeat
 
     repeat
 
       AddCust;
 
       AddCust;
Рядок 358: Рядок 377:
 
       time := time+1;
 
       time := time+1;
 
     until time>100;  { конец дня }
 
     until time>100;  { конец дня }
−
Функция AddCust использует либо Ran1, либо Ran2 для генерации числа покупателей, встающих в очереди при каждом запросе. Функция AddQuece используется для помещения покупателей в очереди в соответствии с результатом Ran2, а также открывает новые очереди, если все существующие переполнены. Функция Display отображает программу моделирования.  Checkout использует Ran2 для назначения каждого покупателя в очередь с соответствующим увеличением счетчика очереди; каждый вызов уменьшает счетчик на 1. Когда счетчик покупателей равен 0, очередь становится пустой.
+
Функція Addcust використовує або Ran1, або Ran2 для генерації числа покупців, що встають в черзі при кожному запиті. Функція Addquece використовується для приміщення покупців в черзі відповідно до результату Ran2, а також відкриває нові черги, якщо ті, що всі існують переповнені. Функція Display відображає програму моделювання.  Checkout використовує Ran2 для призначення кожного покупця в чергу з відповідним збільшенням лічильника черги; кожен виклик зменшує лічильник на 1. Коли лічильник покупців рівний 0, черга стає порожньою.
−
Переменная time  (время)  изменяет интенсивность, с которой генерируются покупатели, для того, чтобы отследить часовые пики. Каждый проход по циклу представляет одну десятую часа.
+
Змінна time  (час)  змінює інтенсивність, з якою генеруються покупці, для того, щоб відстежити годинні списи. Кожен прохід по циклу представляє одну десяту години.
−
На рис.7-4,  7-5 и 7-6 показаны состояния очередей, когда time=28,  time=60 и time=88, что соответствует нормальному времени, концу первого пика и концу второго пика, соответственно. Отметим, что в конце второго пика требуется максимум пять очередей, Если моделирующая программа написана правильно, то в бакалейной лавке оставшиеся пять очередей не нужны.
+
На ріс.7-4,  7-5 і 7-6 показані стани черг, коли time=28,  time=60 і time=88, що відповідає нормальному часу, кінцю першого піку і кінцю другого піку, відповідно. Відзначимо, що в кінці другого піку потрібно максимум п'ять черг, Якщо моделююча програма написана правильно, то в бакалійній лавці п'ять черг, що залишилися, не потрібно.
 
     gueue 1: 10      time: 28
 
     gueue 1: 10      time: 28
 
     gueue 2: 8
 
     gueue 2: 8
Рядок 421: Рядок 440:
  
 
                         1                    10
 
                         1                    10
−
Рис.7-6. Состояние очередей, когда time=88:
+
Ріс.7-6. Стан черг, коли time=88:
−
Вы можете непосредственно управлять различными переменными в программе. Во-первых, вы можете изменить путь и число прибывающих покупателей. Вы также можете изменить функцию AddCost, чтобы она возвращала число покупателей в пиковые часы с большим или меньшим постепенным увеличением или уменьшением. Программа предполагает, что покупатели случайным образом выбирают, в какую очередь им встать. Такой подход справедлив для одних покупателей, а другие будут выбирать самую короткую очередь. Вы можете учесть это, изменив функцию AddQueue так, чтобы она в некоторых случаях помещала покупателей в самую короткую очередь, а в некоторых - случайным образом. При моделировании не учитываются такие случайности, как упавшая булка или буйный покупатель в очереди, которые вызывают временные остановки очереди.
+
Ви можете безпосередньо управляти різними змінними в програмі. По-перше, ви можете змінити шлях і число покупців, що прибувають. Ви також можете змінити функцію Addcost, щоб вона повертала число покупців в піковий годинник з великим або меншим поступовим збільшенням або зменшенням. Програма припускає, що покупці випадковим чином вибирають, в яку чергу їм встати. Такий підхід справедливий для одних покупців, а інші вибиратимуть найкоротшу чергу. Ви можете врахувати це, змінивши функцію Addqueue так, щоб вона в деяких випадках поміщала покупців в найкоротшу чергу, а в деяких - випадковим чином. При моделюванні не враховуються такі випадковості, як булка, що впала, або буйний покупець в черги, які викликають тимчасові зупинки черги.
−
Целиком программа выглядит следующим образом:
+
Цілком програма виглядає таким чином:
 
     program simulation; {моделирование очередей в бакалейной
 
     program simulation; {моделирование очередей в бакалейной
 
                       лавке }
 
                       лавке }
Рядок 616: Рядок 635:
 
       RestoreCrtMode;
 
       RestoreCrtMode;
 
     end.
 
     end.
 +
 +
== Література==
 +
http://uk.wikipedia.org/wiki/Генерація_випадкових_чисел
 +
 +
 +
[[Тести]]

Поточна версія на 13:16, 12 травня 2013

Генерація випадкових чисел і моделювання

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

Генератор випадкових чисел (англ. Random number generator; часто скорочується як RNG, ГВЧ) — обчислювальний або фізичний пристрій, спроектований для генерації послідовності номерів чи символів, які не відповідають будь-якому шаблону, тобто є випадковими. Широко використовуються комп'ютерні системи для генерації випадкових чисел, але часто вони малоефективні. Ці функції, можливо, забезпечують достатньо випадковості для певних завдань (наприклад, для відеоігор), але є непридатними в тих випадках, коли потрібна «високоякісна випадковість», як, наприклад, у криптографічних програмах, статистиці або чисельному аналізі. Методи добування випадкових результатів існували здавна, зокрема, використання гральних костей, підкидання монети, тасування ігрових карт та ін.

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

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

Виділяють такі класи датчиків (генераторів) випадкових чисел:

Табличний датчик випадкових чисел

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

Фізичний датчик випадкових чисел

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

Програмний датчик випадкових чисел

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

Генератори випадкових чисел

Технічно термін "генератор випадкових чисел" - це абсурд; числа само по собі не є випадковими. Наприклад, 100 - це випадкове число? А 25? Що насправді означає цей термін, так це те, що створюється послідовність чисел, що з'являються випадковим чином. Це породжує складніше питання: що таке послідовність випадкових чисел? Єдино правильна відповідь: послідовність випадкових чисел _ це послідовність, в якій всі елементи є незв'язаними. Це визначення приводить до такого парадоксу, що будь-яка послідовність може бути як випадковою, так і невипадковою залежно від того, як ця послідовність отримана. Наприклад, наступний рядок чисел 1 2 3 4 5 6 7 8 9 0 була отримана друкуванням верхнього рядка клавіатури по порядку, таким чином послідовність звичайно не може розглядатися як що згенерувала випадковим чином. Але як бути, якщо ви отримаєте ту ж саму послідовність, виймаючи пронумерований тенісні кулі з боченка. В даному випадку це вже випадковим чином послідовність, що згенерувала. Даний приклад показує, що випадковість послідовності залежить від того, як вона була отримана, а не від неї самої. Пам'ятаєте, що послідовність чисел, що згенерувала комп'ютером, є детермінованою: кожне число, окрім першого, залежить від попередніх чисел. Технічно це означає, що комп'ютером може згенерувати тільки квазівипадкова послідовність чисел. Проте, це досить для більшості завдань і в даній книзі такі послідовності для простоти називатимуться випадковими. У загальному випадку вважається добре, коли числа в послідовності випадкових чисел розподілені рівномірно (не плутайте це з нормальним розподілом або колоколообразной кривою). При рівномірному розподілі всі події рівноімовірні так, що діаграма рівномірного розподілу прагне до прямої горизонтальної лінії, а не до кривій. До широкого розповсюдження комп'ютерів всякий раз, коли необхідні були випадкові числа, вони виходили або киданням гральних кісток, або вийманням пронумерованих куль з ящика. У 1955 році фірма RAND опублікувала таблицю з 1 мільйона випадкових чисел, отриманих за допомогою обчислювальної машини. На ранній стадії розвитку обчислювальної техніки було розроблено багато методів генерації випадкових чисел, але більшість з них не знайшла застосування. Один дуже цікавий метод був розроблений Джоном фон Нейманом; його часто називають середньоквадратичним. У даному методі попереднє випадкове число зводиться в квадрат, а потім з результату виділяються середні цифри. Наприклад, якщо ви створюєте числа з трьох цифр, а попереднє число було 121, то зведення в квадрат дає результат 14641. Виділення трьох середніх цифр дає наступне випадкове число 464. Недоліком даного методу є те, що він має дуже короткий період повторення, званий циклом. З даної причини даний метод сьогодні не використовується. Зараз найчастіше застосовується метод генерації випадкових чисел, що грунтується на використанні рівняння 

      R    = (aR +c)modm
       n+1         n

при виконанні наступних умов 

   R>0
   a>0
   c>0
   m>R , a и c

Відзначимо, що R - це попереднє число, а R - наступне. Даний метод іноді називають лінійним порівняльним методом. Формула така проста, що ви можете подумати, що генерувати випадкові числа просто. Проте, це пастка: наскільки добре працює дана формула, дуже сильно залежить від значення а, з і m. Вибір значень іноді більшою мірою мистецтво, ніж наука. Існують складні правила, які можуть допомогти вам вибрати значення; проте, ми розглянемо лише декілька простих правил і прикладів. Модуль (m) повинен бути досить великим, оскільки він визначає область випадкових чисел. Операція узяття по модулю породжує залишок від ділення числа на модуль. Отже, 10 по модулю 4 рівне 2. Таким чином, якщо модуль рівний 12, то формулою породжуються числа від 0 до 11, а якщо модуль рівний 21425, то породжуються числа від 0 до 21424. Вибір множника а і прирости з є дуже складним завданням. У загальному випадку множник може бути задоволене великим, а приріст - маленьким. Безліч спроб і перевірок необхідна, щоб створити хороший генератор. Як перший приклад тут приведений один з найчастіше використовуваних генераторів випадкових чисел. Рівняння, показане в Rаn1 використовується як основа для генератора випадкових чисел у ряді популярних мов. 

   var
     a1: integer; { установка до первого вызова Ran1 }
   function Ran1: real;
   var
     t: real;
   begin
     t := (a1*32749+3) mod 32749;
     a1 := Trunc(t);
     Ran1 := Abs(t/32749);
   end; {Rea1}

Дана функція має три головні особливості. По-перше, випадкові числа насправді є цілими, хоча функція повертає дійсні числа. Даний метод працює з цілими числами, але генератори випадкових чисел, як це прийнято, повинні повертати числа в межах від 0 до 1, що означає, що це повинні бути числа з плаваючою комою. По-друге, початкове значення задається через глобальну змінну а1. До першого виклику Ran1 змінна а1 повинна бути встановлена в 1. По-третє, в Ran1 випадкові числа діляться на модуль перш, ніж вони будуть повернені функцією, для того, щоб числа лежали в області від 0 до 1. Якщо ви поцікавитеся значенням глобальної змінної а1 до повернення рядка, то воно повинне лежати в області від 0 до 32748. Отже, коли а1 ділиться на 32749, отримане число буде більше або рівне 0 і менше 1. Багато генераторів випадкових чисел не застосовні, оскільки вони породжують не рівномірний розподіл або мають короткий цикл повторення. Навіть коли ці недоліки не дуже впадають в очі, вони можуть породити змішаний результат, якщо такий генератор використовується знову і знову. Рішення полягає в тому, щоб створити різні генератори і застосовувати їх індивідуально або спільно для отримання якісніших послідовностей випадкових чисел. Застосування декількох генераторів може згладити розподіл послідовності за рахунок зменшення малих змішень окремих генераторів. Далі приведена функція генерування випадкових чисел, звана Ran2, яка породжує хороший розподіл: 

   var
     a2:integer; {  встановити в значення 203 до першого виклику
                   Ran2 }
   function Ran2: real;
   var
     t: real;
   begin
     t := (a2*10001+3) mod 17417;
     a2 := Trunc(t);
     Ran2 := Abc(t/17417);
   end; {Ran2}

Обидва цих генератора випадкових чисел породжують хороші послідовності випадкових чисел. Проте залишаються питання: чи достатньо "випадковою" є послідовність? Чи хороші дані генератори?

Визначення якості генераторів

Ви можете застосувати різні тексти для визначення випадковості послідовності чисел. Жоден з тестів не скаже, що послідовність є випадковою, проте, він скаже, якщо вона немає такій. Тести можуть виявити не випадкові послідовності, але, якщо тест не знайшов недоліків, це не означає, що дана послідовність дійсно випадкова. Тести, проте, підвищують упевненість в генераторі випадкових чисел, який породив послідовність. Тепер ми стисло розглянемо декілька простих способів тестування послідовностей. Спершу розглянемо спосіб визначення того, наскільки близький розподіл чисел в послідовності відповідає очікуваному. Наприклад, ви намагаєтеся генерувати послідовність випадкових чисел від 0 9. Вірогідність появи кожної цифри рівна 1/10. Хай згенерувала наступна послідовність 

    9 1 8 2 4 6 3 7 5 2 9 0 4 2 4 7 8 6 2

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

     Цифри            Число появ 
       0                    1
       1                    1
       2                    4
       3                    1
       4                    3
       5                    1
       6                    2
       7                    2
       8                    3
       9                    2

Далі вам слід відповісти самому собі на питання, чи достатній схоже даний розподіл на очікуване вами. Пам'ятаєте: якщо генератор випадкових чисел хороший, він генерує послідовності випадково. У істинно випадковому варіанті всі послідовності можливі. Дійсно, як якась послідовність може бути не випадковою, якщо будь-яка послідовність можлива? Просто деякі послідовності менш схожі на те, якою повинна бути випадкова послідовність, чим інші. Ви можете визначити вірогідність того, що дана послідовність є випадковою, використовуючи критерій хи-квадрат. У критерії хи-квадрат очікувана кількість віднімається із спостережуваної кількості зустрічей числа в послідовності, що згенерувала. Цей результат називається V. Ви можете використовувати Vдля знаходження відсотка в таблиці значень хи-квадрат. Цей відсоток визначає вірогідність того, що була породжена випадкова послідовність. Мала таблиця хи-квадрат приведена на ріс.7-1; ви можете знайти повні таблиці в більшості книг за статистикою 

   p=99%      p=95%     p=75%     p=50%     p=25%    p=5%
   n=5   0.5543    1.1455    2.675     4.351     6.626   11.07
   n=10 2.558     3.940     6.737     9.342    12.55    18.31
   n=15 5.229     7.261    11.04     14.34     18.25    25.00
   n=20 8.260    10.85     15.45     19.34     23.83    31.41
   n=30 14.95     18.49     24.48     29.34     34.80    43.77

Вибрані значення хи-квадрат. Для визначення вірогідності того, що послідовність не випадкова, знайдіть рядок в таблиці, показаній на ріс.7-1, з числом елементів послідовності; в даному випадку це 20. Потім шукайте число по рядку, яке більше V. В даному випадку це колонка 1. Це означає, що існує вірогідність 99% того, що приклад з 20 елементів матиме V більше 8,260. З іншого боку це означає, що існує вірогідність тільки в 1% того, що послідовність, що перевіряється, згенерувала випадковим чином. Щоб пройти через критерій хи-квадрат, вірогідність V повинна знизитися до рівня від 25% до 75%. Проте ви можете протиставити цьому виводу питання: Оскільки всі послідовності можливі, як може дана послідовність мати тільки однопроцентний шанс бути законною? Відповідь така: це всього лише вірогідність. Фактично, якщо ви застосовуєте критерій хи-квадрат, вам слід отримати декілька різних послідовностей і усереднений результат, щоб уникнути відкидання хорошого генератора випадкових чисел. Будь-яка одинична послідовність може бути знехтувана, але ряд різних послідовностей після усереднювання повинен давати добрий результат. З іншого боку, послідовність може пройти через критерій хи-квадрат і не бути випадковою. Наприклад, послідовність 1 3 5 7 9 1 3 5 7 9 пройде критерій хи-квадрат, але вона виглядає не дуже випадковою. В даному випадку згенерував пробіг по діапазону значень. Пробіг - це просто зростаюча або убуваюча послідовність чисел з довільним інтервалом. В даному випадку кожна група з п'яти цифр є зростаючою послідовністю і як така не може вважатися випадковою послідовністю. Можна створити тест для виявлення такої ситуації, але це виходить за рамки даної книги. Іншою характеристикою, належній оцінці, є довжина періоду: тобто, як багато чисел може згенерувати до початку повторення послідовності. Всі машинні генератори випадкових чисел завжди генерували послідовність, що повторюється. Чим довше період, тим краще генератор. Навіть якщо частота чисел усередині періоду розподілена рівномірно, числа не утворюють випадкову серію, оскільки дійсно випадкова серія не може достатньо повторюватися. У загальному випадку період в декілька тисяч чисел задовольняє більшості застосувань. Тест для з'ясування періоду може бути розроблений. Різні інші тести можуть бути застосовані для визначення якості генератора випадкових чисел. Напевно, можна написати більше програм для перевірки генераторів випадкових чисел, чим створити самих генераторів. Розглянемо ще один тест, який дозволить вам перевірити генератор випадкових чисел "візуально", використовуючи діаграму для демонстрації характеристик послідовності, що згенерувала. У ідеалі діаграма повинна грунтуватися на частоті кожного числа. Проте оскільки генератор може породжувати тисячі різних чисел, це не здійснимо. Замість цього створюватимуться діаграми, згруповані до десяти цифрам. Наприклад, оскільки породжувані числа лежать в області від 0 до 1, число 0.9365783 буде включено в групу 9, а число 0.34523445 буде включено в групу 3. Це означає, що діаграма виведення випадкових чисел має 10 ліній, кожна з яких представляє число попадань в групу. Програма також виводить середнє значення послідовності, яке може бути використане для виявлення змішення. Як і всі інші програми даного розділу, наступна програма виконується тільки на персональному комп'ютері IBM РС, який має адаптер кольорового графічного дисплея. Розроблені раніше функції Ran1 і Ran2, а також вбудована функція Турбо Паскаля Random, продемонстровані поряд для порівняння. 

   { програма, яка порівнює три генератори випадкових чисел }
   program RanGenerator;
   uses
     Graph;
   const
     COUNT = 1000;
   var
     freg1, freg2, freg3: array[0..9] of integer;
     a2, a1: integer;
     f, f2, f3: real;
     r, r2, r3: real;
     y, x: integer;
     GraphDriver, GraphMode: integer;
   { відображення графічного виводу}
   procedure Display;
   var
     t : integer;
   begin
     for t := 0 to 9 do
     begin
      Line(t*10, 180, t*10, 180-freg1[t]);
      Line(t*10+110, 180, t*10+110, 180-freg2[t]);
      Line(t*10+220, 180, t*10+220, 180-freg3[t]);
     end;
   end; {Display}
   function Ran1: real;
   var
     t: real;
   begin
     t := (a1*32749+3) mod 32749;
     a1 := Trunc(t);
     Ran1 := Abs(t/32749);
   end; {Ran1}
   function Ran2: real;
   var
     t: real;
   begin
     t := (a2*10001+3) mod 17417;
     a2 := Trunc(t);
     Ran2 := Abs(t/17417);
   end;  {Ran2}
   begin
     { перемикання на графічний режим, використовуючи режим 4 Cga/ega }
     GraphDriver := CGA;
     GraphMode := CGAC1;
     InitGraph(GraphDriver, GraphMode,  );
     SetColor(2);
     SetLineStyle(SolidLn,  0,  NormWidth);
     OutTextXy(80, 10, 'Comparison of Random');
     OutTextXy(96, 20, 'Number Generators');
     { прорисовать базовые линии }
     Line(0, 180, 90, 180);
     Line(110, 180, 200, 180);
     Line(220, 180, 310, 180);
     OutTextXy(30, 190, 'Random    Ran1    Ran2');
      {инициализация переменных генераторов случайных чисел }
     a1:=1; a2:=203;
     f := 0; f2 := 0; f3 := 0;
     for x := 0 to 9 do
     begin { инициализация матриц частот }
      freg1[x] := 0;
      freg2[x] := 0;
      freg3[x] := 0;
     end;
     for x := 1 to COUNT do
     begin
      r:=Random;    { взять случайное число                    }
      f:=f+r;       { прибавить для вычисления среднего     }
      y:=Trunc(r*10);{ преобразовать в целое число от 0 до 9 }
      freg1[y]:=freg1[y]+1;{ увеличить счетчик частоты       }
      r2 := Ran1;    { взять случайное число                   }
      f2:=f2+r2;     { прибавить для     вычисления среднег  }
      y:=Trunc(r2*10);{ преобразовать в целое число от 0 до 9}
      freg2[y]:=freg2[y]+1;{ увеличить счетчик частоты       }
      r3 := Ran2;       { взять случайное число               }
      f3:=f3+r3;       { прибавить для вычисления среднего    }
      y:=Trunc(r3*10);{  преобразовать в целое число от 0 до 9}
      freg3[y]:=freg3[y]+1;{увеличить счетчик частоты        }
      Display;  {  отобразить счетчики частот }
     end;
     ReadLn;
     RestoreCrtMode;
     WriteLn('mean of Random is: ', f/COUNT);
     WriteLn('mean of Ran1 is: ', f2/COUNT);
     WriteLn('mean of Ran2 is: ', f3/COUNT);
   end.

У даній програмі кожна функція генерує 1000 чисел і на основі цього створюються таблиці частот. Процедура Display малює всі три матриці частот на екрані після генерації кожного випадкового числа так, що ви можете спостерігати зростання частот. На ріс.7-2 показано виведення кожного генератора випадкових чисел після генерації 1000 чисел. Середні значення рівні 0,489932 у Ran1, 0,4858311 у Ran2 і 0,494014 у Random. Це прийнятно. 

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



   ¦       ¦               ¦                         ¦ ¦
   ¦   ¦   ¦       ¦   ¦   ¦ ¦   ¦   ¦       ¦     ¦ ¦ ¦ ¦
   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
   ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
   L-+-+-+-+-+-+-+-+-- L-+-+-+-+-+-+-+-+-- L-+-+-+-+-+-+-+-+-
      Random                    Ran1                  Ran2
   ----------------------------------------------------------.

Вивід з програми відображення роботи генераторів 

           випадкових чисел.

Для ефективного використання програми ви повинні спостерігати як за формою діаграми, так і за динамікою зростання, щоб виявити короткі цикли, що повторюються. Наприклад, Ran2 генерує значно менше чисел в області від 0,9 до 0,999999, чим Random і Ran1. Звичайно даний текст не є всеосяжним, але він допоможе вам зрозуміти спосіб, яким генератор породжує числа, і прискорить процес аналізу генераторів.

Використання декількох генераторів

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

   { дана функція використовує три генератори для повернення одного випадкового числа}
   function CombRandom: real;
   var
     f: real;
   begin
     f := Ran2;
     if f>0.5 thenCombRandom := Random
     else CombRandom := Ran1; { случайный выбор генератора }
   end; {CombRandom}

Результат Ran2 використовується для того, щоб вирішити, Ran1 або Random видасть значення головної функції Combrandom. При такому методі період головної функції рівний або більше суми періодів Random і Ran1. Таким чином, даний метод робить можливим породження послідовності з дуже довгим періодом. Можна легко змінювати суміш Random і Ran1 зміною константи в операторові if, щоб отримати бажаний вами розподіл між цими двома генераторами. Крім того, ви можете додати додаткові генератори і здійснювати вибір між ними для отримання ще довшого періоду. Далі слідує програма для відображення діаграми Comprandom і її середнього значення. На ріс.7-3 показана фінальна діаграма після генерації 1000 чисел. Середнє значення Combrandom рівне 0,493361. 

   { дана програма демонструє комбіноване виведення трьох генераторів випадкових чисел }
   program MultiRandom;
   uses
     Graph;
   const
     COUNT=1000;
   var
     freg: array[0..9] of integer;
     a2,a1: integer;
     f, r: real;
     y, x: integer;
     GraphDriver, GraphMode: integer;
    { отображение графического представления работы генераторов }
    procedure Display;
    var
      t: integer;
    begin
      for t := 0 to 9 do
       Line(t*10+110, 180, t*10+110, 180-freg[t]);
    end; {Display}
    function Ran1: real;
    var
      t: real;
    begin
      t := (a1*32749+3) mod 32749;
      a1 := Trunc(t);
      Ran1 := Abs(t/32749);
    end; {Ran1}
    function Ran2: real;
    var
      t: real;
    begin
      t := (a2*10001+3) mod 17417;
      a2 := Trunc(t);
      Ran2 := Abs(t/17417);
    end; {Ran2}
    {данная функция использует три генератора для возврата одного случайного числа
    }
    function CombRandom real;
    var
      t: real;
    begin
      f := Ran2;
      if f>0.5 then CombRandom := Random
      else CombRandom := Ran1; {случайный выбор генератора }
    end; {CombRandom}
    begin
     { переключение на графический режим, используя режим 4 CGA/EGA }
      GraphDriver := CGA;
      GraphMode := CGAC1;
      InitGraph(GraphDriver, GraphMode,  );
      SetColor(2);
      SetLineStyle(SolidLn, 0, NormWidth);
      OutTextXy(48, 10, 'вывод, полученный комбинированием ');
      OutTextXy(40,20, 'три генератора случайных чисел ');
      Line(110, 180, 200, 180);
      a1:=1; a2:=203; {инициализация переменных для
             генераторов случайных чисел }
      f := 0;
      for x:=0 to 9 do freg[x]:=0; {инициализация матрицы
                       частот}
      for x := 1 to COUNT do begin
       r:=CombRandom;  { взять случайное число  }
       f:=f+1;   { прибавить для вычисления среднего  }
       y:=Trunc(r*10);{ преобразовать в целое число от 0 до 9}
       freg[y]:=freg[y]+1;{ увеличить счетчик частоты }         Display;
    end;
    ReadLn;
    RestoreCrtMode;
    WriteLn('Среднее случайное число равно : ', f/COUNT);
    end.
.

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

               ¦ ¦
               ¦ ¦ ¦   ¦
               ¦¦¦¦¦¦¦¦¦¦
               ¦¦¦¦¦¦¦¦¦¦
               ¦¦¦¦¦¦¦¦¦¦
               ¦¦¦¦¦¦¦¦¦¦
               ¦¦¦¦¦¦¦¦¦¦
               L++++++++
    ------------------------------------------------------

Фінальне відображення функції Combrandom

Моделювання

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

Моделювання черг обслуговування

У першому прикладі моделюється обслуговування в бакалійній лавці. Припустимо, що лавка відкрита 10 годин в день з піковим годинником з 12 до 13 і з 17 до 18 годин. Період з 12 до 13 годин має навантаження в два рази, а з 17 до 18 - в три рази більше звичайною. При моделюванні один генератор "породжує" покупців, другий генератор визначає час обслуговування покупця, а третій вирішує, в яку чергу піде покупець. Мета моделювання полягає в тому, щоб допомогти керівникові знайти оптимальне число черг, які повинні працювати в звичайний день за умови, що число людей в черзі у будь-який час не перевищувало б 10 і касири не чекали б покупців. Ключ до даного типу моделювання полягає в створенні багатьох процесів. Хоча Турбо Паскаль безпосередньо не підтримує паралельності, ви можете моделювати за допомогою безлічі процесів або за допомогою головної програми з циклами. Далі показана програма з її глобальними даними для моделювання черг без підтримки процедур і функцій: 

    var
      gueues, count: array[0..9] of integer;
      open: array[0..9] of boolean;
      cust, time: integer;
      a1, a2: integer;
      y, x: integer;
      change: boolean;
      GraphDiver, GraphMode: integer;
    begin
      {переключение на графику, используя режим 4 CGA/EGA}
      GraphDriver := CGA;
      GraphMode := CGAC1;
      InitGraph(GraphDriver, GraphMode, );
      SetColor(2);
      SetLineStyle(SolidLn, 0, NormWidth);
      a1:=1; a2:=203; {инициализация переменных генератора
                     случайных чисел}
      change := FALSE;
      cust := 0;
      time := 0;
      for x:=0 to 9 do begin
       gueues[x]:=0; {инициализация очереди }
       open[x]:=FALSE; { нет покупателей или очередей в
                       начале дня }
       count[x]:=0; {счетчик очереди }
      end;
      OutTextXy(155, 190, '1             10');
      OutTextXy(8,190,'Check-out lines: ');
    { теперь начинается день открытием первой очереди }
    open[0] := TRUE;
      repeat
       AddCust;
       AddQueue;
       Display;
       CheckOut;
       Display;
       if (time>30) and (time<50) then AddCust;
       if (time>70) and (nime<80) then begin
         AddCust;
         AddCust;
       end;
       time := time+1;
      until time>100; { конец дня }
      ReadLn;
      RestoreCrtMode;
    end.

Елемент Graph.P включений, щоб програма могла використовувати графічні функції. Головний цикл управляє всім моделюванням: 

    repeat
      AddCust;
      AddQueue;
      Display;
      CheckOut;
      Display;
      if (time>30) and (time<50) then AddCust;
      if (time>70) and (time<80) then begin
       AddCust;
       AddCust;
      end;
      time := time+1;
    until time>100;  { конец дня }

Функція Addcust використовує або Ran1, або Ran2 для генерації числа покупців, що встають в черзі при кожному запиті. Функція Addquece використовується для приміщення покупців в черзі відповідно до результату Ran2, а також відкриває нові черги, якщо ті, що всі існують переповнені. Функція Display відображає програму моделювання. Checkout використовує Ran2 для призначення кожного покупця в чергу з відповідним збільшенням лічильника черги; кожен виклик зменшує лічильник на 1. Коли лічильник покупців рівний 0, черга стає порожньою. Змінна time (час) змінює інтенсивність, з якою генеруються покупці, для того, щоб відстежити годинні списи. Кожен прохід по циклу представляє одну десяту години. На ріс.7-4, 7-5 і 7-6 показані стани черг, коли time=28, time=60 і time=88, що відповідає нормальному часу, кінцю першого піку і кінцю другого піку, відповідно. Відзначимо, що в кінці другого піку потрібно максимум п'ять черг, Якщо моделююча програма написана правильно, то в бакалійній лавці п'ять черг, що залишилися, не потрібно. 

    gueue 1: 10      time: 28
    gueue 2: 8
    gueue 3: 0
    gueue 4: 0
    gueue 5: 0
    gueue 6: 0
    gueue 7: 0
    gueue 8: 0
    gueue 9: 0
    gueue 10: 0

Очередь ¦ 

                       ¦
                       ¦ ¦
                       ¦ ¦
                       ¦ ¦
                       ¦ ¦
                       ¦ ¦
                       ¦ ¦
                     1                     10

Рис.7-4. Состояние очередей, когда time=28: 


    gueue 1: 6    time: 60
    gueue 2: 8
    gueue 3: 8
    gueue 4: 1
    gueue 5: 0
    gueue 6: 0
    gueue 7: 0
    gueue 8: 0
    gueue 9: 0
    gueue 10: 0

Очередь ¦ ¦ 

                         ¦ ¦
                       ¦ ¦ ¦
                       ¦ ¦ ¦
                       ¦ ¦ ¦
                       ¦ ¦ ¦ ¦

                     1                 10

Рис.7-5. Состояние очередей, когда time=60: 

    gueue 1: 8    time: 80
    gueue 2: 9
    gueue 3: 6
    gueue 4: 6
    gueue 5: 7
    gueue 6: 0
    gueue 7: 0
    gueue 8: 0
    gueue 9: 0
    gueue 10: 0

Очередь ¦ 

                        ¦ ¦
                        ¦ ¦     ¦
                        ¦ ¦ ¦ ¦ ¦
                        ¦ ¦ ¦ ¦ ¦
                        ¦ ¦ ¦ ¦ ¦
                        ¦ ¦ ¦ ¦ ¦

                       1                     10

Ріс.7-6. Стан черг, коли time=88: Ви можете безпосередньо управляти різними змінними в програмі. По-перше, ви можете змінити шлях і число покупців, що прибувають. Ви також можете змінити функцію Addcost, щоб вона повертала число покупців в піковий годинник з великим або меншим поступовим збільшенням або зменшенням. Програма припускає, що покупці випадковим чином вибирають, в яку чергу їм встати. Такий підхід справедливий для одних покупців, а інші вибиратимуть найкоротшу чергу. Ви можете врахувати це, змінивши функцію Addqueue так, щоб вона в деяких випадках поміщала покупців в найкоротшу чергу, а в деяких - випадковим чином. При моделюванні не враховуються такі випадковості, як булка, що впала, або буйний покупець в черги, які викликають тимчасові зупинки черги. Цілком програма виглядає таким чином: 

    program simulation; {моделирование очередей в бакалейной
                      лавке }
    uses
      Graph;
    var
      gueues, count: array[0..9] of integer;
      open: array[0..9] of boolean;
      cust, time: integer;
      a1, a2: integer;
      y,x: integer;
      change: boolean;
      GraphDriver, GraphMode: integer;
    function Ran1: real;
    var
      t: real;
    begin
      t := (a1*32749+3) mod 32749;
      a1 := Trunc(t);
      Ran1 := Abs(t/32749);
    end; {Ran1}
    function Ran2: real;
    var
      t: real;
    begin
      t := (a2*10001+3) mod 17417;
      a2 := Trunc(t);
      Ran2 := Abs(t/17417);
    end; {Ran2}
    function CombRandom: real;
    {random selection of generators} 2
    var
      f: real;
    begin
      f := Ran2;
      if f>0.5 then CombRandom := Random
      else CombRandom:=Ran1;{случайный выбор генераторов}
    end; {CombRandom}
    { добавление покупателей в очередь }
    procedure AddCust;
    var
      f, r: real;
    begin
      if change then f:=Random {переключение между двумя }
      else f := Ran2;              {генераторами }
      if f>0.5 then
       if f>0.6 then cust:=cust+1 {добавить одного покупателя}
       else if f>0.7 then cust:=cust+2 {два покупателя}
       else if f<0.8 then cust:=cust+3 {три покупателя }
       else cust := cust+4; {четыре покупателя }
    end; {AddCust}
    { обслуживание покупателя }
    Procedure CheckOut;
    var
      t: integer;
    begin
      for t := 0 to 9 do
      begin
       if gueues[t]<>0 then
       begin
         {получить время обслуживания }
         while count[t]=0 do count[t]:=Trunc(Ran1+5);
         {новый покупатель требует времени обслуживания }
         count[t]:=count[t]-1;
         if count[t]=0 then gueues[t]:=gueues[t]-1;
         {удаление покупателя}
       end;
       if gueues[t]=0 then open[t]:=FALSE;{закрытие очереди}
      end;
    end; {CheckOut}
    {возвращается TRUE, если очередь переполнена }
    function AllFull: Boolean;
    var
      t: integer;
    begin
      AllFull := TRUE;
      for t := 0 to 9 do
       if (gueues[t]<10) and open[t] then AllFull:=FALSE;
    end; {AllFull}
    {данная процедура вводит новые очереди }
    procedure AddQueue;
    var
      t, line: integer;
      done: Boolean;
    begin
      done := FALSE;
      while cust<>0 do
      begin
       if AllFull then
       begin
         t:=0;
         repeat
           if not open[t] then
           begin
             open[t]:=TRUE;
             done:=TRUE;
             end;
           t:=T+1;
           until done or (t=9);
         end
         else
         begin
           Line:=Trunc(Ran2*10);
           if open[line] and (gueues[line]<10) then
           begin
             gueues[line]:=gueues[line]+1;
             cust:=cust-1;
           end;
         end;
         if AllFull and open[9] then cust:=0; {all full}
       end;
    end; {AddQueue}
    {очистить символы длины, начиная с позиции Х, У }
    procedure ClrVed(x,y,len: integer);
    var
      i: integer;
      s: string[80];
    begin
      for i := 1 to len do
       s := concat(Chr(219), Chr(219));
      SetColor(0);
      OutTextXy(x, y, s);
      SetColor(2);
    end; {ClrVid}
    {отображение экрана результатов моделирования очереди }
    procedure Display;
    var
      t: integer;
      value: string[80];
    begin
      cirVid(170, 10, 3);
      str(time, value);
      OutTextXy(120, 10, 'Time: ');
      OutTextXy(170, 10, value);
      for t := 0 to 9 do
      begin
       {erase old line}
       SetColor(0);
       Line((t*10)+160, 180, (t*10)+160, 180);
       {нарисовать новое состояние моделирования }
       SetColor(2);
       Circle((t*10)+160, 180, 3);
       Line((t*10)+160, 180, (t*10)+160, 180-gueues[t]*10);
       {дать также текстовый вывод }
       OutTextXy(8, t*10, 'gueue');
       str(t+1, value);
       value       := concat(value, ':');
       OutTextXy(56, t*10, value);
       ClrVid(80, t*10, 3);
       str(gueues[t], value);
       OutTextXy(80, t*10, value);
       end;
    end; {Display}
    begin
      {переключение на графику, используя режим 4 CGA/EGA }
      GraphDriver := CGA;
      GraphMode := CGAC1;
      InitGraph(GraphDriver, GraphMode, );
      SetColor(2);
      SetLineStyle(SolidLn, 0, NormWidth);
    a1:=1; a2:=203; {инициализация переменных генератора
                  случайных чисел }
      change:=FALSE;
      cust:=0;
      time:=0;
      for x := 0 to 9 do begin
       gueues[x]:=0; {инициализировать очереди }
       open[x]:=FALSE;{нет покупателей или очередей в начале
                        дня }
       count[x]:=0; {счетчик очереди }
      end;
      OutTextXy(155, 190, '1         10');
      OutTextXy(8, 190, 'Check-out lines; ');
    {теперь начинается ден.
открытием первого пункта обслуживания
     }
    open[0]:=TRUE;
    repeat
      AddCust;
      AddQueue;
      Display;
      CheckOut;
      Display;
      if (time>30) and (time<50) then AddCust;
      if (time>70) and (time<80) then begin
       AddCust;
       AddCust;
      end;
      time:=time+1;
     until time>100; { конец дня }
     ReadLn;
     RestoreCrtMode;
    end.

Література

http://uk.wikipedia.org/wiki/Генерація_випадкових_чисел


Тести

Отримано з https://wiki.cusu.edu.ua/index.php?title=Генератори_випадкових_чисел&oldid=95145