【转】趣题: 一道面试题的解法：随机数生成 原题: Given a random number generator which can generate the number in range (1,5) uniformly. How can you use it to build a random number generator which can generate the number in range (1,7) uniformly? 译文: 给定一个随机数生成器， 这个生成器能均匀生成 1 到 5(1,5)的随机数， 如何使用这个生成器生成均匀分布的 1 到 7(1,7)的数? 用(1,5) 生成器去扩展它的生成数范围，一次不行，我两次呢？没错，我们先后取两次，然后把结果相乘，那么可以知道，这两个数相乘后的范围是 125。 并且取到 125 中间的任何一个数的可能性是相同的。21 是 7 的 3 倍，于是我们就有了 这样的映射: 13 1 46 - 2 1921-7 如果得到的数大于 21，则重取。这样做，我们至少可以保证，生成的 17 的数的概率是相同的，因此满足题目的要求。 算法二： 二进制，由于 7 的二进制是 111 1-2 映射到 0，3 跳过，4-5 映射到 1 生成三位的二进制即可 -随机数范围扩展方法总结【转】问题描述 已知 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内，则重新取样 解决方法 CPP CODEint random5()int val =0;do val =3*(random3()-1)+ random3();while(val 5);return val;归纳总结 将这个问题进一步抽象，已知 random_m()随机数生成器的范围是1, m 求 random_n()生成1, n范围的函数，m t);return val;