C++11 随机数

C++11 随机数

• • C++11之前的随机数生成方法
  • • rand() 随机数函数
    • srand() 初始化随机种子
  • C++11 random库
  • • 随机数引擎
    • • default_random_engine 类
      • mt19937 随机数引擎
    • 真随机数 random_device（）
    • 随机数分布引擎
    • • uniform_real或int_distribution 均匀分布随机数
      • 其他概率分布类型
  • 随机数例题
  • 补充：shuffle()函数 打乱顺序

相对于C++ 11之前,只需srand、rand这两函数即可获取随机数，这也是C语言常用的随机数生成方法。
而对于C++ 11，则提供了更多随机数生成器。比较常用的是default_random_engine和 mt 19937_64类。

C++11之前的随机数生成方法 rand() 随机数函数

头文件#include

1）rand()不需要参数，它会返回一个从0到最大随机数RAND_MAX之间的均匀分布的伪随机数整数。RAND_MAX必须至少为32767。
rand()的内部实现是用线性同余法实现的， 随机数生成器总是以相同的种子开始，默认以1为种子（即起始值），所以形成的伪随机数列也相同，失去了随机意义。（但这样便于程序调试） ，由于周期较长，因此在一定范围内可以看成是随机的。

2）如果你要产生0~99这100个整数中的一个随机整数，可以表达为：int num = rand() % 100;
如果要产生1~100，则是这样：int num = rand() % 100 + 1;

总结来说，可以表示为：int num = rand() % n +a;
其中的a是起始值，n-1+a是终止值，n是整数的范围。

3）一般性：rand() % (b-a+1)+ a ; 就表示 a~b 之间的一个随机整数。

4）若要产生0~1之间的小数，则可以先取得0-10的整数，然后均除以10即可得到“随机到十分位”的10个随机小数。
若要得到“随机到百分位”的随机小数，则需要先得到0~100的10个整数，然后均除以100，其它情况依 此类推。

5）在调用rand()函数之前，可以使用srand()函数设置随机数种子，如果没有设置随机数种子，rand()函数在调用时，自动设计随机数种子为1。随机种子相同，每次产生的随机数也会相同。

srand() 初始化随机种子

是随机数发生器的初始化函数。原型:void srand(unsigned seed);
用法:它初始化随机种子，会提供一个种子，这个种子会对应一个随机数，如果使用相同的种子后面的rand()函数会出现一样的随机数，如: srand(1); 直接使用1来初始化种子。也就是说当srand()的参数值固定的时候，rand()获得的数也是固定的。
不过为了防止随机数每次重复，常常使用time函数获取系统时间来初始化，同时程序中包含一个新的头文件 #include让，随机种子来自系统时钟。
如果想在一个程序中生成随机数序列，需要至多在生成随机数之前设置一次随机种子。 即：只需在主程序开始处调用srand((unsigned)time(NULL)); 后面直接用rand就可以了。
例如：

#include 
#include  // Header file needed to use srand and rand
#include  // Header file needed to use time
using namespace std;
void test_rand(void)
     {
           unsigned long n;
          srand((unsigned)time(NULL));
          for(int i = 0; i < 100; i++)
          {
                n = rand();
                printf("d\n", n);
           }
}
或者调用time函数时必须给它传递一个参数 0：
int main()
{
    unsigned seed;  // Random generator seed
    // Use the time function to get a "seed” value for srand
    seed = time(0);
    srand(seed);
    // Now generate and print three random numbers
    cout << rand() << " " ;
    cout << rand() << " " ;
    cout << rand() << endl;
    return 0;
}

C++11 random库

C库函数rand（）生成的是均匀分布的伪随机数，每个随机数的范围在0和一个系统相关的最大值（至少为32767）之间。
rand函数的问题是：很多程序需要不同范围的随机数，一些应用需要随机浮点数，以及非均匀分布的随机数。为了解决这些问题，通常会转换rand生成的随机树的范围、类型或者是分布，转换的 *** 作常常会引入非随机性。

C++11中，随机数都是定义在#include 头文件中的。
random库的组件主要有随机数引擎和随机数分布引擎。
1.随机数引擎类是可以独⽴运⾏的随机数发⽣器，它以均匀的概率⽣成某⼀类型的随机数，但⽆法指定随机数的范围、概率等信息。因此，它也被称为“原始随机数发⽣器”，由于不能指定⽣成随机数的范围，它通常不会被单独使⽤。
2.随机数分布类是⼀个需要于随机数引擎类的⽀持才能运⾏的类，但是它能根据⽤户的需求利⽤随机数引擎⽣成符合条件的随机数，例如某⼀区间、某⼀分布概率的随机数。

