如何利用一个小范围随机数生成一个大范围的随机数?
这是面试中常遇到的一个问题. 举例来说, 给你一个 0~4范围之内的随机数生成器, 如何得到一个0~12范围内的随机数生成器?
常见的想法是 利用0~4生成器, 生成三次的结果相加, 得到0~12, 可惜这样的随机数不是均匀的, 特别是0~12中间的一些数字出现的概率会大一些.
程序可以证明这一点:
<?phpfunction get_random_0_4(){ return rand()%5;}function get_random_0_24(){ return get_random_0_4() * 5 + get_random_0_4();}function get_random_0_12(){ $num = get_random_0_24(); while ($num > 12) { $num = get_random_0_24(); } return $num;}$arr = array();for ($i=0; $i<1000000; $i++){ $j = get_random_0_12(); if (!isset($arr[$j])) { $arr[$j] = 0; } $arr[$j] ++; } $arr = array_flip($arr);asort($arr);$arr = array_flip($arr);print_r($arr);