Страница 2 из 2
Добавлено: 14 дек 2005, 18:09
DeeJayC
Naeel Maqsudov, и элементы массива уже нельзя считать случаными числами с равномерным распределением.
Добавлено: 14 дек 2005, 18:21
Naeel Maqsudov
Строго говоря, нельзя. Между тем надо подождать, что скажет автор вопроса. Оба предложенных решения ведут себя хорошо при k<n, что составляло главную проблему.
Кстати, а что можно сказать о распределении величины, которая получалась по исходному алгоритму:
array+=random(10)?
Добавлено: 14 дек 2005, 18:38
DeeJayC
слёту - ничего
Добавлено: 14 дек 2005, 20:30
Naeel Maqsudov
В формулировке выше была ошибка. P забыл прибавить.
Получилось пока вот что:
Код: Выделить всё
Sub Macro2()
K1 = 0: K2 = 1: N = 30: P = 0.5
xx = 0
For i = 0 To N - 1
x = xx + Rnd() * ((K2 - P) * (i + 1) / N + P - xx) + K1
ActiveCell.Offset(i, 0).Value = x
xx = x
Next
End Sub
Распределение дает конечно же не навномерное. График, построенный по усредненным значениям на 50 опытах выглядит не как линейная функция, а скорее как SQRT(X)
Приблизить его к линейному (практически сделать его линейным) можно так:
Код: Выделить всё
Sub Macro2()
K1 = 0: K2 = 1: N = 30: P = 0.5
xx = 0
For i = 0 To N - 1
x = xx + Rnd() * ((K2 - P) * (i + 1) / N + P * (i + 1) / N - xx) + K1
ActiveCell.Offset(i, 0).Value = x
xx = x
Next
End Sub
Однако на массиве из 30 значений в 50 опытах этот алгоритм дает более нормальное распределение, чем просто функция Rnd. При увеличении размерности массива алгоритм будет давать результат все более и более близкий к обычной функции Rnd.
Вот.
Добавлено: 14 дек 2005, 20:34
Naeel Maqsudov
Хе-хе! Так и есть!
Последний алгоритм рулит!
на 26000 разницы между сортировкой готового массива из RND и последним алгоритмом не заметно.
Добавлено: 15 дек 2005, 11:06
DeeJayC
Увы, но это бездоказательно.... Меня лично ломает сидеть и вычислять....
И ещё!!!!
более нормальное распределение - осторожнее в формулировках.
Добавлено: 15 дек 2005, 14:19
Naeel Maqsudov
На 30 значениях Random() дала среднее 0.591, а моя функция 0.525.
На достаточно большом количестве значений они реально позволяют получить чрезвычайно сходный результат.
Просто не знаю, с какой стороны и подступиться к доказательству....
Добавлено: 15 дек 2005, 16:53
DeeJayC
Усреднение численное - это - увы - не доказательство. А как такие штуки доказывать - у Феллера описано.
Добавлено: 18 дек 2005, 00:48
AMDemon
Naeel Maqsudov, Выражаю тебе свою благодарность.
X[-1]=0
i=0..N-1:
X=X[i-1]+random((Kmax-P)*(i+1)/N-X[i-1])+Kmin
Этот алгоритм работает для большинства условий, только приходится слегка поработать с вещественными типами. Кстати говоря, гланая проблема сортировки - перемещение элементов. Во-первых структура, во-вторых на винчестере.