生成随机数
----------

编写算法程序常常会需要自己生成一些测试数据。如果数据量小可以自己手动编一些，但是往往会需要大数据量的测试数据，这时候手动编数据就很困难了。我们需要用计算机来自动生成一批随机数，使用 ``cstdlib`` 库的 ``rand()`` 函数可以生成均匀分布的随机数。

.. code-block:: c++

    int rand();

调用这个函数不需要提供任何参数，每次调用返回一个从0到 ``int`` 类型最大值（一般是2\ :superscript:`31`-1=2,147,483,647）之间的随机数。将得到的随机数除以任一大于1的正整数 :math:`a` 取余数，余数的取值范围为 :math:`[0,a)`\ ，所以调用 ``rand() % a`` 即可得到在此范围内均匀分布的随机数。

更一般地，如果要生成 :math:`[a,b)` 区间内的随机数，可以通过调用 ``rand() % (b - a) + a`` 来实现。例如要生成从1到99之间均匀分布的随机数，那么就调用 ``rand() % 99 + 1``\ ，而不是 ``rand() % 100 + 1``\ ，后者生成的是从1到100的随机数；若要生成-100到100之间的随机数，则应调用 ``rand() % 201 - 100``\ 。这个规则可以简单记作“除长加头”。

.. attention::

   请注意在计算机软件的世界里，表示范围的惯例就是“含头不含尾”，用数学语言来说就是“左闭右开”区间，千万要牢记并熟悉这一惯例。


``rand()`` 函数生成的其实是\ :strong:`伪随机数`\ ，并不是真正的随机数。这些“随机”数实际上是用一套精巧但是确定的数学公式计算出来的，看上去随机，实际上有规律。程序每一次运行，第一次调用 ``rand()`` 时，会用一个正整数来启动随机数生成过程。这个正整数叫做伪随机数生成过程的\ :strong:`种子`\ 。用同一个种子启动伪随机过程，会生成完全相同的伪随机数序列。不巧的是，``rand()`` 函数每次都用整数1来作为启动的种子，从来不变，永远是1！我们可以多次运行下面这个小程序来观察这一现象。

.. literalinclude:: ../codes/120_random_nums.cpp
   :language: c++
   :lines: 1,3-6,8-12

我可以保证，不管运行多少次，你都会得到同样的一百个数，如果你也使用NOI Linux的g++ 4.8.4的话，十有八九是这样的：

.. code-block:: none

      1,  4,  6, 70, 87, 66, 57, 92, 60, 11, 81, 79, 85, 72, 50, 62, 43, 16, 36, 56
     13, 70, 25, 99, 17,  8, 91, 97,  8, 64, 50, 61, 20, 56, 84,  7, 74, 41, 51, 87
      4, 33, 66, 41, 57, 16,  3,  0, 84, 39,  9, 50, 61, 34,  1, 78, 94, 92, 28,  2
     56, 78, 16, 28, 35,  0, 88,  9, 41, 39, 96, 97, 24, 62, 38, 82, 30, 41, 34, 15
     32, 43, 17, 45, 29, 18, 23, 24, 10, 51, 78, 18, 30, 94, 46, 17, 94, 34, 26, 87


这可怎么办？这样不就没法生成真正可用的随机数了吗？当然不会。\ ``cstdlib`` 库提供了一个用来设置随机种子的函数 ``srand()``\ 。

.. code-block:: c++

    void srand(unsigned int seed);


这个函数没有返回值，调用它可以给伪随机过程人为设置一个启动种子。所以我们只要在程序开始时调用一下 ``srand()`` 函数，种下一颗“每次程序运行都不相同而且很难被复制”的种子，就可以用 ``rand()`` 来生成仿真程度相当好的随机数了。可是到哪里去找这样一个“每次程序运行都不相同而且很难被复制”的无符号整数呢？方法很多，最方便最常用的是使用 ``ctime`` 库提供的 ``time()`` 函数。调用 ``time(NULL)`` 可获取程序运行到当前语句时的实际时间，是从1970年1月1日凌晨0点0分0秒开始到当前为止的秒数，其返回类型 ``t_time`` 实际上就是 ``unsigned int``\ ，它恰好能满足“每次运行都不相同而且很难被复制”的要求。

现在我们来试着运行一下用 ``time()`` 函数优化过的这个小程序。

.. literalinclude:: ../codes/120_random_nums.cpp
   :language: c++
   :emphasize-lines: 2,7

多运行几次，你会发现现在每次都会得到100个完全看不出规律的不同的随机数。

.. hint::

   在每一个要用到随机数的程序的开头，运行一下 ``srand(time(NULL))``\ 。

.. admonition:: 思考

   如果要生成浮点数类型的随机数，或者比 ``int`` 更大的整型，比如 ``long long`` 类型的随机数时应该怎么办呢？这个问题请自行思考解决。

.. warning::

   无论看上去多么没有规律，\ ``rand()`` 函数使用的伪随机数生成算法都是不安全的，只能用于一般的随机数模拟，不能用于真正的加解密应用。如果今后你要编写实用的加密解密算法，绝对不能使用它来生成密钥！