Моделирование испытаний
Back Home Up Next

Одной из наиболее простых и вместе с тем весьма распространенных схем повторения независимых испытаний является классическая схема Бернулли. Суть её в следующем. Пусть при некотором испытании событие A может наступить или не наступить. Обозначим вероятность наступления события A через p=p(A) (0<p<1), а вероятность ненаступления A, то есть противоположного события , через q=1-p. Требуется определить вероятность P(n,m) наступления события A в серии из n независимых испытаний ровно m раз. Известно, что  , где - число сочетаний из n элементов по m.

В связи со схемой Бернулли можно поставить много разных задач. Одной из них, весьма необычной и поучительной с точки зрения рекурсивной реализации её решения, мы и займемся.

адача 50. Количество появлений события до первой неудачи.
A
. Составить рекурсивную программу-функцию, которая для данного события A и его вероятности p наступления при каждом испытании моделирует схему Бернулли и подсчитывает значение случайной величины x, равной количеству появлений A до первой неудачи.
          B. Составить рекурсивную программу-функцию, решающую задачу A последовательно n раз и возвращающую результат в виде компонентов вектора.

Решение. Появление или непоявление события A в схеме Бернулли легко моделируется датчиком случайных чисел. Например, функция rnd(a) (a>0) возвращает равномерно распределенное случайное значение x: 0£x<a. Поэтому вне зависимости от сути события A очередное полученное по rnd(1) значение можно интерпретировать так:

 0£rnd(1)<p   «   событие A наступило,       

p£rnd(1)<1   «   событие A не наступило.

Исходя из сказанного, для решения подзадачи a можно предложить такую функцию:

Здесь ненаступление события A определяет терминальную ветвь vmat() и, следовательно, служит базой рекурсии. Декомпозиция задачи состоит в простом переходе к следующему испытанию. Фактически мы имеем рекурсивное определение серии испытаний до первой неудачи. В чем же необычность "вероятностной рекурсии"? Функция обращается сама к себе с тем же самым значением аргумента p, а проблема остановки алгоритма решается вовсе не за счет изменения её аргумента, а за счет внешнего датчика, то есть получения конкретных значений другой вспомогательной функции. В данном случае это функция rnd(1), которая, по сути, является неявным аргументом функции vmat(p).

Умея решать задачу A, для решения подзадачи B, то есть получения "серии серий" испытаний до первой неудачи, можно предложить такую функцию:

 

Случай n=1 является базой рекурсии, а далее мы имеем простую повторительную рекурсию.

 Контрольный пример:

v := mas(9, 0.8),     vT = [1  8   10   0   2   6   2   4   3].

Home Содержание Схемы ООД Доска объявлений Поиск