一站式学习 C 编程

主题

3. 数组应用实例：直方图 ​

继续上面的例子。我们统计一列 0~9 的随机数，打印每个数字出现的次数，像这样的统计结果称为直方图（Histogram）。有时候我们并不只是想打印，更想把统计结果保存下来以便做后续处理。我们可以把程序改成这样：

c
int main(void) {
    int howmanyones = howmany(1);
    int howmanytwos = howmany(2);
    ...
}

这显然太繁琐了。要是这样的随机数有 100 个呢？显然这里用数组最合适不过了：

c
int main(void) {
    int i, histogram[10];

    gen_random(10);
    for (i = 0; i < 10; i++)
        histogram[i] = howmany(i);
    ...
}

有意思的是，这里的循环变量 i 有两个作用，一是作为参数传给 howmany 函数，统计数字 i 出现的次数，二是做 histogram 的下标，也就是“把数字 i 出现的次数保存在数组 histogram 的第 i 个位置”。

尽管上面的方法可以准确地得到统计结果，但是效率很低，这 100000 个随机数需要从头到尾检查十遍，每一遍检查只统计一种数字的出现次数。其实可以把 histogram 中的元素当作累加器来用，这些随机数只需要从头到尾检查一遍（Single Pass）就可以得出结果：

c
int main(void) {
    int i, histogram[10] = {0};

    gen_random(10);
    for (i = 0; i < N; i++)
        histogram[a[i]]++;
    ...
}

首先把 histogram 的所有元素初始化为 0，注意使用局部变量的值之前一定要初始化，否则值是不确定的。接下来的代码很有意思，在每次循环中， a[i] 就是出现的随机数，而这个随机数同时也是 histogram 的下标，这个随机数每出现一次就把 histogram 中相应的元素加 1。

把上面的程序运行几遍，你就会发现每次产生的随机数都是一样的，不仅如此，在别的计算机上运行该程序产生的随机数很可能也是这样的。这正说明了这些数是伪随机数，是用一套确定的公式基于某个初值算出来的，只要初值相同，随后的整个数列就都相同。实际应用中不可能使用每次都一样的随机数，例如开发一个麻将游戏，每次运行这个游戏摸到的牌不应该是一样的。因此，C 标准库允许我们自己指定一个初值，然后在此基础上生成伪随机数，这个初值称为 Seed，可以用 srand 函数指定 Seed。通常我们通过别的途径得到一个不确定的数作为 Seed，例如调用 time 函数得到当前系统时间距 1970 年 1 月 1 日 00:00:00 [1]的秒数，然后传给 srand ：

c
srand(time(NULL));

然后再调用 rand ，得到的随机数就和刚才完全不同了。调用 time 函数需要包含头文件 time.h ，这里的 NULL 表示空指针，到 第 1 节“指针的基本概念” 再详细解释。

习题 ​

  1. 补完本节直方图程序的 main 函数，以可视化的形式打印直方图。例如上一节统计 20 个随机数的结果是：

    plaintext
    0  1  2  3  4  5  6  7  8  9

*  *  *  *     *  *  *     *
*     *  *     *  *  *     *
      *  *        *
                  *
                  *

  2. 定义一个数组，编程打印它的全排列。比如定义：

    c
    #define N 3
int a[N] = { 1, 2, 3 };

    则运行结果是：

    bash
    $ ./a.out
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
1 2 3

    程序的主要思路是：

    1. 把第 1 个数换到最前面来（本来就在最前面），准备打印 1xx，再对后两个数 2 和 3 做全排列。
    2. 把第 2 个数换到最前面来，准备打印 2xx，再对后两个数 1 和 3 做全排列。
    3. 把第 3 个数换到最前面来，准备打印 3xx，再对后两个数 1 和 2 做全排列。

    可见这是一个递归的过程，把对整个序列做全排列的问题归结为对它的子序列做全排列的问题，注意我没有描述 Base Case 怎么处理，你需要自己想。你的程序要具有通用性，如果改变了 N 和数组 a 的定义（比如改成 4 个数的数组），其它代码不需要修改就可以做 4 个数的全排列（共 24 种排列）。

    完成了上述要求之后再考虑第二个问题：如果再定义一个常量 M 表示从 N 个数中取几个数做排列（ N == M 时表示全排列），原来的程序应该怎么改？

    最后再考虑第三个问题：如果要求从 N 个数中取 M 个数做组合而不是做排列，就不能用原来的递归过程了，想想组合的递归过程应该怎么描述，编程实现它。

  1. 各种派生自 UNIX 的系统都把这个时刻称为 Epoch，因为 UNIX 系统最早发明于 1969 年。 ↩︎