заполнение массива со случайным числом

Я пытаюсь заполнить массив 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 цикла, один для того, чтобы пересечь массив и в то время как для выбора случайного числа. В каждом повторении цикла с условием продолжения число может вновь появиться и порождение другого цикла с условием продолжения. Там более быстрый путь состоит в том, чтобы сделать это?

10
задан James 29 August 2012 в 09:43
поделиться

9 ответов

Вы можете последовательно заполнить массив, а затем перемешать его. Это предотвратит необходимость создания более 20 случайных чисел.

Перемешивание Фишера-Йейтса : можно выполнить за O (n) раз.

Из википедии:

При правильной реализации перетасовка Фишера – Йейтса является несмещенной, так что каждая перестановка одинаково вероятна. Современная версия алгоритма также довольно эффективна, требуя только времени, пропорционального количеству перетасовываемых элементов, и не требует дополнительного места для хранения.

19
ответ дан 3 December 2019 в 13:37
поделиться

Вы можете заполнить массив числами от 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;
}
9
ответ дан 3 December 2019 в 13:37
поделиться

Я бы поместил 20 случайных чисел в массив, затем скопировал в другой массив из 20 элементов, отсортировал один массив, и для каждого числа в отсортированном массиве нашел соответствующее число в неотсортированном массиве и поместил туда индекс сортировки.

0
ответ дан 3 December 2019 в 13:37
поделиться

Если вы можете использовать контейнеры, я бы просто заполнил std :: set числами от 1 до 20.

Затем вы можете извлечь случайное число из своего набора и вставить его в массив.

0
ответ дан 3 December 2019 в 13:37
поделиться

что-то вроде этого?

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; 

}
0
ответ дан 3 December 2019 в 13:37
поделиться

Пример кода для Фишера-Йейтса:

#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;
}
0
ответ дан 3 December 2019 в 13:37
поделиться

В вашем коде есть возможность очень длительного цикла. Если вы находитесь внутри цикла while (! Done), нет никакой гарантии, что вы когда-нибудь закончите. Очевидно, что с массивом из 20 элементов это на практике не будет проблемой, но может вызвать проблемы, если вы увеличите его до многих тысяч элементов.

Более надежным решением было бы последовательно заполнить массив, а затем перетасовать его.

1
ответ дан 3 December 2019 в 13:37
поделиться

Посмотрите на std :: random_shuffle и std :: vector .

15
ответ дан 3 December 2019 в 13:37
поделиться

Другой возможный способ

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. То же, что и исходный

0
ответ дан 3 December 2019 в 13:37
поделиться
Другие вопросы по тегам:

Похожие вопросы: