Блог

Один из способов сделать это — создать пул или пакет чисел в требуемом диапазоне и выбирать из них. Это не намного сложнее, чем повторная проверка, чтобы увидеть, было ли уже выбрано число, и более эффективно. Ваша измененная программа теперь:

 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define ARRLEN  25          // how many to pick
#define NUMBERS 75          // range of available numbers
#if NUMBERS < ARRLEN        // precaution
    #error Impossible job!
#endif

int cmp(const void *a, const void *b)
// optional, for qsort
{
    return *(int *)a - *(int *)b;
}

int main(void)
{
    int arr[ARRLEN];                    // final array
    int bag[NUMBERS];                   // bag of available numbers
    int avail = NUMBERS;                // size of bag available
    srand((unsigned)time(NULL));

    // prepare the bag of available numbers
    for(int i = 0; i < NUMBERS; i  ) {
        bag[i] = i   1;
    }

    // fill the array with values from the bag
    for(int i = 0; i < ARRLEN; i  ) {
        int index = rand() % avail;     // random index into array
        arr[i] = bag[index];            // take that number

        avail--;
        bag[index] = bag[avail];        // replace with the one from the top
    }

    // just to check, sort the array, can be deleted
    qsort(arr, ARRLEN, sizeof arr[0], cmp);

    // output the result
    for (int i = 0; i < ARRLEN; i  ) {
        printf("%d ", arr[i]);
    }
    printf("n");

    getchar();
    return 0;
}
  

Я отсортировал массив, чтобы было легко увидеть, есть ли дубликаты. Эта qsort строка и cmp функция могут быть удалены.

Вывод программы из трех запусков

6 7 8 9 12 16 17 19 21 27 31 35 43 46 47 50 51 53 59 64 65 66 70 71 72
2 6 7 14 17 23 24 25 30 31 32 34 36 37 45 58 59 61 65 68 69 71 73 74 75
5 10 13 18 20 21 25 30 34 36 39 40 41 43 49 50 54 58 60 63 64 66 67 72 75

… но я получил бесконечный цикл.

просто замените

     while (k != 1)
    {
        arr[i] = rand() % 75   1;
        for (j = 0; j < 25; j  ) {
          ...
        }
    }
    k = 0;
  

Автор:

 do
{
  k = 0;
  arr[i] = rand() % 75   1;
  for (j = 0; j < 25; j  ) {
     ...
  }
} while (k != 1);
  

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

 do
{
  k = 0;
  arr[i] = rand() % 75   1;
  for (j = 0; j < i; j  )
  {
    if (arr[i] == arr[j])
    {
      k  ;
    }
  }
} while (k != 0);
  

поскольку теперь j не может принимать значения i, тест (k != 0) , а не (k != 1)

или лучше, потому что, когда найдено идентичное значение, нет причин продолжать

 do
{
  arr[i] = rand() % 75   1;
  for (j = 0; j < i; j  )
  {
    if (arr[i] == arr[j])
      break;
  }
} while (j != i);
  

Чтобы хорошо видеть значения, также добавьте пробел между ними и добавьте окончательную новую строку:

 for (i = 0; i < 25; i  )
{
    printf("%d ", arr[i]);
}
putchar('n');
  

После этих изменений компиляция и выполнение :

 pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall r.c
pi@raspberrypi:/tmp $ ./a.out
74 60 16 65 54 19 55 45 41 24 39 59 66 36 27 22 68 49 29 14 28 5 71 56 72 

pi@raspberrypi:/tmp $ ./a.out
16 34 62 29 74 41 3 43 69 17 61 22 28 59 7 65 5 46 60 20 66 14 49 54 45 

pi@raspberrypi:/tmp $ 
  

Редактировать

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

В отношении интересного предложения Weather Vane все наоборот: количество вызовов rand равно только количеству возвращаемых значений, но чем больше диапазон допустимых значений, тем больше размер массива, который может быть переполнен объемом памяти.

Вероятно, для 25 значений от 1 до 75 решение флюгера лучше … даже моему предложению, похоже, требуется всего 0,001 секунды на моем Raspberry pi, так что почти ничего

 int *fillint(int *arr, size_t size)
{
    int added = 0;
    int pos = 0
    while(pos != size)
    {
        int rv;
        do
        {
            added = 1;
            rv = rand();

            for(size_t index = 0; index < pos; index  )
            {
                if(arr[index] == rv)
                {
                    added = 0;
                    break;
                }
            }
        }while(!added)
        arr[pos  ] = rv;
    }
    return arr;
}
  

