Среди математических функций
бейсика имеется функция 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] имеет другую
заданную высоту и т. д. Если сложить высоты всех столбцов, то
мы должны получить единицу. Это естественное условие, если
мы хотим иметь дело с вероятностями. Если ваша столбцовая
диаграмма не такая (а она наверняка не такая), то вам
придется нормировать столбцы, то есть разделить высоту
каждого столбца на сумму высот всех столбцов. Можно это
делать прямо на компьютере. Пусть заданы высоты столбцов:
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,
позволяют теперь получить нужную нам величину следующим
образом:
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, но велика последующая
обработка, ведь для хорошего приближения должно быть много
ступенек. Выгодно усовершенствовать этот метод и сделать
ступеньки неодинаковой ширины. Там где плотность сильно
меняется, ступеньки должны быть чаще, на краях ступеньки
могут быть широкими. Ширину ступенек приходится хранить в
отдельном массиве. Алгоритм при этом еще немного усложнится.
Подходы и алгоритмы случайного моделирования можно множить.
Мы же лишь слегка затронули эту тему. Если читатели пришлют
свои соображения и вопросы, то разговор можно продолжить.
