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

А. Панфілов, Азбука Visual Basic

Серед математичних функцій Бейсіка є функція Rnd, призначена для вироблення випадкових чисел. Ця функція, якщо до неї звернутися без параметра, видає чергове “випадкове” число. Слово випадкове ми уклали
в лапки, бо насправді це число виходить в Внаслідок зовсім невипадкових обчислень і лише виглядає, як випадкове. Написавши програму, яка друкує кілька випадкових числ, наприклад, таку





Debug.Print Rnd
Debug.Print Rnd
Debug.Print Rnd
Debug.Print Rnd
Debug.Print Rnd





і запустивши її кілька разів поспіль ми виявимо, що програма видає ту саму серію випадкових чисел. Яка вже тут випадковість! Справі можна допомогти, якщо перед першим зверненням до функції Rnd видати команду
Randomize, 
що означає “зробити випадковим” або “змішати карти”. Ця команда, використовуючи датчик поточного часу, робить наступне число, повертається функцією Rnd, дійсно випадковим, або хоча б непередбачуваним.
А навіщо нам непередбачуваність?

Справа в тому, що ми хочемо використовувати функцію Rnd для нашої програми, яка розкладає пасьянс. Природно, ми хочемо, щоб при кожному запуску програми раслад пасьянсу був різним. Ну заважати карти ми вже навчилися. Тепер приступимо до розкладці карт. Припустимо нам треба вибрати випадковим чином 5 карт з колоди в 36 аркушів. Як же використовувати для цього функцію Rnd? Адже ця функція просто повертає нам число в діапазоні від 0 до 1, а не номер необхідної картки.

Припустимо всі карти в колоді вихідної пронумеровані від 1 до 36. Будемо вести облік карт з використанням масиву deck (36). Елемент масиву містить істину, якщо карта присутня в колоді і ще не брала участь в розкладі. Ось як буде виглядати тільки що роздрукована колода





dim deck(36)
For i = 1 to 36
  deck(i) = True
Next





Заважати карти ми вже не будемо, а замість цього змішаємо датчик





Randomize





Перша викладена карта з однаковою ймовірністю має бути однією з 36 карт. Для вироблення випадкового номера картки треба випадкове число, отримане від Rnd, помножити на 36, відкинути дробову частину і додати одиницю. Тепер можна занести до відповідного елемент масиву deck значення False – ознака того, що карта пішла з колоди.





n = Int(Rnd * 36) + 1
deck(n) = False





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





Dim deck(36)
For i = 1 To 36
  deck(i) = True
Next
Randomize
For i = 1 To 5
  Do
    n = Int(Rnd * 36) + 1
    If deck(n) Then
      deck(n) = False
      Exit Do
    End If
  Loop
Next
For i = 1 To 36
  If Not deck(i) Then
    Debug.Print (i)
  End If
Next





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

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

Розглянемо одну з труднощів, з якою ми зустрінемося при розробці імітаційних програм. Скажімо, програма, імітує оператора, натискає на клавіші. Хотілося б, щоб між натисканнями окремих клавіш проходило певний час: близько секунди – трохи більше або трохи менше. Як програма повинна обчислювати час очікування? Відразу спадає на думку наступний алгоритм: програма повинна виробити випадкове число, а потім, наприклад, додати до нього 5.5 і розділити результат на 6. В результаті вийде, що час очікування буде коливатися між 5.5 / 6 і 6.5 / 6 і розподілено рівномірно на цьому відрізку. Звичайно, це буде надто грубою імітацією процесу, оскільки в житті час очікування розподілено нерівномірно.

Розглянемо детальніше, що означає рівномірний розподіл. Функція Rnd повертає нам величину, яка рівномірно розподілена. Це значить що потрапляння числа у відрізок [0, 0.1] відбувається з тією ж імовірністю, що й у відрізок [0.55, 0.65]. Неважливо, що один з цих відрізків знаходиться на краю діапазону, а інший рівно в середині. Головне, що ці відрізки мають однакову довжину. Графік функції щільності такого розподілу має вигляд прямокутника, тому такий розподіл ще називають прямокутним. Така “прямокутна випадковість “не цілком відповідає випадковим процесам, з якими ми стикаємося в житті. Час очікування або час реакції зазвичай розподілені не прямокутно, а колоколообразной, тобто попадання в відрізок, що лежить поблизу середнього значення, має набагато більшу ймовірність, ніж потрапляння в відрізок тієї ж довжини, що лежить на периферії. Виявляється моделювати такого типу розподілу досить просто. Для цього досить скласти кілька величин з прямокутним розподілом. Давайте проведемо відповідний експеримент. Звернемося 12 разів до функції Rnd і складемо результати. Сума буде перебувати в діапазоні від 0 до 12. Подивимося, як часто результат буде потрапляти в відрізки [0.5, 1.0], [3.0, 3.5] та [6.0, 6.5]. Всі ці відрізки мають однакову довжину, але розташовані по-різному. Для надійності число звернень повинно бути багато, скажімо 100000. Ось відповідна програма:





