Q如何在特定范围内获取随机整数?
A显而易见的方法,
rand() % N /* POOR */(它试图返回从0与N-1)很糟糕,因为许多随机数生成器的低位非常不随机。(参见问题 13.18。)一个更好的方法是类似于
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
如果你不想使用浮点数,另一种方法是
rand() / (RAND_MAX / N + 1)如果你只需要以 1/N的概率做某事,你可以使用
if(rand() < (RAND_MAX+1u) / N)所有这些方法显然都需要知道RAND_MAX(ANSI#define在<stdlib.h>),并且假设N远小于RAND_MAX.
当N接近RAND_MAX,并且随机数生成器的范围不是的倍数N(即如果(RAND_MAX+1) % N != 0),所有这些方法都会失效:一些输出比其他输出出现的频率更高。(使用浮点数并不有帮助;问题在于rand返回RAND_MAX+1个不同的值,它们不能总是平均分配到N个“桶”中。)如果这是一个问题,你唯一能做的就是调用rand多次,丢弃某些值
unsigned int x = (RAND_MAX + 1u) / N; unsigned int y = x * N; unsigned int r; do { r = rand(); } while(r >= y); return r / x;
对于这些技术中的任何一种,如果需要,可以轻松地调整范围;范围在 [M, N] 内的数字可以这样生成:
M + rand() / (RAND_MAX / (N - M + 1) + 1)
(顺便说一句,请注意RAND_MAX是一个常量,告诉你 C 库的固定范围rand函数是。你不能设置RAND_MAX为其他值,也没有办法要求rand返回其他范围内的数字。)
如果你使用的是返回 0 到 1 之间浮点值的随机数生成器(例如问题 13.15 中提到的 PMrand 的最后一个版本,或问题 13.21 中的 drand48),你只需要将该生成器的输出乘以PMrand(在问题 13.15 中提及)或drand48(在问题 13.21 中提及)),你需要做的就是将该生成器的输出乘以N-1NN:
(int)(drand48() * N)
参考文献:K&R2 第 7.8.7 节,第 168 页
PCS 第 11 节,第 172 页