Re: масив чисел

From

Oleg I. Khovayko ()

To

Oleg Polubasoff

Date

2003-01-07T23:33:51Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Oleg Polubasoff wrote:
> 
>     RND(n) часто определяют как random()%n, и для практических целей этого
> обычно вполне достаточно. Но, если, как ты говоришь, интересует именно
> "математически верный" алгоритм, то надо иметь ввиду, что результат
> random()%n может быть распределён не равномерно.

Естественно. Я это знаю. Типичный пример: random() дает числа 0..15,
а надо получить случайное число в диапазоне 0..9. Понятно, что если
сделать генератор "x = random() % 10", то числа из интервала 0..5 будут 
выпадать вдвое чаще, чем числа из интервала 6..9.

В свою защиту могу сказать то, что я приводил математически верный алгоритм 
ПЕРЕМЕШИВАНИЯ, а не генерации случайного числа. И акцентировался я именно на 
перемешивании. Поэтому генерацию случайного числа "схалявил". И писать было лениво,
н загромождать исходник-пример мало относящимся к делу мусором не хотелось.

А если уж хочется совсем равномерного распределения от 0 до N, то его делать можно так:

1. Находим некое максимально возможное int Z, такое, что (Z % N == 0) && (Z <= max_random())
2. Генерим равномерно распределенное число:
	int x;
	while((x = random()) >= Z);
	x %= N;

Особое внимание надо обратить на знак сравнения  ">= Z". Если наш random()
может выдавать нуль, надо писать именно ">= Z". Если же random() нуля вернуть не может
(а именно такие генераторы распространены наиболее широко), надо писать "> Z".

>     О том, что последовательные вызовы random() обычно не независимы, молчу.

Ну естественно! Не хватало нам еще физического генератора случайных чисел...

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)