随机数

计算机的随机数都是由伪随机数，即是由小M多项式序列生成的，其中产生每个小序列都有一个初始值，即随机种子。（注意： 小M多项式序列的周期是65535，即每次利用一个随机种子生成的随机数的周期是65535，当你取得65535个随机数后它们又重复出现了。）

我们知道rand()函数可以用来产生随机数，但是这不是真正意义上的随机数，是一个伪随机数，是根据一个数（我们可以称它为种子）为基准以某个递推公式推算出来的一系列数，当这系列数很大的时候，就符合正态公布，从而相当于产生了随机数，但这不是真正的随机数，当计算机正常开机后，这个种子的值是定了的，除非你破坏了系统。

1.rand()

功能:随机数发生器

用法:int rand(void)

所在头文件: stdlib.h

rand()的内部实现是用线性同余法做的，它不是真的随机数，因其周期特别长，故在一定的范围里可看成是随机的。

rand()返回一随机数值的范围在0至RAND_MAX 间。RAND_MAX的范围最少是在32767之间(int)。用unsigned int 双字节是65535，四字节是4294967295的整数范围。0~RAND_MAX每个数字被选中的机率是相同的。

用户未设定随机数种子时，系统默认的随机数种子为1。

rand()产生的是伪随机数字，每次执行时是相同的;若要不同,用函数srand()初始化它。

2.srand()

功能:初始化随机数发生器

用法: void srand(unsigned int seed)

所在头文件: stdlib.h

srand()用来设置rand()产生随机数时的随机数种子。参数seed必须是个整数，如果每次seed都设相同值，rand()所产生的随机数值每次就会一样。

3.使用当前时钟作为随机数种子

rand()产生的随机数在每次运行的时候都是与上一次相同的。若要不同,用函数srand()初始化它。可以利用srand((unsigned int)(time(NULL))的方法，产生不同的随机数种子，因为每一次运行程序的时间是不同的。

4.产生随机数的用法

1) 给srand()提供一个种子，它是一个unsigned int类型； 
2) 调用rand()，它会根据提供给srand()的种子值返回一个随机数(在0到RAND_MAX之间)； 
3) 根据需要多次调用rand()，从而不间断地得到新的随机数； 
4) 无论什么时候，都可以给srand()提供一个新的种子，从而进一步“随机化”rand()的输出结果。

0~RAND_MAX之间的随机数程序

#include <iostream>
#include <stdlib.h>
#include <time.h> 
using namespace std; 
int main()
{ 
srand((unsigned)time(NULL)); 
for(int i = 0; i < 10;i++ ) 
        cout << rand() << '\t'; 
cout << endl; 
return 0;
}

5.产生一定范围随机数的通用表示公式

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。 
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

不重复随机数

1. 方法一

最初的思想是每生成一个随机数，便于前面的所有随机数进行比较，如果有重复，则舍去不要，重新选取。但该方法十分费时，并且在数据量巨大的并且有一定限制的时候，会引发巨大问题。例如要生成10000个随机数，范围是0-9999，且不能重复，那么最后几个随机数有可能需要相当长的时间才能筛选出来。

下面我们从另外一个角度来思考，假设我们已经由一个数组长度为10000的数组，里面分别存储了数据0-9999，我现在的做法是想办法让10000个数进行随机排列，便得到了这样一个随机数列，如果我只要其中的100个数，那么从前面取出100个就好。这里利用algorithm.h里面的一个函数，来进行简单处理。

template<class RandomAccessIterator>  
    void random_shuffle(
      RandomAccessIterator _First, 
      RandomAccessIterator _Last
);

这个函数操作的对象是容器的迭代器，即我们需要将存储数据从数组变为容器就好了，下面代码实现一下：

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

void randperm(int Num)
{
    vector<int> temp;
    for (int i = 0; i < Num; ++i)
    {
        temp.push_back(i + 1);
    }

    random_shuffle(temp.begin(), temp.end());

    for (int i = 0; i < temp.size(); i++)
    {
        cout << temp[i] << " ";
    }
}

cout << endl;

2. 方法二

按顺序产生这些数，但随机产生它们的位置。例如下面产生100个100以内不重复随机数的代码：

int a[100];
for(i=0; i<=99; ++i) a[i]=i;
for(i=99; i>=1; --i) swap(a[i], a[rand()%i]);

