如何实现随机函数,其中每个后续值比前一个值更不可能？

Question

对于比较-标准的随机函数取数,比方说3,那么就意味着0,1和2每个人都有33%的机会返回.

我需要实现随机函数,让我们说它0.5意味着0有50%的机会返回,1是25%,2是12.5%,依此类推,直到无穷大.

我不能使用循环例如:

int SequencialRandom(double x)
{
    int result=0;
    while (DoubleRandom()>x) //DoubleRandom() returns randomized double that ranges from 0.0 to 1.0.
        result++;
    return result;
}

因为当我0.01输入参数时,它平均会循环100次,而且性能很差.这个问题有很好的算法吗？

Answer 1

你要找的是几何分布,由std :: geometric_distribution提供:

生成随机非负整数值i,根据离散概率函数分布:

P(i | p)= p·(1-p)ⁱ

该值表示获得单个成功所必需的是/否试验(每个试验以概率p成功)的数量.

示例代码:

#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <random>
int main()
{
    std::random_device rd;
    std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
    std::mt19937 gen(seed);

    // same as std::negative_binomial_distribution<> d(1, 0.5);
    std::geometric_distribution<> d;

    std::map<int, int> hist;
    for(int n=0; n<10000; ++n) {
        ++hist[d(gen)];
    }
    for(auto p : hist) {
        std::cout << p.first <<
                ' ' << std::string(p.second/100, '*') << '\n';
    }
}

分配输出:

0 **************************************************
1 ************************
2 ************
3 ******
4 **
5 *
6 
7 
8 
9 
10 
13