Массив случайных целых чисел без повторений

Желательно, чтобы числа эти ещё и лежали в заданном диапазоне значений [min,max].

Если нас не особо волнует скорость алгоритма, поступить можно по-простому, как показано в листинге ниже.

Функция getRandomArrayUnique вернёт 0 если массив удалось заполнить или 1, если переданы ошибочные параметры (например, мы требуем 100 различных целых значений, лежащих в диапазоне от 0 до 9).

#include <iostream>
using namespace std;

int getRandomArrayUnique (int size, int *arr, int min, int max) {
 //Генерация массива arr из size случайных целочисленых уникальных значений,
 //принадлежащих интервалу [min,max]
 //return 0 = OK, 1 = error
 int i, j;
 int duplicate;
 int value, diapazone = max-min+1;
 if (diapazone<1 || size<0 || size>diapazone) {
    return 1;
 }
 for ( i= 0; i<size; i++ ) {
  for ( ; ; ) {
   value= min+rand()%diapazone;
   duplicate= 0;
   for ( j= 0; j<i; j++ ) {
    if ( value == arr[j] ) { duplicate= 1; break; }
   }
   if ( !duplicate ) { break; }
  }
  arr[i]= value;
 }
 return 0;
}

int main(void) {
 int size = 100, min = 0, max = 99;
 int *arr = new int [size];
 if (!arr) {
  cout << "No memory!"; return 1;
 }
 int res = getRandomArrayUnique (size,arr,min,max);
 if (res) cout << "Bad data!";
 else for (int i=0; i<size; i++) cout << arr[i] << " ";
 cin.sync(); cin.get(); return 0;
}

Все 100 выведенных программой чисел будут разными, так что ей придётся использовать весь диапазон значений от 0 до 99 включительно.

Если критична скорость выполнения, начинается программистская эзотерика и поджирание дополнительной оперативной памяти. Например, код мог бы быть таким:

#include <iostream>
using namespace std;

int getRandomArrayUnique (int size, int *arr, int min, int max) {
 //Генерация массива arr из size случайных целочисленых уникальных значений,
 //принадлежащих интервалу [min,max]
 //return 0 = OK, 1 = Bad data, 2 = No memory
 int i, size2, index, diapazone;
 diapazone = max-min+1;
 if ( diapazone<1 || size<0 || size>diapazone ) {
  return 1;
 }
 if ( size == 0 ) { return 0; }
 int *arr2 = new int [diapazone];
 if (!arr2) {
  return 2;
 }
 for ( i= 0; i<diapazone; i++ ) {
  arr2[i]= min+i;
 }
 size2= diapazone;
 for ( i= 0; i<size; i++ ) {
  index= rand()%size2;
  arr[i]= arr2[index];
  size2--;
  arr2[index]= arr2[size2];
 }
 if (arr2) delete arr2;
 return 0;
}

int main(void) {
 int size = 100, min = 0, max = 99;
 int *arr = new int [size];
 if (!arr) {
  cout << "No memory!"; return 1;
 }
 int res = getRandomArrayUnique (size,arr,min,max);
 if (res==1) cout << "Bad data!";
 else if (res==2) cout << "No memory!";
 else for (int i=0; i<size; i++) cout << arr[i] << " ";
 cin.sync(); cin.get(); return 0;
}

Следует иметь в виду, что стандартная функция rand() генерирует машинно-зависимую последовательность чисел, то есть, при каждом запуске на конкретном компьютере может генерироваться одна и та же цепочка значений. Поэтому часто применяют функцию srand(), позволяющую получить последовательность на основе некоторого начального значения (ключа). В качестве такого ключа может служить, например, текущее системное время: srand(time(NULL));

Коды из заметки проверялись на оказавшемся под рукой Visual C++ 2010 Express, в 15-м может понадобиться, как всегда, волшебная директива.

08.09.2016, 17:59 [7067 просмотров]