问题描述

已知random3()这个随机数产生器生成[1, 3]范围的随机数,请用random3()构造random5()函数,生成[1, 5]的随机数?

问题分析

如何从[1-3]范围的数构造更大范围的数呢?同时满足这个更大范围的数出现概率是相同的,可以想到的运算包括两种:加法和乘法

考虑下面的表达式:

3 * (random3() – 1) + random3();

可以计算得到上述表达式的范围是[1, 9]  而且数的出现概率是相同的,即1/9

下面考虑如何从[1, 9]范围的数生成[1, 5]的数呢?

可以想到的方法就是 rejection sampling 方法,即生成[1, 9]的随机数,如果数的范围不在[1, 5]内,则重新取样

解决方法

int random5()
{
    int val = 0;
    do {
        val = 3 * (random3() - 1) + random3();
    } while (val > 5);
    return val;
}

归纳总结

将这个问题进一步抽象,已知random_m()随机数生成器的范围是[1, m] 求random_n()生成[1, n]范围的函数,m < n && n <= m *m
一般解法:

int random_n()
{
    int val = 0 ;
    int t; // t为n最大倍数,且满足 t &lt;= m * m     
    do {         
        val = m * (random_m() - 1) + random_m();     
    } while (val > t);
    return val;
}

参考资料:

http://stackoverflow.com/questions/137783/expand-a-random-range-from-1-5-to-1-7

来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/1326