c - 根据概率的 N 个随机选择

Question

此代码用于获取一定概率的随机数：如果r在 0 和 0.8 之间，则返回 8；r如果介于 0.8 和 1 之间，则返回2。

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

int main()
{
    srand(time(NULL));
    double r = rand() / (double)RAND_MAX;
    double sum = 8 + 2;
    if (r < 8 / sum) {
        printf("80% \n");
    } else {
        printf("20% \n");
    }  
}

但是如果我有两个以上的数字，比如 n，我该如何处理呢？我可以用多个 if-else 语句来处理它吗？或者还有什么？

Answer 1

简单的

1. O(n)及时创建一个概率数组（总和为 1.0）
2. 生成一个介于 0.0 和 1.0 之间的随机数
3. 及时遍历数组O(n)：
   • 如果随机数<元素的概率，停止
   • 否则按概率递减随机数并移动到下一个元素
4. 答案是与您停止的元素对应的数字

复杂的

1. 创建一个累积概率数组并将它们及时存储在一个数组中O(n)（这个数组应该有递增的值）
2. 生成一个介于 0.0 和 1.0 之间的随机数
3. 进行二进制搜索以及时找到作为>=随机数的最小元素O(log(n))。
4. 答案是与您停止的元素对应的数字

我没有包括必要的极端案例来解决。我相信你可以自己做。

Answer 2

除了 randomstring 的建议之外，您还可以考虑构建一个别名表- O(n log n) 来构建表，每个值 O(1) 来生成。