PDA

Показать полную графическую версию : Нужен алгоритм выборки


IksSafonsky
06-12-2004, 17:09
Нужно получить n неповторяющихся целых чисел, равномерно распределенных от 1 до N (n <= N). Считаем, что функция, выдающая _одно_ псевдослучайное число, есть.
Просто проверять каждое вновь получаемое число на совпадение со всеми выпавшими до него, при совпадении бросать снова и снова проверять - долго и тупо. Не подскажет ли кто-нибудь более быстрый алгоритм?

McDAK
07-12-2004, 07:04
IksSafonsky
Толи я смысл задачи не уловил, толи... Случайной выборкой тут и так ничего не выйдет, ведь получаемые числа не будут распределены равномерно. Если заполнять диапазон от 1 до N до предела, то получится ряд чисел с шагом единица, в получении такого ряда вообще не вижу проблем. Если задаться произвольным целым шагом (в нецелом смысла нет), то создаем цикл от 1, в цикле включаем счетчик, что бы знать n, на каждом новом шаге определяем новое число, добавляя шаг к предыдущему числу и проверяем условие, что бы вновь полученное число не превысило N. В общих чертах так, по идее проще валенка или я чего-то не допер с просонья? В таком случае прошу меня вразумить.

shurikan
07-12-2004, 20:01
IksSafonsky
int i;
int n;
int found[N]; // это с помощью malloc
int data[N]; // ...
...
for (i=0; i<N; ++i)
{
data[i] = i+1;
}

n = 0;

while (N>1)
{
i = random(N--);

found[n++] = data[i];

for (int k=i; k<N; ++k)
{
data[k] = data[k+1];
}
}

found[n] = data[0];


:)




© OSzone.net 2001-2012