заполнение массива со случайным числом
Я пытаюсь заполнить массив 20 ints с числами от 1-20 в случайной последовательности. вот мой код:
int lookup[20]={0};
int array[20]={0};
srand(time(NULL));
for(int i=0;i<20;++i){
bool done=false;
while(!done){
int n=rand()%20;
if(lookup[n]==0){
array[i]=n;
lookup[n]=1;
done=true;
}
}
}
Я создал массив поиска, чтобы проверить, не выбрано ли случайное число еще и сохранило его в массиве. Поскольку Вы видите, что я создал 2 цикла, один для того, чтобы пересечь массив и в то время как для выбора случайного числа. В каждом повторении цикла с условием продолжения число может вновь появиться и порождение другого цикла с условием продолжения. Там более быстрый путь состоит в том, чтобы сделать это?
9 ответов
Вы можете последовательно заполнить массив, а затем перемешать его. Это предотвратит необходимость создания более 20 случайных чисел.
Перемешивание Фишера-Йейтса : можно выполнить за O (n) раз.
Из википедии:
При правильной реализации перетасовка Фишера – Йейтса является несмещенной, так что каждая перестановка одинаково вероятна. Современная версия алгоритма также довольно эффективна, требуя только времени, пропорционального количеству перетасовываемых элементов, и не требует дополнительного места для хранения.
Вы можете заполнить массив числами от 1 до 20 и использовать std::random_shuffle
обратите внимание, что вам не нужен вектор, для этого подойдет простой массив.
пример :
#include <iostream>
#include <algorithm>
using namespace std;
int main( void )
{
int array[] = { 0, 1, 2, 3, 4 };
srand( unsigned( time(NULL) ) );
random_shuffle(array, array+5);
for(int i=0; i<5; i++)
cout << array[i] << endl;
return 0;
}
Я бы поместил 20 случайных чисел в массив, затем скопировал в другой массив из 20 элементов, отсортировал один массив, и для каждого числа в отсортированном массиве нашел соответствующее число в неотсортированном массиве и поместил туда индекс сортировки.
Если вы можете использовать контейнеры, я бы просто заполнил std :: set числами от 1 до 20.
Затем вы можете извлечь случайное число из своего набора и вставить его в массив.
что-то вроде этого?
int n = 20; //total element of array
int random = 0, temp=0, start=1;
for(int i=0; i < n; ++i,++start)
{
array[i] = start;
}
for(int i=0; i<n ; ++i)
{
random=rand()%(n-i)+i;
//swapping, you can make it as a function
temp = array[i];
array[i] = array [random];
array[random] = temp;
}
Пример кода для Фишера-Йейтса:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void shuffle(int array[], size_t size)
{
if(size) while(--size)
{
size_t current = (size_t)(rand() / (1.0 + RAND_MAX) * (size + 1));
int tmp = array[current];
array[current] = array[size];
array[size] = tmp;
}
}
int main(void)
{
srand((int)time(NULL));
rand(); // throw away first value: necessary for some implementations
int array[] = { 1, 2, 3, 4, 5 };
shuffle(array, sizeof array / sizeof *array);
size_t i = 0;
for(; i < sizeof array / sizeof *array; ++i)
printf("%i\n", array[i]);
return 0;
}
В вашем коде есть возможность очень длительного цикла. Если вы находитесь внутри цикла while (! Done), нет никакой гарантии, что вы когда-нибудь закончите. Очевидно, что с массивом из 20 элементов это на практике не будет проблемой, но может вызвать проблемы, если вы увеличите его до многих тысяч элементов.
Более надежным решением было бы последовательно заполнить массив, а затем перетасовать его.
Посмотрите на std :: random_shuffle и std :: vector .
Другой возможный способ
int array[20]={0};
int values[20];
for(int i = 0; i < 20; i++)
values[i] = i;
int left = 20;
for(int i = 0; i < 20; i++)
{
int n = rand() % left;
array[i] = values[n];
left--;
values[n] = values[left];
}
PS заполнен числами от 0 до 19, а не от 1 до 20. То же, что и исходный