如何利用一个小范围随机数生成一个大范围的随机数?

68 阅读 0 评论 45 点赞

我是靠谱客的博主乐观纸鹤，最近开发中收集的这篇文章主要介绍如何利用一个小范围随机数生成一个大范围的随机数?，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这是面试中常遇到的一个问题. 举例来说, 给你一个 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
)