繼續上面的例子。我們統計一列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
個數做組合而不是做排列,就不能用原來的遞歸過程了,想想組合的遞歸過程應該怎麼描述,編程實現它。