1116人阅读
微软、谷歌、百度等公司经典面试100题_2011（34）
给定一个函数rand5()，该函数可以随机生成1-5的整数，且生成概率一样。现要求使用该函数构造函数rand7()，使函数rand7()可以随机等概率的生成1-7的整数。
很多人的第一反应是利用rand5() + rand()%3来实现rand7()函数，这个方法确实可以产生1-7之间的随机数，但是仔细想想可以发现数字生成的概率是不相等的。rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。
正确的方法是利用rand5()函数生成1-25之间的数字，然后将其中的1-21映射成1-7，丢弃22-25。例如生成(1，1)，(1，2)，(1，3)，则看成rand7()中的1，如果出现剩下的4种，则丢弃重新生成。
简单实现：
Java代码&&
public&class&Test&{&&&&&&&&public&int&rand7()&{&&&&&&&&&&&&int&x&=&22;&&&&&&&&&&&&while(x&&&21)&{&&&&&&&&&&&&&&&&x&=&rand5()&+&(rand5()&-&1)*5;&&&&&&&&&&&&}&&&&&&&&&&&&return&1&+&x%7;&&&&&&&&}&&&&&&&&}&&&&
&&&我的备注：
&&&&这种思想是基于，rand()产生[0,N-1]，把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机，而相反，借助其他方式来使用rand()产生随机数(如&rand5() + rand()%3&)都是不能保证概率平均的。
&&&&此题中N为5，因此可以使用rand5()*5+rand5()来产生2位的5进制数，范围就是1到25。再去掉22-25，剩余的除3，以此作为rand7()的产生器.
给定一个函数rand()能产生0到n-1之间的等概率随机数，问如何产生0到m-1之间等概率的随机数？
int&random(int&m,int&n){&&&&int&k=rand();&&&&int&max=n-1;&&&&while(k&m){&&&&&&&&k=k*n+rand();&&&&&&&&max=max*n+n-1;&&&&}&&&&return&k/(max/n);}
如何产生如下概率的随机数？0出1次，1出现2次，2出现3次，n-1出现n次？
int&random(int&size){&&&&while(true){&&&&&&&&int&m=rand(size);&&&&&&&&int&n=rand(size);&&&&&&&&if(m+n&size)&&&&&&&&&&&&return&m+n;&&&&}}
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：588834次
积分：6225
积分：6225
排名：第3090名
原创：11篇
转载：568篇
评论：36条
(2)(22)(14)(2)(1)(3)(8)(4)(7)(23)(2)(36)(24)(4)(4)(2)(1)(3)(7)(5)(20)(2)(8)(3)(4)(5)(2)(19)(6)(2)(1)(2)(3)(12)(32)(56)(44)(11)(36)(10)(22)(26)(2)(46)(29)(7)生成随机数rand函数的用法详解
字体：[ ] 类型：转载 时间：
本篇文章是对生成随机数rand函数的用法进行了详细的分析介绍，需要的朋友参考下
函数rand()是真正的随机数生成器，而srand()会设置供rand()使用的随机数种子。如果你在第一次调用rand()之前没有调用srand()，那么系统会为你自动调用srand()。而使用同种子相同的数调用 srand()会导致相同的随机数序列被生成。srand((unsigned)time(NULL))则使用系统定时/计数器的值做为随机种子。每个种子对应一组根据算法预先生成的随机数，所以，在相同的平台环境下，不同时间产生的随机数会是不同的，相应的，若将srand（unsigned）time(NULL)改为srand(TP)（TP为任一常量），则无论何时运行、运行多少次得到的“随机数”都会是一组固定的序列，因此srand生成的随机数是伪随机数。库函数中系统提供了两个函数用于产生随机数：srand()和rand()。 原型为：函数一：int rand(void)；从srand (seed)中指定的seed开始，返回一个[0, RAND_MAX（0x7fff）]间的随机整数。函数二：void srand(unsigned seed)；参数seed是rand()的种子，用来初始化rand()的起始值。但是，要注意的是所谓的“伪随机数”指的并不是假的随机数。其实绝对的随机数只是一种理想状态的随机数，计算机只能生成相对的随机数即伪随机数。计算机生 成的伪随机数既是随机的又是有规律的 —— 一部份遵守一定的规律，一部份则不遵守任何规律。比如“世上没有两片形状完全相同的树叶”，这正点到了事物的特性 —— 差异性；但是每种树的叶子都有近似的形状，这正是事物的共性 —— 规律性。从这个角度讲，我们就可以接受这样的事实了：计算机只能产生伪随机数而不是绝对的随机数。系统在调用rand（）之前都会自动调用srand()，如果用户在rand()之前曾调用过srand()给参数seed指定了一个值，那么 rand()就会将seed的值作为产生伪随机数的初始值；而如果用户在rand()前没有调用过srand()，那么系统默认将1作为伪随机数的初始 值。如果给了一个定值，那么每次rand()产生的随机数序列都是一样的~~所以为了避免上述情况的发生我们通常用srand((unsigned)time(0))或者srand((unsigned)time(NULL))来 产生种子。如果仍然觉得时间间隔太小，可以在(unsigned)time(0)或者(unsigned)time(NULL)后面乘上某个合适的整数。 例如,srand((unsigned)time(NULL)*10)另外，关于time_t time(0)：time_t被定义为长整型，它返回从日零时零分零秒到目前为止所经过的时间，单位为秒。生成随机数函数rand用法，如代码所示: 代码如下:#include "stdafx.h"#include &time.h&#include &stdlib.h&int _tmain(int argc, _TCHAR* argv[]){&// 初始化随机数种子&// time函数返回从日零时零分零秒到目前为止所经过的时间，单位为秒&srand((int)time(NULL));&&for (int i = 0; i & 10; i++) {&&j = (rand() * 10) / RAND_MAX + 1; // 生成1~10之间的随机数&&printf("j = %d \n", j);&}&unsigned start = (rand() * 1000)/ RAND_MAX + 15550; // 生成之间的随机数&printf("start = %d \n", start);&&& start &= ~1; // 把start变为偶数，如果是奇数，则start变为start - 1的偶数&printf("start = %d \n", start);&getchar();&return 0;}运行结果如下所示：j = 9j = 6j = 7j = 8j = 1j = 5j = 3j = 1j = 10j = 9start = 16185start = 16184
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具几乎所有编程语言中都提供了"生成一个随机数"的方法，也就是调用这个方法会生成一个数，我们事先也不知道它生成什么数。比如在.Net中编写下面的代码：
Random rand = newRandom();
Console.WriteLine(rand.Next());
运行后结果如下：
&&&&Next()方法用来返回一个随机数。同样的代码你执行和我的结果很可能不一样，而且我多次运行的结果也很可能不一样，这就是随机数。
&&&&看似很简单的东西，使用的时候有陷阱。我编写下面的代码想生成100个随机数：
for(int i=0;i&100;i++)
Random rand = new Random();
Console.WriteLine(rand.Next());
&&&&太奇怪了，竟然生成的"随机数"有好多连续一样的，这算什么"随机数"呀。有人指点"把new Random()"放到for循环外面就可以了：
Random rand = newRandom();
for(int i=0;i&100;i++)
Console.WriteLine(rand.Next());
&&&&&运行结果：
&&&&确实可以了！&
二、这是为什么呢？
&&&&这要从计算机中"随机数"产生的原理说起了。我们知道，计算机是很严格的，在确定的输入条件下，产生的结果是唯一确定的，不会每次执行的结果不一样。那么怎么样用软件实现产生看似不确定的随机数呢？
&&&&生成随机数的算法有很多种，最简单也是最常用的就是&"线性同余法"： &第n+1个数=(第n个数*29+37) % 1000，其中%是"求余数"运算符。很多像我一样的人见了公式都头疼，我用代码解释一下吧，MyRand是一个自定义的生成随机数的类：
class MyRand
public MyRand(int seed)
this.seed =
public int Next()
int next = (seed * 29 + 37) % 1000;
&如下调用：
MyRand rand = newMyRand(51);
for (int i = 0; i & 10; i++)
Console.WriteLine(rand.Next());
执行结果如下：
生成的数据是不是看起来"随机"了。简单解释一下这个代码：我们创建MyRand的一个对象，然后构造函数传递一个数51，这个数被赋值给seed，每次调用Next方法的时候根据(seed * 29 + 37) % 1000计算得到一个随机数，把这个随机数赋值给seed，然后把生成的随机数返回。这样下次再调用Next()的时候seed就不再是51，而是上次生成的随机数了，这样就看起来好像每一次生成的内容都很"随机"了。注意"%1000"取余预算的目的是保证生成的随机数不超过1000。&
当然无论是你运行还是我每次运行，输出结果都是一样的随机数，因为根据给定的初始数据51，我们就可以依次推断下来下面生成的所有"随机数"是什么都可以算出来了。这个初始的数据51就被称为"随机数种子"，这一系列的516、1、66、951、616&&数字被称为"随机数序列"。我们把51改成52，就会有这样的结果：
三、楼主好人，跪求种子
&&&&那么怎么可以使得每次运行程序的时候都生成不同的"随机数序列"呢？因为我们每次执行程序时候的时间很可能不一样，因此我们可以用当前时间做"随机数种子"
MyRand rand = newMyRand(Environment.TickCount);
for (int i = 0; i & 10; i++)
Console.WriteLine(rand.Next());
&&&&&Environment.TickCount为"系统启动后经过的微秒数"。这样每次程序运行的时候Environment.TickCount都不大可能一样（靠手动谁能一微秒内启动两次程序呢），所以每次生成的随机数就不一样了。
&&&&当然如果我们把new MyRand(Environment.TickCount)放到for循环中：&
for (int i = 0; i & 100; i++)
MyRand rand = newMyRand(Environment.TickCount);
Console.WriteLine(rand.Next());
&&&&运行结果又变成"很多是连续"的了，原理很简单：由于for循环体执行很快，所以每次循环的时候Environment.TickCount很可能还和上次一样（两行简单的代码运行用不了一毫秒那么长事件），由于这次的"随机数种子"和上次的"随机数种子"一样，这样Next()生成的第一个"随机数"就一样了。从"-320"变成"-856"是因为运行到"-856"的时候时间过了一毫秒。&
四、各语言的实现
&&&&我们看到.Net的Random类有一个int类型参数的构造函数：
public&Random(int&Seed)
就是和我们写的MyRand一样接受一个"随机数种子"。而我们之前调用的无参构造函数就是给Random(int&Seed)传递Environment.TickCount类进行构造的，代码如下：
&&&&&&&&public&Random()&:&this(Environment.TickCount)&&&&&&&&{&&&&&&&&}
&&&&这下我们终于明白最开始的疑惑了。
同样道理，在C/C++中生成10个随机数不应该如下调用：
for(i=0;i&10;i++)
srand( (unsigned)time( NULL ) );
printf("%d\n",rand());
srand( (unsigned)time( NULL ) ); //把当前时间设置为"随机数种子"
for(i=0;i&10;i++)
printf("%d\n",rand());
&五、"奇葩"的Java
Java学习者可能会提出问题了，在Java低版本中，如下使用会像.Net、C/C++中一样产生相同的随机数：&
for(int i=0;i&100;i++)
Random rand = new Random();
System.out.println(rand.nextInt());
&因为低版本Java中Rand类的无参构造函数的实现同样是用当前时间做种子：
public&Random()&{&this(System.currentTimeMillis());&}&
但是在高版本的Java中，比如Java1.8中，上面的"错误"代码执行却是没问题的：
&&&&为什么呢？我们来看一下这个Random无参构造函数的实现代码：
public Random()
this(seedUniquifier() ^ System.nanoTime());
private static long seedUniquifier() {
for (;;) {
long current = seedUniquifier.get();
long next = current * 652981L;
if (pareAndSet(current, next))
privatestaticfinal AtomicLong seedUniquifier
= new AtomicLong(8012L);
&&&&&这里不再是使用当前时间来做"随机数种子"，而是使用System.nanoTime()这个纳秒级的时间量并且和采用原子量AtomicLong根据上次调用构造函数算出来的一个数做异或运算。关于这段代码的解释详细参考这篇文章《》
最核心的地方就在于使用static变量AtomicLong来记录每次调用Random构造函数时使用的种子，下次再调用Random构造函数的时候避免和上次一样。
六、高并发系统中的问题
&&&&前面我们分析了，对于使用系统时间做"随机数种子"的随机数生成器，如果要产生多个随机数，那么一定要共享一个"随机数种子"才会避免生成的随机数短时间之内生成重复的随机数。但是在一些高并发的系统中一个不注意还会产生问题，比如一个网站在服务器端通过下面的方法生成验证码：
Random rand = new Random();
Int code = rand.Next();
&&&&当网站并发量很大的时候，可能一个毫秒内会有很多个人请求验证码，这就会造成这几个人请求到的验证码是重复的，会给系统带来潜在的漏洞。
&&&&&再比如我今天看到的一篇文章《当随机不够随机：一个在线扑克游戏的教训》里面就提到了"由于随机数产生器的种子是基于服务器时钟的，黑客们只要将他们的程序与服务器时钟同步就能够将可能出现的乱序减少到只有 200,000 种。到那个时候一旦黑客知道 5 张牌，他就可以实时的对 200,000 种可能的乱序进行快速搜索，找到游戏中的那种。所以一旦黑客知道手中的两张牌和 3 张公用牌，就可以猜出转牌和河牌时会来什么牌，以及其他玩家的牌。" &
&&&&这种情况有如下几种解决方法：
把Random对象作为一个全局实例（static）来使用。Java中Random是线程安全的（内部进行了加锁处理）；.Net中Random不是线程安全的，需要加锁处理。不过加锁会存在会造成处理速度慢的问题。而且由于初始的种子是确定的，所以攻击者存在着根据得到的若干随机数序列推测出"随机数种子"的可能性。
因为每次生成Guid的值都不样，网上有的文章说可以创建一个Guid计算它的HashCode或者MD5值的方式来做种子：&new Random(Guid.NewGuid().GetHashCode())&。但是我认为Guid的生成算法是确定的，在条件充足的情况下也是可以预测的，这样生成的随机数也有可预测的可能性。当然只是我的猜测，没经过理论的证明。
采用"真随机数发生器"，快看下一节分解！
&七、真随机数发生器
&&&&根据我们之前的分析，我们知道这些所谓的随机数不是真的"随机"，只是看起来随机，因此被称为"伪随机算法"。在一些对随机要求高的场合会使用一些物理硬件采集物理噪声、宇宙射线、量子衰变等现实生活中的真正随机的物理参数来产生真正的随机数。
当然也有聪明的人想到了不借助增加"随机数发生器"硬件的方法生成随机数。我们操作计算机时候鼠标的移动、敲击键盘的行为都是不可预测的，外界命令计算机什么时候要执行什么进程、处理什么文件、加载什么数据等也是不可预测的，因此导致的CPU运算速度、硬盘读写行为、内存占用情况的变化也是不可预测的。因此如果采集这些信息来作为随机数种子，那么生成的随机数就是不可预测的了。
在Linux/Unix下可以使用"/dev/random"这个真随机数发生器，它的数据主来来自于硬件中断信息，不过产生随机数的速度比较慢。
Windows下可以调用系统的CryptGenRandom()函数，它主要依据当前进程Id、当前线程Id、系统启动后的TickCount、当前时间、QueryPerformanceCounter返回的高性能计数器值、用户名、计算机名、CPU计数器的值等等来计算。和"/dev/random"一样CryptGenRandom()的生成速度也比较慢，而且消耗比较大的系统资源。
当然.Net下也可以使用RNGCryptoServiceProvider&类（System.Security.Cryptography命名空间下）来生成真随机数，根据StackOverflow上一篇帖子介绍RNGCryptoServiceProvider&并不是对CryptGenRandom()函数的封装，但是和CryptGenRandom()原理类似。 &
有人可能会问：既然有"/dev/random" 、CryptGenRandom()这样的"真随机数发生器"，为什么还要提供、使用伪随机数这样的"假货"？因为前面提到了"/dev/random" 、CryptGenRandom()生成速度慢而且比较消耗性能。在对随机数的不可预测性要求低的场合，使用伪随机数算法即可，因为性能比较高。对于随机数的不可预测性要求高的场合就要使用真随机数发生器，真随机数发生器硬件设备需要考虑成本问题，而"/dev/random"、CryptGenRandom()则性能较差。
万事万物都没有完美的，没有绝对的好，也没有绝对的坏，这才是多元世界美好的地方。
阅读(...) 评论()