题目:

给你一个等概率随机产生1~5的随机函数getRandom1To5,除此之外你不能使用任何额外的随机机制,如何用getRandom1To5实现等概率随机产生1~7的随机函数。
进阶1:给你一个以p的概率产生0,以1-p的概率产生1的函数getRandom01P,除此之外你不能使用任何额外的随机机制,如何用getRandom01P实现等概率随机产生1~6的随机函数。
进阶2:从1~M的等概率随机,怎么实现1~N的等概率随机

 

解答:

原问题难度:尉
进阶题难度:校

原问题解法:
第1步,getRandom1To5()等概率随机产生:1,2,3,4,5;
第2步,getRandom1To5()-1等概率随机产生:0,1,2,3,4;
第3步,(getRandom1To5()-1)*5等概率随机产生:0,5,10,15,20;
第4步,(getRandom1To5()-1)*5+(getRandom1To5()-1)等概率随机产生:0,1,2,3,…,23,24。注意这两个getRandom1To5()是指独立的两次调用,请不要化简。这是”插空儿”过程;
第5步,如果第4步产生的结果大于20,则重复进行第4步,直到产生的结果在0~20之间。同时可以轻易知道出现21~24的概率,会平均分配到0~20上。这是”筛”过程;
第6步,因为第5步的结果是等概率随机的产生0~20,所以第5步的结果再%7,就会等概率的随机产生0~6;
第7步,第6步的结果+1,就会等概率的随机产生1~7
过程结束。具体请参看如下代码中的getRandom1To7方法:

 进阶1:
虽然getRandom01P方法以p的概率产生0,以1-p的概率产生1,但是getRandom01P产生01和10的概率却都是p*(1-p),可以利用这一点来实现等概率随机产生0和1的函数:

第1步,实现等概率随机产生0和1的函数(如上代码中的getRandom01方法);
第2步,getRandom01()*2,等概率随机产生:0,2
第3步,getRandom01()*2+getRandom01(),等概率随机产生:0,1,2,3。注意这两个getRandom01()是指独立的两次调用,请不要化简;这是”插空儿”过程;
第3步说明我们已经可以实现等概率随机产生0~3的函数,具体请参看如下代码中的getRandom0To3方法:

 第4步,getRandom0To3()*4+getRandom0To3(),等概率随机产生:0,1,2,…,14,15。注意这两个getRandom0To3()是指独立的两次调用,请不要化简;这是”插空儿”过程;
第5步,如果第4步产生的结果大于11,则重复进行第4步,直到产生的结果在0~11之间;同时可以轻易知道出现12~15的概率,会平均分配到0~11上。这是”筛”过程;
第6步,因为第5步的结果是等概率随机的产生0~11,所以第5步的结果再%6,就会等概率的随机产生0~5;
第7步,第6步的结果+1,就会等概率的随机产生1~6;
过程结束。进阶解法的全部代码请参看如下代码中的getRandom1To6方法:

进阶2:
如果读者真正理解了”插空儿”过程和”筛”过程,就可以知道,只要给定某一个区间上的等概率随机函数,就可以实现任意区间上的随机函数。
具体来说如果M>=N,直接进入如上所述的”筛”过程;如果M<N,先进入如上所述”插空儿”过程,直到产生比N的范围还大的随机范围后,再进入”筛”过程;
总结一下:调用k次Random(n),写成有k位的M进制,使得m^k>=n;然后除去大于等于n的数,剩下的就均匀分布了0…n-1了。
具体请参看如下代码中的getRandom1ToNFromM方法:

 

欢迎留言