Randomize
n1 = 0
n2 = 0
n3 = 0
For i = 1 To 100000
  s = 0
  For j = 1 To 12
    s = s + Rnd
  Next
  If 1 < s And s <= 1.5 Then
    n1 = n1 + 1
  End If
  If 3 < s And s <= 3.5 Then
    n2 = n2 + 1
  End If
  If 6 < s And s <= 6.5 Then
    n3 = n3 + 1
  End If
Next
Debug.Print n1
Debug.Print n2
Debug.Print n3





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

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

Спочатку зрозуміємо, чого ж ми хочемо. Середнє значення величини – це зрозуміло. Візьмемо да складемо тисячі вироблених величин і розділимо на цю ж тисячу. А ось з розплющеними складніше. Прийнято вимірювати її середньою квадратичним відхиленням або дисперсією. Це треба знову виробити тисячі величин, посмотреть, на скільки кожна відрізняється від середнього значення, звести цю різницю в квадрат і все скласти, після чого розділити на ту ж тисячу. Фактично ми дали не точне визначення середнього та дисперсії, а запропонували спосіб їх вимірювання. Якщо ми виробимо не тисячу, а
10000 величин, то точність вимірювання, природно, підвищиться.

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

Звернемося до функції Rnd 12 разів і складемо результати. (Можна було взяти не 12 а інше число, це спричинило б за собою лише невелику корекцію наступних далі формул). додамо до результату C і помножимо на G, де C і G спеціально підібрані числа обчислені за формулами: G = Sqr (D) і C = (E-6G) / G

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





D = 0.1 ‘Необхідна дисперсія
E = 1 ‘Необхідний середнє
G = Sqr (D) ‘Множник
C = (E – 6 * G) / G ‘Доданок
Randomize
‘Оцінюємо середню
m = 0
For i = 1 To 10000
  s = 0
  For j = 1 To 12
    s = s + Rnd
  Next
  s = (s + C) * G
  m = m + s
Next
m = m / 10000
‘Оцінюємо дисперсію
D = 0
For i = 1 To 10000
  s = 0
  For j = 1 To 12
    s = s + Rnd
  Next
  s = (s + C) * G
  D = D + (m – s) ^ 2
Next
D = D / 10000
‘Друкуємо результати
Debug.Print m
Debug.Print D





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

Подібні методи існують і для інших класичних імовірнісних розподілів. Але ми зараз спробуємо інший підхід, який можна застосовувати загалом, некласичному випадку. Нехай розподіл задано у вигляді стовпчастої діаграми або гістограми. Для хорошого опису реального розподілу стовпців в діаграмі має бути багато, але ми для простоти розглянемо приклад з п’яти стовпців. Нехай стовпець над відрізком [0,1] має висоту 0.1, це означає, що вироблена випадкова величина повинна потрапляти на цей відрізок з ймовірністю 0.1. Стовпець над відрізком [1,2] має іншу задану висоту і т. д. Якщо скласти висоти всіх стовпців, то ми повинні отримати одиницю. Це природна умова, якщо ми хочемо мати справу з імовірностями. Якщо ваша столбцовая діаграма не така (а вона напевно не така), то вам доведеться нормувати стовпці, тобто розділити висоту кожного стовпця на суму висот всіх стовпців. Можна це робити прямо на комп’ютері. Нехай задані висоти стовпців:





Dim f(5)
f(1) = 10
f(2) = 15
f(3) = 40
f(4) = 25
f(5) = 10





Тоді наступний фрагмент зробить нормування





s = 0
For i = 1 To 5
  s = s + f(i)
Next
For i = 1 To 5
  f(i) = f(i) / s
Next





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





s = 0
For i = 1 To 5
  s = s + f(i)
  f(i) = s
Next





Природно, в останній елемент масиву потрапить одиниця. Масив f буде виглядати наступним чином:





f(1) = 0.1
f(2) = 0.25
f(3) = 0.65
f(4) = 0.90
f(5) = 1.0





Вся ця підготовча робота проводиться один раз. Значення, підготовлені в масиві f, дозволяють тепер отримати потрібну нам величину таким чином:



r = Rnd
For i = 1 To 5
  If r < f(i) Then
s = i – 0.5 ‘беремо середину інтервалу
    Exit For
  End If
Next



На цьому можна зупинитися і прийняти s за вироблене значення. А можна і додатково розмазати це значення рівномірно по всьому інтервалу:





s = s – 0.5 + Rnd





У цьому методі потрібно всього лише одне або два звернення до датчика Rnd, але велика подальша обробка, адже для хорошого наближення має бути багато сходинок. Вигідно удосконалити цей метод і зробити сходинки неоднаковою ширини. Там де щільність сильно змінюється, сходинки повинні бути частіше, на краях сходинки можуть бути широкими. Ширину сходинок доводиться зберігати в окремому масиві. Алгоритм при цьому ще трохи ускладниться.

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

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*