也就是说，一个引擎类可以生成unsigned随机数列，一个分布使用一个引擎类生成指定类型的，在给定范围内的，服从指定概率分布的随机数。

随机数类常⽤的主要有以下四个：
1）default_random_engine：随机⾮负数（不建议单独使⽤）；
default_random_engine 是⼀个随机数引擎类。它定义的调⽤运算符返回⼀个随机的 unsigned 类型的值。

2）uniform_int_distribution：指定范围的随机⾮负数；
uniform_int_distribution是⼀个随机数分布类，也是个模板类，模板参数为⽣成随机数的类型（不过只能是 int、unsigned、short、unsigned short、long、unsigned long、long long、unsigned long long 中的⼀种）。它的构造函数接受两个值，表⽰随机数的分布范围（闭区间）。

3）uniform_real_distribution：指定范围的随机实数；
uniform_real_distribution 是⼀个随机数分布类，它也是模板类，参数表⽰随机数类型（可选类型为 float、double、long double）。构造函数也需要最⼤值和最⼩值作为参数。（左闭右开区间）

4）bernoulli_distribution：指定概率的随机布尔值。
bernoulli_distribution 是⼀个分布类，但它不是模板类。它的构造函数只有⼀个参数，表⽰该类返回 true 的概率，该参数默认为 0.5 ，即 返回 true 和 false 的概率相等。

下面这个样例可以学会：

	//随机数生成引擎
	//利用了真随机数 random_device（）
	default_random_engine e{random_device{}()};
    mt19937_64 eng{random_device{}()};
    //随机数分布引擎
    uniform_real_distribution<double> dis1(0, 20);
    uniform_int_distribution<int> dis2(20, 40);
    bernoulli_distribution u;
    
    for(int i = 0;i < 4; ++i){
        cout<<e()<<" ";
    }
    cout<<endl;  //370521601 1801455354 1835679272 1511451702
    
    for(int i = 0;i < 4; ++i){
        cout<<dis1(eng)<<" ";
    }
    cout<<endl; //6.65994 0.0263284 0.0570728 17.9504
    
    for(int i = 0;i < 4; ++i){
        cout<<dis2(e)<<" ";
    }
    cout<<endl; //23 36 25 30
    
    for(int i = 0;i < 4; ++i){
        cout<<u(e)<<" ";
    }
    cout<<endl;  //0 0 1 0

随机数引擎

C++11提供了下面三种随机数生成算法可供选择：

linear_congruential_engine线性同余法
mersenne_twister_engine梅森旋转法
substract_with_carry_engine滞后Fibonacci

这三种算法，在C++11里面都是用模板的方式实现的。C++11标准预定义了一些随机数类，这些随机数类都是用比较好的参数实例化上面那三个模板类得到的。
注意：在C++11里面，把这些随机数生成器叫做引擎(engines)。

下图列出了一些实例化的随机数类：

当然具体用了哪些参数，我们是不用管的，直接用就行了。

default_random_engine 类

上图左上角的default_random_engine的类，也是一个实例化的类。之所以不归入那三种算法，是因为它的实现是由编译器厂家决定的，有的可能用linear_congruential_engine实现，有的可能用mersenne_twister_engine实现。不过，对于其他的类，C++11是有明确规定用哪种算法和参数实现的。

default_random_engine 是⼀个随机数引擎类。它定义的调⽤运算符返回⼀个随机的 unsigned 类型的值。

#include
#include

int main(){
    default_random_engine e; 
    //也可为随机数引擎加随机数发生器的参数：
    //default_random_engine random(time(NULL)); 
    //default_random_engine random{random_device{}()};
    for(int i = 0; i < 20; ++i)
        cout<<e()<<' ';
    cout<<endl; 
    return 0;
}
//gcc编译器需要加上 –std=c++11 选项。

mt19937 随机数引擎

mt19937又叫梅森旋转算法，用于生成随机数的，他也不是梅森发明的，是俩日本人发明的。它的循环节是 2 19937 − 1 2^{19937}-1 219937−1，这是一个梅森素数，所以叫mt19937，也就是说：
mt是指maxint（整型int最大值的缩写）
19937是指 2 19937 − 1 2^{19937}-1 219937−1

常用下面的语句生成一个随机数引擎，例如：478. 在圆内随机生成点

mt19937 gen{random_device {}()};

