等概率随机函数

昨天在做练习题的时候,看到了一道设计等概率随机函数的练习题,突然想到了之前看到过的问题,故仔细求解。


问题如下:

现有一个等概率随机函数f5,返回1~5这5个自然数随机一个数,需要用f5来构造f7,返回1~7这7个自然数的随机一个数,请问f7该如何构造?


我灵光一现,这个简单啊,f5+f5%3,OK。但是仔细想想,好像不对,f5%3中,0的概率是1/5,1和2的概率是2/5,所以整个算法产生6和7的概率,要高于产生5的概率。

仔细想了想,等概率,是不是意味着,如果我有30个数,等概率取出来,那么我只要从这30个数中能够让他取到1~7的时候返回,其余时候重新去取,不就可以了?而取1~7,是不是也就意味着取到1~21,我用这个结果%7+1就可以了,所以算法如下:

while(x < 21) {

x = 5 * (f5 - 1) + f5

}

return 1 + x%7;

取1到25个自然数等概率,然后大于21的舍弃重新去取,最后的结果模7加1,搞定。

上一篇:PHP数据结构之——链表


下一篇:PHP 自动载入