Еще одно небольшое изменение подхода флюгера к сумке — вместо того, чтобы готовить пакет со всеми доступными числами, просто объявите массив с максимальным количеством элементов, равным диапазону принятых чисел, инициализированных всем нулем (например int arr[75] = {0}; , в этом случае). Нет необходимости заполнять массив, вы просто увеличиваете элемент на 1 каждый раз, когда это число используется при заполнении вашего массива.

Чтобы убедиться, что вы используете только уникальное число, вы проверяете, равен ли соответствующий элемент массива нулю, если это так, используйте это число и увеличьте элемент. Если оно не равно нулю, вы знаете, что это число использовалось — сгенерируйте другое и повторите попытку.

Например, если количество целых чисел в массиве равно 25 , а максимальное значение любого целого числа равно 75 , вы могли бы сделать;:

 #define NINT 25
#define MAXI 75
...
    int arr[NINT],
        seen[MAXI] = {0};
    ...
    for (int i = 0; i < NINT; i  ) {    /* for each needed element */
        int tmp = rand() % MAXI   1;    /* generate a random in range */
        while (seen[tmp-1])             /* has been seen/used yet? */
            tmp = rand() % MAXI   1;    /* if so, generate another */
        seen[tmp-1]  ;                  /* incement element */
        arr[i] = tmp;                   /* assign unique value to arr */
    }
  

(примечание: seen индексы отображаются как tmp-1 для сопоставления с действительными индексами 0-74 , в то время как числа, сгенерированные для tmp , будут 1-75 использоваться rand() % MAXI 1 . Вы можете разместить любой диапазон, необходимый для этого типа отображения. Для использования диапазона чисел из 1000001 - 1000075 все равно потребуется только массив из 75 элементов seen .)

Для вывода чисел, используемых по порядку, вам просто нужно вывести индекс, соответствующий каждому из ненулевых элементов seen массива ( 1 для отображения обратно в 1-75 диапазон значений), например

     for (int i = 0; i < MAXI; i  )
        if (seen[i])
            printf (" %d", i   1);
    putchar ('n');
  

Поместив это в целом в короткий пример, вы могли бы сделать:

 #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NINT 25
#define MAXI 75

int main (void) {

    int arr[NINT],
        seen[MAXI] = {0};
    srand (time(NULL));

    for (int i = 0; i < NINT; i  ) {    /* for each needed element */
        int tmp = rand() % MAXI   1;    /* generate a random in range */
        while (seen[tmp-1])             /* has been seen/used yet? */
            tmp = rand() % MAXI   1;    /* if so, generate another */
        seen[tmp-1]  ;                  /* incement element */
        arr[i] = tmp;                   /* assign unique value to arr */
    }

    puts ("array:");
    for (int i = 0; i < NINT; i  ) {
        if (i amp;amp; i % 5 == 0)
            putchar ('n');
        printf (" -", arr[i]);
    }

    puts ("nnused:");
    for (int i = 0; i < MAXI; i  )
        if (seen[i])
            printf (" %d", i   1);
    putchar ('n');
}
  

(примечание: очевидно, что размер видимого массива будет ограничен доступным размером стека, поэтому, если ваш диапазон необходимых чисел превышает объем памяти, доступный для seen объявленного с автоматическим типом хранения, вам нужно будет создать seen массив с выделенным типом хранения).

Пример использования / вывода

 $ ./bin/randarr25-75
array:
  1 18 70 26 75
 29 31 58 22  9
  5 13  3 25 35
 40 48 44 57 56
 60 50 71 67 43

used:
 1 3 5 9 13 18 22 25 26 29 31 35 40 43 44 48 50 56 57 58 60 67 70 71 75
  

Независимо от того, используете ли вы пакет или массив для отслеживания увиденных чисел, результаты будут одинаковыми. Никто не лучше другого. Добавьте их оба в свой C-toolbox.

Во внутреннем цикле for , цикле для j, выполняйте итерацию до тех пор, пока j < i , чтобы проверить, было ли значение, сгенерированное на шаге i, уже сгенерировано на более раннем шаге.

Кроме того, инициализируйте значение k равным нулю каждый раз, когда вы проверяете предыдущие вхождения, это упрощает чтение кода.

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

Что-то вроде этого:

 for (i = 0; i < 25; i  )
{
    k = 1;
    while (k != 0)
    {
        arr[i] = rand() % 75   1;
        k = 0; 

        for (j = 0; j < i; j  )
        {
            if (arr[i] == arr[j])
            {
                k  ;
                break;
            }
        }
    }
}