mt19937是c++11新特性，它是一种随机数算法，用法与rand()函数类似，但是与其它已使用的伪随机数发生器相比，mt19937具有速度快，周期长的特点，周期可达到 2 19937 − 1 2^{19937}-1 219937−1。
rand()在windows下生成的数据范围为0-32726
mt19937所生成的数据范围大概为(-maxint,+maxint)（maxint整型int最大值的缩写）

真随机数 random_device（）

random_device（）函数目的就是产生生成真随机数。它并不是由某一个数学算法得到的随机序列，而是通过读取文件，读什么文件看具体的实现(Linux可以通过读取/dev/random文件来获取)。文件的内容是随机的，因为文件内容是计算机系统的熵（熵指的是一个系统的混乱程度）。也是当前系统的环境噪声，系统噪音可以通过很多参数来评估，如内存的使用，文件的使用量，不同类型的进程数量等等。Linux的熵来自键盘计时、鼠标移动等。
然而randm_device()只在Linux下有效，在Windows下无效。

	#include //随机数
	random_device rd;//随机数发生器
	mt19937 g(rd());//随机数引擎
	或者写为下面一句：
	mt19937 g{random_device{}()};
	//类似于srand()和rand()的效果
	srand(time(NULL)); //初始化随机数种子

随机数分布引擎 uniform_real或int_distribution 均匀分布随机数

uniform_int_distribution是⼀个随机数分布类，也是个模板类，模板参数为⽣成随机数的类型（不过只能是 int、unsigned、short、unsigned short、long、unsigned long、long long、unsigned long long 中的⼀种）。它的构造函数接受两个值，表⽰随机数的分布范围（闭区间）。

uniform_real_distribution 是⼀个随机数分布类，它也是模板类，参数表⽰随机数类型（可选类型为 float、double、long double）。构造函数也需要最⼤值和最⼩值作为参数。

通常用uniform_real_distribution来产生均匀分布的随机数。此外还常用正态分布的normal_distribution。
如果我们只想产生0到100的随机数。按照我们之前的做法是直接random()%100。这种做法是不好的。原因可以参见《Accelerated C++》的7.4.4节。我们平常说产生随机数，隐含是意思是产生均匀分布的随机数。
C++11提供的均匀分布模板类为：uniform_int_distribution和uniform_real_distribution。
uniform_int_distribution 整数均匀分布：从均匀分布中生成随机的整数
uniform_real_distribution 浮点数均匀分布： 从均匀分布中生成随机的浮点数（double或float）。

前一个模板类名字中的int不是代表整型，而是表示整数。因为它是一个模板类，可以用int、long、short等整数类型来实例化。后一个表示浮点数模板类，可以用float和double来实例化。使用例子如下：

#include  
#include  
#include  
   
int main()  
{  
    default_random_engine random(time(NULL));  
    uniform_int_distribution<int> dis1(0, 100);  //能产生100
    uniform_real_distribution<double> dis2(0.0, 1.0);  //不能产生1.0
   
    for(int i = 0; i < 10; ++i)  
        cout<<dis1(random)<<' ';  
    cout<<endl;  
   
    for(int i = 0; i < 10; ++i)  
        cout<<dis2(random)<<' ';  
    cout<<endl;  
   
    return 0;  
}  

uniform_int_distribution的随机数的范围是[ ]，而uniform_real_distribution却是左闭右开范围[ )。
对于default_random_engine来说，其产生的随机数范围是在[min()， max()]之间，其中min()和max()为它的两个成员函数。同样，也是闭区间范围。
对于浮点数，如果真的是想产生[0.0, 1.0]范围的数，可以使用

#include  
#include  
uniform_real_distribution<double> dis2(0, std::nextafter(1,DBL_MAX));  

如果uniform_int_distribution使用了无参构造函数，那么其随机数的范围是[0,numberic_limits::max()]，也就是0到对应实例化类型能表示的最大值。对于uniform_real_distribution的无参构造函数，则是[0, 1)。

其他概率分布类型

C++11提供的概率分布类型有下面这些：
均匀分布：

   uniform_int_distribution          整数均匀分布
   
   uniform_real_distribution        浮点数均匀分布

伯努利类型分布：（仅有yes/no两种结果，概率一个p，一个1-p）：

   bernoulli_distribution    伯努利分布
   注：bernoulli_distribution 是⼀个分布类，但它不是模板类。
   它的构造函数只有⼀个参数，表⽰该类返回 true 的概率，
   该参数默认为 0.5 ，即 返回 true 和 false 的概率相等。

   binomial_distribution     二项分布

   geometry_distribution    几何分布

   negative_biomial_distribution  负二项分布

