Генераторы случайных чисел преобразуют стандартное равномерное распределение к требуемому виду, оставляя числа независимыми. В подразделе "Получение случайных чисел" представлены наиболее важные распределения.
Для тех, кто решит скрасить досуг программированием компьютерных игр и головоломок, окажутся полезными дискретные генераторы случайных чисел.
В бейсике "МК 85" датчик псевдослучайных чисел вызывается функцией RAN#. Она возвращает числа, распределенные равномерно в интервале [0;1[. Рандомизация входа в последовательность выполняется автоматически и обеспечивается запоминанием последнего полученного числа. Выполнение вшитого теста (команда TEST) переводит датчик в исходное состояние.
Программа 123. Распределение Бернулли
P(0)=1-p, P(1)=p, 0≤p≤1.
Размещение переменных. Здесь и далее результат выделен жирным шрифтом.
|
A |
B |
|
X |
p |
100 A=0:IF RAN#≤B;A=1
110 RETURN
Размер: 19, B
Программа 124. Биномиальное распределение
P(x)=n!/x!/(n-x)!px(1-p)x, x=0...n.
100 A=0:FOR C=1 TO D:IF RAN#≤B;A=A+1
110 NEXT C:RETURN
Размер: 31, D
Программа 125. Биномиальное распределение с малой вероятностью успеха
|
A |
B |
С |
D |
|
X |
p |
|
n |
10 B=LN (1-B)
100 A=0:C=0
110 C=C+1+INT (LN RAN#/B):IF C>D;RETURN
120 A=A+1:GOTO 110
Размер: 57, D
Программа 126. Полиномиальное распределение
P(x1, ... , xm)= n!/x1!/.../xm!p1...pmxm, е(i)xi=n., е(i)pi=1, i=1...n.
|
A |
B |
G |
F(A) |
G(A) |
F(A+A) |
|
m |
n |
p1 |
pm |
X1 |
Xm |
10 F=0:FOR C=1 TO A:F(C)=F(C)+F:F=F(C):NEXT
C
100 FOR C=1 TO A:F(C+A)=0:NEXT C
110 FOR E=1 TO B:D=RAN#:FOR C=1 TO A
120 IF D<F(C);F(C+A)=F(C+A)+1:GOTO 140
130 NEXT C
140 NEXT E:RETURN
Размер: 119, F(2*m)
Программа 127. Геометрическое распределение
P(x)=p(1-p)x-1, x=1,2, ...
|
A |
B |
|
X |
p |
100 A=0
110 A=A+1:IF RAN#>B THEN 110
120 RETURN
Размер: 27, B
Программа 128. Геометрическое распределение с малой вероятностью успеха
|
A |
B |
|
X |
p |
10 B=LN (1-B)
100 A=1+INT (LN RAN#/B):RETURN
Размер: 27, B
Программа 129. Гипергеометрическое распределение
P(m)=CmM Cn-mN-M/CnN
|
A |
B |
С |
D |
|
N |
M |
m |
n |
100 C=0:E=A:FOR F=1 TO D:IF RAN#≤B/E;C=C+1:B=B-1
110 E=E-1:NEXT F:RETURN
Размер: 49, F
Программа 130. Распределение Паскаля
P(x)= Cn-xn-1 px(1-p)n-x, x=1...n
|
B |
С |
D |
E |
|
p |
X |
|
n |
10 B=LN (1-B)
100 C=0:FOR D=1 TO E:C=C+INT (LN RAN#/B):NEXT D:RETURN
Размер: 41, E
Программа 131. Распределение Пуассона
P(x)=ax/x!e-a, a>0, x=1,2, ...
|
A |
B |
С |
|
a |
|
X |
10 A=EXP -A
100 B=1:C=0
110 B=B*RAN#:IF B≥A;C=C+1:GOTO 110
120 RETURN
Размер: 46, C
Программа 132. Равномерное распределение
j(x)=1/(b-a), a≤x<b.
|
A |
B |
С |
|
a |
b |
X |
Размер: 21, C
10 B=B-A
100 C=RAN#*B+A:RETURN
j(x)=lcxc-1e-lx/G(c), l>0, c>0, x>0.
Частный случай - c=1.
Программа 133. Экспоненциальное распределение
j(x)=le-lx
|
A |
B |
|
l |
X |
100 B=-LN RAN#/A:RETURN
Размер: 12, B
Частный случай - c натуральное
Программа 134. Распределение Эрланга
|
A |
B |
С |
|
l |
X |
c |
100 B=1:FOR D=1 TO C:B=B*RAN#:NEXT D:B=-LN B/A:RETURN
Размер: 32, D
В программах 135, 136 реализован метод браковки. Более быстрым является алгоритм, использующий полиномиальную аппроксимацию, однако он занял бы значительно больше места.
Программа 135. Гамма-распределение с параметром формы c<1
|
A |
B |
С |
D |
E |
F |
G |
|
l |
|
c |
X |
|
|
|
10 B=1/C:C=1/(1-C):A=-2/A:F=0
100 F=F+.5:IF FRAC F=0;D=E:RETURN
110 G=RAN#:D=G-B:E=G-C:IF
D+E>1 THEN 110
120 G=A*LN RAN#/(D+E):D=D*G:E=E*G:RETURN
Размер: 108, G
Программа 136. Гамма-распределение с произвольным параметром формы. Числа генерируются парами.
|
A |
B |
С |
D |
E |
F |
G |
H |
I |
J |
|
l |
|
c |
|
X2i |
X2i+1 |
|
|
|
|
10 D=INT C+2:B=C/D:C=1/(1-B):B=1/B:A=-2/A
100 E=0:F=0:FOR G=1 TO D
110 H=RAN#:I=H-B:J=H-C:IF
I+J>1 THEN 110
120 H=A*LN RAN#/(I+J):E=E+I*H:F=F+J*H:NEXT G:RETURN
Размер: 122, J
Программа 137. Бета-распределение
j(x)=xv-1(1-x)w-1G(v+w)/G(v)/G(w), 0≤x≤1, v>0, w>0
Метод браковки для бета-распределения основан на получении чисел, распределенных по гамма-, с использованием соотношения:
b(v, w)=g(1, v)/(g(1, v)+g(1, w))
Программа записана для частного случая, когда v и w - целые.
|
A |
B |
С |
D |
E |
F |
|
v |
w |
|
|
|
X |
100 C=A:GOSUB 110:F=-LN D:C=B:GOSUB
110:F=F/(F-LN D):RETURN
110 D=1:FOR E=1 TO C:D=D*RAN#:NEXT E:RETURN
Размер: 63, F
Программа 138. Распределение Вейбулла
j(x)=cxc-1/bcexp(-(x/b)c), b>0, c>0, x≥0.
100 A=B*(-LN RAN#)-(1/B):RETURN
Размер: 20, C
j(x)=1/s/Ц(2p) exp{-1/2 ((x-m)/s)2}, s>0.
Ниже приведены генераторы, основанные на разных принципах. Какой из них быстрее, определяется особенностями ЭВМ.
Программа 139. Точный генератор. Создает числа попарно:
X2i=Ц(-2ln R2i)
sin(2pR2i+1)s+m;
X2i+1=Ц(-2ln R2i)
cos(2pR2i+1)s+m;
где R2i- элемент равномерной последовательности;
X2i- элемент нормальной последовательности.
|
A |
B |
С |
D |
E |
|
m |
s |
X2i |
X2i+1 |
|
10 MODE 5
100 D=SQR (-2*LN RAN#):E=2*p*RAN#
110 C=D*SIN E*B+A:D=D*COS E*B+A:RETURN
Размер: 47, E
Программа 140. Использование закона больших чисел
X=(е(i)Ri-6)s+m, i=1...12
|
A |
B |
С |
D |
|
m |
s |
X |
|
Размер: 35, D
100 C=-6:FOR D=1 TO 12:C=C+RAN#:NEXT D:C=C*B+A:RETURN
Программа 141. Использование полиномиальной аппроксимации
X={Y-41/13440/n2(Y5-10Y3+15Y)}s+m,
где Yi=е(j)Rni+j, j=1...n, n=2
|
A |
B |
С |
|
m |
s |
X |
100 C=(RAN#-RAN#)*1.224744871
110 C=(C-7.626488E-4*C*(15+C*C*(C*C-10)))*B+A:RETURN
Размер: 67, C
Программа 142. Распределение Релея
j(x)=x/a exp(-x2/2/a), a>0, x>0.
|
A |
B |
|
a |
X |
Размер: 17, B
100 B=A*SQR (-2*LN RAN#):RETURN
Программа 143. Логистическое распределение
j(x)= p/s/Ц3 exp((x-m)p/s/Ц3)/{1+exp((x-m)p/s/Ц3)}2
|
A |
B |
С |
|
m |
s |
X |
10 B=SQR 3/p*B
100 C=RAN#:C=LN (C/(1-C))*B+A:RETURN
Размер: 36, C