2. 数组应用实例:统计随机数

本节通过一个实例介绍使用数组的一些基本模式。问题是这样的:首先生成一列0~9的随机数保存在数组中,然后统计其中每个数字出现的次数并打印,检查这些数字的随机性如何。随机数在某些场合(例如游戏程序)是非常有用的,但是用计算机生成完全随机的数却不是那么容易。计算机执行每一条指令的结果都是确定的,没有一条指令产生的是随机数,调用C标准库得到的随机数其实是伪随机(Pseudorandom)数,是用数学公式算出来的确定的数,只不过这些数看起来很随机,并且从统计意义上也很接近均匀分布(Uniform Distribution)的随机数。

C标准库中生成伪随机数的是rand函数,使用这个函数需要包含头文件stdlib.h,它没有参数,返回值是一个介于0和RAND_MAX之间的接近均匀分布的整数。RAND_MAX是该头文件中定义的一个常量,在不同的平台上有不同的取值,但可以肯定它是一个非常大的整数。通常我们用到的随机数是限定在某个范围之中的,例如0~9,而不是0~RAND_MAX,我们可以用%运算符将rand函数的返回值处理一下:

int x = rand() % 10;

完整的程序如下:

例 8.2. 生成并打印随机数

#include <stdio.h>
#include <stdlib.h>
#define N 20

int a[N];

void gen_random(int upper_bound)
{
	int i;
	for (i = 0; i < N; i++)
		a[i] = rand() % upper_bound;
}

void print_random()
{
	int i;
	for (i = 0; i < N; i++)
		printf("%d ", a[i]);
	printf("\n");
}

int main(void)
{
	gen_random(10);
	print_random();
	return 0;
}

这里介绍一种新的语法:用#define定义一个常量。实际上编译器的工作分为两个阶段,先是预处理(Preprocess)阶段,然后才是编译阶段,用gcc-E选项可以看到预处理之后、编译之前的程序,例如:

$ gcc -E main.c
...(这里省略了很多行stdio.h和stdlib.h的代码)
int a[20];

void gen_random(int upper_bound)
{
 int i;
 for (i = 0; i < 20; i++)
  a[i] = rand() % upper_bound;
}

void print_random()
{
 int i;
 for (i = 0; i < 20; i++)
  printf("%d ", a[i]);
 printf("\n");
}

int main(void)
{
 gen_random(10);
 print_random();
 return 0;
}

可见在这里预处理器做了两件事情,一是把头文件stdio.hstdlib.h在代码中展开,二是把#define定义的标识符N替换成它的定义20(在代码中做了三处替换,分别位于数组的定义中和两个函数中)。像#include#define这种以#号开头的行称为预处理指示(Preprocessing Directive),我们将在第 21 章 预处理学习其它预处理指示。此外,用cpp main.c命令也可以达到同样的效果,只做预处理而不编译,cpp表示C preprocessor。

那么用#define定义的常量和第 3 节 “数据类型标志”讲的枚举常量有什么区别呢?首先,define不仅用于定义常量,也可以定义更复杂的语法结构,称为宏(Macro)定义。其次,define定义是在预处理阶段处理的,而枚举是在编译阶段处理的。试试看把第 3 节 “数据类型标志”习题2的程序改成下面这样是什么结果。

#include <stdio.h>
#define RECTANGULAR 1
#define POLAR 2

int main(void)
{
	int RECTANGULAR;
	printf("%d %d\n", RECTANGULAR, POLAR);
	return 0;
}

注意,虽然includedefine在预处理指示中有特殊含义,但它们并不是C语言的关键字,换句话说,它们也可以用作标识符,例如声明int include;或者void define(int);。在预处理阶段,如果一行以#号开头,后面跟includedefine,预处理器就认为这是一条预处理指示,除此之外出现在其它地方的includedefine预处理器并不关心,只是当成普通标识符交给编译阶段去处理。

回到随机数这个程序继续讨论,一开始为了便于分析和调试,我们取小一点的数组长度,只生成20个随机数,这个程序的运行结果为:

3 6 7 5 3 5 6 2 9 1 2 7 0 9 3 6 0 6 2 6

看起来很随机了。但随机性如何呢?分布得均匀吗?所谓均匀分布,应该每个数出现的概率是一样的。在上面的20个结果中,6出现了5次,而4和8一次也没出现过。但这说明不了什么问题,毕竟我们的样本太少了,才20个数,如果样本足够多,比如说100000个数,统计一下其中每个数字出现的次数也许能说明问题。但总不能把100000个数都打印出来然后挨个去数吧?我们需要写一个函数统计每个数字出现的次数。完整的程序如下:

例 8.3. 统计随机数的分布

#include <stdio.h>
#include <stdlib.h>
#define N 100000

int a[N];

void gen_random(int upper_bound)
{
	int i;
	for (i = 0; i < N; i++)
		a[i] = rand() % upper_bound;
}

int howmany(int value)
{
	int count = 0, i;
	for (i = 0; i < N; i++)
		if (a[i] == value)
			++count;
	return count;
}

int main(void)
{
	int i;

	gen_random(10);
	printf("value\thow many\n");
	for (i = 0; i < 10; i++)
		printf("%d\t%d\n", i, howmany(i));

	return 0;
}

我们只要把#define N的值改为100000,就相当于把整个程序中所有用到N的地方都改为100000了。如果我们不这么写,而是在定义数组时直接写成int a[20];,在每个循环中也直接使用20这个值,这称为硬编码(Hard coding)。如果原来的代码是硬编码的,那么一旦需要把20改成100000就非常麻烦,你需要找遍整个代码,判断哪些20表示这个数组的长度就改为100000,哪些20表示别的数量则不做改动,如果代码很长,这是很容易出错的。所以,写代码时应尽可能避免硬编码,这其实也是一个“提取公因式”的过程,和第 2 节 “数据抽象”讲的抽象具有相同的作用,就是避免一个地方的改动波及到大的范围。这个程序的运行结果如下:

$ ./a.out
value	how many
0	10130
1	10072
2	9990
3	9842
4	10174
5	9930
6	10059
7	9954
8	9891
9	9958

各数字出现的次数都在10000次左右,可见是比较均匀的。

习题

1、用rand函数生成[10, 20]之间的随机整数,表达式应该怎么写?