[原]等概率随机函数

    最近面试呀,肯定又接触了不少以前没接触过的东西。这不,又遇上一个,整理了一段时间,就准备发上来啦。

    关于等概率随机函数,以前都是用随机数生成函数 直接给定范围,生成随机数。没有多想。

    这个的主要意思其实就是  用一个已知的等概率随机函数去完成另一个函数。

eg:已知函数 f5() 该函数的作用是生成一个 1-5 的随机数。请用该函数实现另一个函数 f7() 产生 1-7 的随机数。

ps:看上去好像实际过程中这玩意其实没什么用。1-7 rand 一下不就有了么。。其实这里面 比较重要的还是 了解 数学思想在实际中的应用。数学用的熟练了,就能写出比这有用多的东西啦。

    1. 使用一个算数式 扩展 f5() 产生的随机数。

    例如 : ( f5()-1 ) + f5()

    OK,这样一计算我们就发现,这个结果已经被扩展到了  1-9。但是!有的朋友应该注意到了,1-9并不是等概率产生的。我们来看产生的数字表格。

    

1 2 3 4 5
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8
4 5 6 7 8 9

    这样的话 最低概率 是 1 出现的概率是 1/25 最高是 5出现的概率 5/25。

    2. 跟NO.1类似,仍然是用 一个算数式扩展 f5()。 

    例如 : f5() + f5()%3

    这个算术式比第一种要好一些,虽然也不是等概率随机,但是基本差不多了,而且数字范围正好就是 1-7


1 2 3 4 5
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7

    其中,f5()%3产生0的概率是 1/5 而产生1和2的概率是  2/5

    3.等概率随机。

    例如:(f5()-1)*5+f5()

    通过这个式子我们能得到什么?是的,等概率随机的 1-25的随机数。其中包括1-7,其实这样我们就已经得到了结果,只要我们只取其中的1-7其他数字全部抛弃,我们就可以获得 等概率的1-7随机数。虽然然获得1-7的概率不是 1/7,但是概率确实相等的,只要多取几次就可以了。

    改进:

    我们继续改进一下这个方案,因为我们的目的是1-7,而上述方案,我们只有7/25的概率达到目的。多循环几次效率自然就底了。

    映射:

    我们找到一个小于25的7的倍数,那就是21,我们将21以内的数字映射到7上,也就是说  (1-3)=1,(4-6)=2……..(19-21)=7。( ps.其实最后映射的时候不一定是1-3映射成1,这要考虑具体的程序实现。总之就是将每三个数字对应一个数字就可以了。)这样的话,我们获得 1-7随机数的概率仍然是相等的,我们有21/25的概率达到目的。而且1-7单个数字的获得概率是 3/25,已经比较接近1/7了。 我们只要丢弃 22-25四个数字就可以了。

    程序实现:

function f7()
{
	$num = 0;
	do
	{
                $num = ( f5() - 1 ) * 5 + f5();

	}while($num > 21);

	return 1 + $num%7;   // ( 7,14,21 映射为 1 )
}