学步园

这是面试中常遇到的一个问题. 举例来说, 给你一个 0~4范围之内的随机数生成器, 如何得到一个0~12范围内的随机数生成器?

常见的想法是 利用0~4生成器, 生成三次的结果相加, 得到0~12, 可惜这样的随机数不是均匀的, 特别是0~12中间的一些数字出现的概率会大一些.

程序可以证明这一点:

<?php
function get_random_0_4()
{
    return rand()%5;
}

$arr = array();

for ($i=0; $i<1000; $i++)
{
    $j = get_random_0_4();
    $j += get_random_0_4();
    $j += get_random_0_4();
    if (!isset($arr[$j]))
    {
        $arr[$j] = 0;
    }
    $arr[$j] ++;
}
                                                                                                                                                                                 
$arr = array_flip($arr);
asort($arr);
$arr = array_flip($arr);

print_r($arr);

执行结果: 可以看出明显的中间的数字出现的次数更多.
Array
(
    [0] => 13
    [1] => 16
    [2] => 49
    [3] => 83
    [4] => 125
    [5] => 146
    [6] => 157
    [7] => 119
    [8] => 134
    [9] => 84
    [10] => 42
    [11] => 25
    [12] => 7

)

后来经过重新思考之后, 觉得应该这样做, 把0~4随机数作为一个5进制数, 第一次生成的0~4作为5进制数的最低位, 第二次生成的五进制数作为第二位, 这样两个0~4的随机数可以生成一个 范围是0~24的随机数. 把>12的数字丢弃, 则可生成一个范围是0~12的随机数啦.

代码如下:

<?php

function 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);

运行结果如下: 看上去0~12之间的出现的概率都差不多.
Array
(
    [0] => 76755
    [1] => 77146
    [2] => 76763
    [3] => 76529
    [4] => 77075
    [5] => 76712
    [6] => 77476
    [7] => 76960
    [8] => 76821
    [9] => 77301
    [10] => 76844
    [11] => 76554
    [12] => 77064
)