3. 數組應用實例:直方圖

繼續上面的例子。我們統計一列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. 把第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年。