Показать полную графическую версию : Нужен алгоритм выборки
IksSafonsky
06-12-2004, 17:09
Нужно получить n неповторяющихся целых чисел, равномерно распределенных от 1 до N (n <= N). Считаем, что функция, выдающая _одно_ псевдослучайное число, есть.
Просто проверять каждое вновь получаемое число на совпадение со всеми выпавшими до него, при совпадении бросать снова и снова проверять - долго и тупо. Не подскажет ли кто-нибудь более быстрый алгоритм?
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
vBulletin v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.