上面这段代码只需要遍历一次就可以产生这100个不重复的随机数，它是如何做到的呢？首先第二行按顺序用0到99填满整个数组；第三行，是随机产生从0到m-2个数组下标，把这个下标的元素值跟m-1下标的元

素值交换，一直进行到下标为1的元素。因此它只需要遍历一次就能产生全部的随机数。

再看下面的代码，原理跟上面例子相似，但效率比上面的差点，但仍不失为一个好方法：

int a[100]={0};
int i, m;
for(i=1; i<=99; ++i)
{
        while(a[m=rand()%100]);
        a[m] = i;
}

这段代码也是随机产生位置，但它预先把整个数组初始化为0，然后随机产生其中一个位置，如果该元素值为0，表示这个位置还没有被使用过，就把i赋予它；否则，就重新随机产生另一个位置，直到整个数组

被填满。这个方法，越到后面，遇到已使用过的元素的可能性越高，重复次数就越多，这是不及第一个方法的地方，但总的来说，效率还是不错的。

References：

[1]. 如何高效产生m个n范围内的不重复随机数

[2]. C/C++中产生随机数(rand,srand用法)

[3]. C++中随机数和不重复的随机数

C语言中有可以产生随机数的函数，需要添加 stdlib.h 头文件和 time.h 头文件。

	srand((unsigned) time(NULL));	//初始化随机种子 
	for(int i = 0; i < 10; i++)
		printf("%d ", rand());

其中，rand()函数只能产生[0, RAND_MAX]范围内的整数(RAND_MAX是stdlib.h中的一个常数)。

如果想要产生给定范围[a,b]内的随机数，需要使用 rand()%(b-a+1)+a。其中rand()%(b-a+1)的范围是[0,b-a]，再加上a之后就是[a,b]。

若要生成大于RAND_MAX的随机数，则可使用下一种方法：

1.先用rand()生成一个[0,RAND_MAX]范围内的随机数

2.然后用这个随机数除以RAND_MAX，这样就能得到一个[0,1]范围内的浮点数

3.最后用这个浮点数乘以范围长度b-a+1，再加上a即可

(int)(round(1.0 * rand() / RAND_MAX * (right - left) + left))

即如上代码所示，可产生[left,right]范围内的随机数。

C++产生随机数函数rand()

C++11之前没有random,生成随机数用rand()，可以配合srand()来使用。rand()不是真正的生成随机数，而是线性取余，有可能也会生成相同的数出来。生成的随机数最大值为RAND_MAX，宏定义在<stdlib.h>中，为0x7FFF，也就是4294967295。
rand()规则：
生成0到最大值之间的随机数：rand()
生成(a,b)之间的随机数：(rand()%(b-a)) + (a+1)
生成[a,b)之间的随机数：(rand()%(b-a)) + a
生成(a,b]之间的随机数：((rand()%(b-a)) +a )+ 1
生成[a,b]之间的随机数：(rand()%(b-a+1)) + a
例如产生一个10~20之间的随机数

(rand()%10) + 10

srand()用来设置rand()产生随机数时的随机数种子。 参数seed必须是个整数，通常可以利用time(0)的返回值或NULL来当做seed。如果每次seed都设相同值，rand()所产生的随机数值每次就会一样。

#include <iostream>
#include <stdlib.h>
#include <random>
#include <ctime>
using namespace std;

void f1()
{
	srand((int)time(0));
	cout << "f1 rand:" << endl;
	for (int i = 0; i < 10; ++i)
	{
		cout << rand() << ' ';
	}
	cout << endl;
}

void f2()
{
	cout << "f2 rand:" << endl;
	for (int i = 0; i < 10; ++i)
	{
		srand((int)time(0));
		cout << rand() << ' ';
	}
	cout << endl;
}

int main()
{
	f1();
	f2();
	system("pause");
	return 0;
}

输出：

f1 rand:
28071 30499 28792 20690 25000 5286 6554 1446 4794 29189
f2 rand:
28071 28071 28071 28071 28071 28071 28071 28071 28071 28071

产生相同随机数的原因：
计算机的随机数都是由伪随机数，即是由小M多项式序列生成的，其中产生每个小序列都有一个初始值，即随机种子。（注意： 小M多项式序列的周期是65535，即每次利用一个随机种子生成的随机数的周期是65535，当你取得65535个随机数后它们又重复出现了。