生成可被N整除的随机数的最佳算法

Question

有没有更好的算法来完成以下任务？

我正在尝试生成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?
    }

- user593747

---

仅使用 rand() * n 真的有益吗？生成随机数数组，然后再随机选择一个真的会提高效率吗？ - cnicutar

我知道生成一个7的倍数随机数最简单的方法是7*rand()。如果您需要更具体的需求，您需要清楚地陈述要求... - R.. GitHub STOP HELPING ICE

在编程中，你应该注意溢出问题：当 j > INT_MAX / 7 时，7*j 将会发生溢出。 - Foo Bah

Answer 1

为什么你不能只是这样做呢？

return (rand() % MAX) * 7;

它几乎做了同样的事情。

其中MAX足够小，以避免在乘以7时溢出。您可以定义为：

const MAX = INT_MAX / 7;

或者如果你希望它更快，你可以尝试这样做：

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

- Mysticial

---

百分号或与运算符会使分布失真，尽管如果RAND_MAX是2的幂，则 & 0xFF 不应该造成偏差。 - harold

@harold：我认为RAND_MAX保证是2的幂。 - Mooing Duck

@MooingDuck，我能找到的唯一保证是它必须至少为32767。 - harold

Answer 2

随机生成可被7整除的数字最有效的方法是先生成一个随机数，然后将其乘以7。

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

- K-ballo

---

那里的%操作会使分布偏斜。为什么不直接除以7再乘以7呢？这也会使分布偏斜，但更简短。 - harold

Answer 3

为什么要生成一堆随机数，然后再从中随机选择一个？你已经有了核心思想：生成一个随机数并乘以7。`potentialNums` 数组没有增加任何价值。

- Wyzard

Answer 4

为了加快速度，首先使用快速随机生成函数 在这里找到，这应该使生成随机数的实际过程更快。

接下来，您可以将随机数乘以7，它总是7的倍数，但是，如果这个乘法导致int溢出（这在随机数中很可能发生），则始终可以取前几位的掩码并将其相乘。

例如：

randomNumber = (generatedRandom & 0x00FFFFFF) * 7

- Serdalis