Генерация псевдослучайных чисел

Генерация псевдослучайных чисел

     Случайные числа имеют разнообразные компьютерные приложения. Однако никакой алгоритмический процесс не способен сгенерировать по-настоящему случайные числа: при повторном запуске такого процесса мы получим ту же самую последовательность чисел. Случайный процесс не должен обладать таким свойством, и случайность можно сымитировать, запуская программу всякий раз с новой точки. Начальная точка обычно вычисляется по текущему значению системных часов компьютера, и к нашему генератору добавляется тем самым случайность положения часов.
     Использование постоянной случайной последовательности облегчает тестирование программы: после каждого исправления мы можем повторять ее на тех же самых данных. После того, как мы сочли, что программа работает правильно, можно добавить случайный выбор начальной точки.
     Существуют различные способы генерации случайных последовательностей; здесь мы рассмотрим лишь один из них. В методе смешанных вычетов очередное случайное число вычисляется на основе предыдущего. Вот как выглядит такой алгоритм:

function RanNum() returns float
	seed = (seed*p + i) mod m
	return seed/m
end RanNum

     Значение seed вычисляется по модулю m, поэтому оно всегда находится в интервале [0, m - 1]. После деления на m мы заведомо получаем число из отрезка [0, 1], которое и возвращается функцией.
     Если три константы p, i и m взаимно просты, то есть не имеют общего делителя, то период получившейся последовательности равен m - раньше повторений не будет. Если, например, p = 25173, i = 13849 и m = 65536, то написанная функция сгенерирует последовательность из 65536 попарно различных значений прежде, чем значения начнут повторяться. При тестировании программ можно положить начальное значение seed равным 0 - тогда будет всякий раз генерироваться одна и та же последовательность. После завершения тестирования можно в качестве начального значения переменной seed выбирать число секунд или миллисекунд текущего времени на системных часах - последовательность будет более случайной.

Случайная последовательность в произвольном интервале
     Зачастую в приложениях требуются случайные последовательности не из интервала [0, 1], а из других интервалов. Если нам нужна последовательность в интервале Low <= N < High, то ее сгенерирует функция:
(High - Low)* RanNum() + Low

Пример применения
     Допустим, что нам нужен список чисел от 1 до N в случайном порядке. Есть несколько возможностей сгенерировать такой список.

Первый способ
     Инициализируем элементы списка нулевыми значениями; тогда по мере помещения элементов в список еще не занятые ячейки будут оставаться нулевыми. Если выбранная нами случайная ячейка содержит нуль, то она еще не занята, и мы можем поместить в нее очередное число. Если же она занята, то мы просто генерируем случайный номер следующей ячейки. В результате мы приходим к такому алгоритму:

for i = 1 to N do
	list[i] = 0
end for
for i = 1 to N do
	repeat
		location = [N*RanNum() + 1]
	until list[location] = 0
	list[location] = i
end for

Первые несколько значений быстро займут свои места в списке; проблема этого метода, однако, заключается в том, что по мере заполнения списка становится все труднее и труднее помещать в него очередное значение. Поэтому даже в такой простой ситуации программа может работать довольно долго.

Второй способ
Как мы видели, проблема с реализацией первого способа возникает, если выбранная случайная ячейка оказывается "заполненной". В предлагаемом ниже варианте, обнаружив заполненную ячейку, мы просто проверяем следующие за ней до тех пор, пока не найдем свободную. В результате мы приходим к следующему алгоритму:

for i = 1 to N do
	list[i] = 0
end for
for i = 1 to N do
	location = [N*RanNum() + 1]
	while list[location] /= 0 do
		location = (location mod N) + 1
	end while
	list[location] = 1
end for

Этот способ работает достаточно быстро, однако если в списке быстро появится блок из подряд идущих заполненных клеток, то у нас будет довольно длинный подсписок, содержащий числа с сохранением их относительного порядка. Пусть, например, первые 25 из 100 ячеек уже заполнены случайными числами. Тогда имеется 25%-ная вероятность того, что очередная выбранная ячейка окажется среди первых 25, и соответствующее значение будет занесено в ячейку 26. При последующих выпадениях одной из первых ячеек мы занесем соответствующие значения в 27, 28 и т.д. ячейки. Такое может случиться в любой части списка, и мы получим блок ячеек, значения которых последовательны или почти последовательны.

Третий способ
В этом последнем способе сгенерированное случайное число указывает, сколько пустых ячеек, считая от текущей, следует пропустить прежде, чем заносить в список очередное число. В результате мы преодолеваем недостаток первого метода, поскольку используем каждое сгенерированное случайное число. Кроме того, снижается и вероятность записи последовательных значений в последовательные ячейки - такое может произойти только, если последовательные ячейки свободны, а сгенерированное число сравнимо с единицей по модулю числа оставшихся свободными ячеек. Вот реализация этого алгоритма:

for i = 1 to N do
	theList[i] = 0
end for
location = 1
freeCount = N
for i = 1 to N do
	skip = [freeCount*RanNum() + 1]
	while skip > 0 do
		location = (location mod N) + 1
		if theList[location] = 0 then
			skip = skip - 1
		end if
	end while
	theList[location] = i
	freeCount = freeCount - 1
end for

В этом алгоритме мы ведем счетчик свободных ячеек и генерируем случайное число, не превышающее значения счетчика. Это делается для того, чтобы не было необходимости проходить по списку несколько раз. Видно, что цикл while всегда завершается, поскольку даже на последнем проходе остается по крайней мере одна пустая ячейка.

Сайт управляется системой uCoz