继续上面的例子。我们统计一列0~9的随机数,打印每个数字出现的次数,像这样的统计结果称为直方图(Histogram)。有时候我们并不只是想打印,更想把统计结果保存下来以便做后续处理。我们可以把程序改成这样:
int main(void) { int howmanyones = howmany(1); int howmanytwos = howmany(2); ... }
这显然太繁琐了。要是这样的随机数有100个呢?显然这里用数组最合适不过了:
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)就可以得出结果:
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[18]的秒数,然后传给srand
:
srand(time(NULL));
然后再调用rand
,得到的随机数就和刚才完全不同了。调用time
函数需要包含头文件time.h
,这里的NULL
表示空指针,到第 1 节 “指针的基本概念”再详细解释。
1、补完本节直方图程序的main
函数,以可视化的形式打印直方图。例如上一节统计20个随机数的结果是:
0 1 2 3 4 5 6 7 8 9 * * * * * * * * * * * * * * * * * * * *
2、定义一个数组,编程打印它的全排列。比如定义:
#define N 3 int a[N] = { 1, 2, 3 };
则运行结果是:
$ ./a.out 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2 1 2 3
程序的主要思路是:
把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列。
把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列。
把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列。
可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想。你的程序要具有通用性,如果改变了N
和数组a
的定义(比如改成4个数的数组),其它代码不需要修改就可以做4个数的全排列(共24种排列)。
完成了上述要求之后再考虑第二个问题:如果再定义一个常量M
表示从N
个数中取几个数做排列(N == M
时表示全排列),原来的程序应该怎么改?
最后再考虑第三个问题:如果要求从N
个数中取M
个数做组合而不是做排列,就不能用原来的递归过程了,想想组合的递归过程应该怎么描述,编程实现它。