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

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

  1. int main(void)
  2. {
  3.     int howmanyones = howmany(1);
  4.     int howmanytwos = howmany(2);
  5.     ...
  6. }

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

  1. int main(void)
  2. {
  3.     int i, histogram[10];
  4.  
  5.     gen_random(10);
  6.     for (i = 0; i < 10; i++)
  7.         histogram[i] = howmany(i);
  8.     ...
  9. }

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

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

  1. int main(void)
  2. {
  3.     int i, histogram[10] = {0};
  4.  
  5.     gen_random(10);
  6.     for (i = 0; i < N; i++)
  7.         histogram[a[i]]++;
  8.     ...
  9. }

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

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

  1. srand(time(NULL));

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

习题

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

  1. 0  1  2  3  4  5  6  7  8  9
  2.  
  3. *  *  *  *     *  *  *     *
  4. *     *  *     *  *  *     *
  5.       *  *        *
  6.                   *
  7.                   *

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

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

则运行结果是：

  1. $ ./a.out
  2. 1 2 3 
  3. 1 3 2 
  4. 2 1 3 
  5. 2 3 1 
  6. 3 2 1 
  7. 3 1 2 
  8. 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个数做组合而不是做排列，就不能用原来的递归过程了，想想组合的递归过程应该怎么描述，编程实现它。

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