Лучший алгоритм для случайной генерации числа, кратного N

#c #c #algorithm

#c #c #алгоритм

Вопрос:

Есть ли лучший алгоритм для выполнения следующего?

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

Есть ли более эффективный / лучший способ случайной генерации чисел, которые делятся на 7? Есть ли лучший способ, которым я мог бы закодировать / сделать это?

     unsigned int generateRandomNumberDivisibleByN( unsigned int n, unsigned int num=10 )
    {
        // Post: Generate many different random numbers that are divisible by n, then randomly select one of
        //       of those numbers to return.

        unsigned int potentialNums[num];

        for (int i=0, j=2; i<num; i  , j=rand()%INT_MAX)
        {
            potentialNums[i] = j*n;
        }

        return potentialNums[ rand()%num ]; // should this be rand()%(num-1) so it never returns an invalid array index?
    }

1. Действительно ли есть преимущество над just rand() * n ? Действительно ли генерация массива случайных чисел и затем случайный выбор одного из них что-нибудь улучшат?

2. Самый простой способ, который я знаю, сгенерировать случайное число, кратное 7, — это 7*rand() . Если у вас есть более конкретные потребности, вам нужно четко указать требования…

3. Вы должны быть осторожны с переполнением: когда j > INT_MAX / 7 7*j произойдет переполнение.

Ответ №1:

Почему вы не можете просто сделать это?

 return (rand() % MAX) * 7;

Он делает почти то же самое.

Где MAX достаточно мало, чтобы избежать переполнения при умножении на 7. Которое вы можете определить как:

 const MAX = INT_MAX / 7;

Или, если вы хотите, чтобы это было быстро, вы можете сделать что-то вроде:

 return (rand() amp; 0xff) * 7;

1. Операция % или amp; приведет к искажению распределения, хотя amp; 0xFF не должна искажаться, если RAND_MAX является степенью двойки.

2. @harold: я думаю RAND_MAX , что гарантированно будет степенью двойки.

3. @MooingDuck единственная гарантия, которую я могу найти, это то, что оно должно быть не менее 32767

Ответ №2:

Наиболее эффективный способ случайной генерации числа, кратного 7, — это сгенерировать случайное число, а затем умножить его на 7.

 return ( rand() % ( INT_MAX / 7 ) ) * 7

Ответ №3:

Зачем генерировать кучу случайных чисел, а затем выбирать одно из них случайным образом? У вас уже есть основная идея: сгенерируйте случайное число и умножьте его на 7. potentialNums Массив не добавляет никакого значения.

Ответ №4:

Чтобы сделать это намного быстрее, сначала используйте функцию быстрой генерации случайных чисел, найденную здесь, это должно значительно ускорить фактический процесс создания случайных чисел,

Затем вы можете умножить случайное число на 7, и оно всегда будет кратно 7, однако, если это умножение вызывает переполнение int (что с вероятностью случайных чисел), вы всегда можете взять маску из первых нескольких битов и умножить их.

например

randomNumber = (generatedRandom amp; 0x00FFFFFF) * 7