algorithm - 使用均匀分布的 rand100() 编写函数 rand30() 返回 1 到 100

Question

请尝试编写rand30()返回 1 到 30 的函数。

你有rand100()功能。

Answer 1

假设函数返回整数：

int r = rand100();
while (r > 90) {
    r = rand100();
}
return 1 + (r - 1) % 30;

其中%运算符表示模数。

当我们均匀分布 100 个输入数字时，要获得 30 个输出数字的均匀分布，我们能做的最好的事情是将 3 个输入数字映射到一个输出数字。必须丢弃剩余的 10 个输入。

我们平均多久调用一次 rand100？1 次 90% 2 次 9% 3 次 0.9% ...

平均值为 1.111111