С/С++ | Выбор 10 случайных элементов из массива

[Vovius]

Надо реализовать такую штуку.

Имееться масив на (макс) 200 чисел

Заполняеться просто от 1 до 200, надо что бы прога выдала 10 из них полным рендомом, причём что бы не повторялись, кто знает как это сделать на с++ а ещё лучше в с++ builder 6.0.

[Cyberhawk]

Цитата:



надо что бы прога выдала 10 из них полным рендомом



Первые 10 или вообще? Если вообще, то как ты узнаешь, какие именно 10 выданы рандомом, а какие заполнены каким-то другим образом?

Короче, я толком не понял даже формулировки задачи. И какой диапазон у членов массива? И что значит
Цитата:



Имееться масив на (макс) 200 чисел



? Произвольный размер что ли?

Короче, ждем конкретизации задачи.

[XCodeR]

Vovius




Цитата:



Заполняеться просто от 1 до 200



в С++ нумерация идет с 0, а не с 1.



Допустим исходный массив mass.




Цитата:



int randoms[10],ri;

Randomize();

for(int i=0;i

[pva]

Код: Выделить всё

#include <vector>
#include <cstdlib>
int main()
{
  // >> Надо реализовать такую штуку.
  // >> Имееться масив на (макс) 200 чисел
  std::vector<double> array1(200);
  // >> Заполняеться просто от 1 до 200, 
  for(unsigned n=0; n<array1.size(); +n) array1[n] = n + 1;
  // >> надо что бы прога выдала 10 из них полным рендомом, 
  std::randomize();
  for(unsigned n=0; n<10; ++n)
  {
    unsigned rand_index = std::random(array1.size());
    std::cout << array1[rand_index] << std::endl;
    // >> причём что бы не повторялись, 
    std::vector<double>::iterator i = array1.begin();
    std::advance(i, rand_index);
    array1.erase(i);
  }
  // >> кто знает как это сделать на с++ а ещё лучше в с++ builder 6.0.
  // работает с любым компилятором C++ 3.3.2 под любую ОС
  return 0;
}

[Vovius]

Cyberhawk

Ну вот видьшь ниже всё народ понял.



XCodeR

Спасибо за команду для рандома.



pva

Спасибо полезный исходник.

[Vovius]

pva

Небольша опечатка, должно быть

Код:

Код: Выделить всё

for(unsigned n=0; n<array1.size(); ++n) array1[n] = n + 1;

А ещё можно воспользоваться

random_shuffle

. Правда, если нужны только 10 элементов из 200 это будет слегка оверкилл. С другой стороны, он гарантированно линейный от размера массива (т.е. будет сделано 200 перестановок), а вариант pva, если ничего не путаю имеет сложность O(m*n) в худшем/среднем случае, где n - число требуемых элементов, а m - размер массива.



Ещё такое придумалось:



Код:

Код: Выделить всё

std::vector<int> array; //считаем, что как-то уже заполнено
std::set<size_t> used;
std::list<int> out;
for (size_t i = 0; i < n; ++i)
{
    size_t j = rand() % array.size();
    while (used.find(j) != used.end())
        j = (j+1) % array.size();
    out.push_back(array[j]);
    used.insert(j);
}

Идея сводится к тому, что просто храним список использованных ключей. Если выпадает уже использованный, то перебираем все за ним следующие на предмет нахождения неиспользованного. Худший случай - O(n*n*logn), лучший - O(n*log n). Если n