Rate-based distributions:

   poisson_distribution 泊松分布

   exponential_distribution指数分布

   gamma_distribution 伽马分布

    weibull_distribution 威布尔分布

   extreme_value_distribution 极值分布

正态分布相关：

   normal_distribution        正态分布

   chi_squared_distribution卡方分布

   cauchy_distribution       柯西分布

   fisher_f_distribution      费歇尔F分布

   student_t_distribution t分布

分段分布相关：

   discrete_distribution离散分布

   piecewise_constant_distribution分段常数分布

   piecewise_linear_distribution分段线性分布

这些概率分布函数都是有参数的，在类的构造函数中把参数传进去
下面是一个泊松分布的例子

#include
#include
#include
#include
 
int main()
{
  const int nrolls = 10000; // number ofexperiments
  const int nstars = 100;   // maximum number of stars to distribute
 
  int parameter = 4;
 
  minstd_rand engine(time(NULL));
  poisson_distribution<int>distribution(parameter);
 
  int p[20]={};
 
  for (int i=0; i<nrolls; ++i)
  {
    int number = distribution(engine);
    if (number < 20)
        ++p[number];
  }
 
  std::cout << "poisson_distribution"<<parameter<< std::endl;
  for (int i=0; i < 20; ++i)
    std::cout<<std::setw(2)<< i<< ": " << std::string(p[i]*nstars/nrolls, '*') <<std::endl;
 
  return 0;
}

随机数例题

例题：478. 在圆内随机生成点

【做法】在单位圆中随机生成一个点，它离圆心的距离小于等于 r 的概率为 F ( r ) = r 2 F( r )=r ^2 F(r)=r2 ，可以通过 [0,1) 的均匀分布生成随机变量 u，，即用 r = u r = \sqrt{u} r=u ​来生成随机变量 r。再通过类似的方法随机生成其与水平轴正方向的夹角 θ ∈ [ 0 , 2 π ) \theta \in [0, 2\pi) θ∈[0,2π)，最后坐标变换到当前圆中。

【细节注意】如果直接在 [0, 1) 范围内生成 r 以及 [ 0 , 2 π ) [0, 2\pi) [0,2π) 范围内生成 θ \theta θ，得到的随机点是不均匀的，原因：
假设先生成角度θ，它是一个 [ 0 , 2 π ) [0, 2\pi) [0,2π) 的uniform的一次采样，那么确定θ后，点离圆心距离r的分布不再是一个uniform，如果用uniform去生成r，更靠近圆心的点会得到更大的被选择概率，无法在圆中均匀地得到一点。

class Solution {
    mt19937 gen{random_device {}()};
    uniform_real_distribution<double> dis;
    double x, y, ra;

public:
    Solution(double radius, double x_center, double y_center):dis(0, 1), ra(radius), x(x_center), y(y_center){}
       
    vector<double> randPoint() {
        double u = dis(gen), theata = dis(gen) * 2 * acos(-1.0);
        double r = sqrt(u);
        return {x + r * cos(theata) * ra, y + r * sin(theata) * ra};
    }
};

补充：shuffle()函数 打乱顺序

重排序给定范围 [first, last) 中的元素，打乱顺序，使得这些元素的每个排列拥有相等的出现概率。

头文件：#include
函数原型：

template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
参数：
first, last - 要随机打乱的元素范围
g - 均匀随机位生成器 (UniformRandomBitGenerator)
RandomIt 必须满足值可交换 (ValueSwappable) 和 遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。

同样的，内置类型数组也支持这种用法，比如下面的int型数组与char型数组。

int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
char crr[] = "ABCDEFGH";

通常使用样例：
注意random_device{ }( ) 需要加头文件#include

shuffle(myvector.begin(), myvector.end(), mt19937(random_device{}()));

vector使用样例：

#include 
#include 
#include 
#include 

int main()
{
	std::vector<int> v = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	//两种写法：
	std::random_device rd;	//随机数发生器
	std::mt19937 g(rd());	// 随机数引擎:基于梅森缠绕器算法的随机数生成器
	std::shuffle(v.begin(), v.end(), g);	// 打乱顺序，重新排序（随机序列）
	//上面三句等价于下面一句
	std::shuffle(myvector.begin(), myvector.end(), std::mt19937(std::random_device{}()));
	
	for (int a : v) std::cout << a << " "; //输出：3 1 4 9 5 10 2 8 7 6
	std::cout << "\n";
}