2017年11月29日 星期三

取 n 個亂數,總和為 100

現在在中興大學資工系修資訊第二專長,這學期資料結構的課程有個作業是要產生 5~10 個亂數來畫一個霍夫曼樹 (嗯,霍夫曼樹是什麼還是上網查才知道的,反正不是今天的重點),不過作業有個附加條件,就是這 5~10 個亂數的總和要為 100。

我還在頭痛這種亂數要怎麼得到咧?幾個同修第二專長的數學老師提出不同的方法來取總和 100 的亂數了。這還滿有趣的,光是取亂數就有這麼多種解法。

我怕以後忘了,所以把這些數學老師提出的方法記錄下來,也許以後用得到。為了方便說明,底下都以『取 5 個亂數,總和為 100』為例,比較統一,比較好說明。

水桶法

陳志峰老師提出一個方法,我把它稱為水桶法。先準備 5 個水桶,準備來取亂數。

準備 5 個水桶
圖、準備 5 個水桶

丟 5 面的骰子 10 次 (其實就是產生 1~5 的亂數,連續做 10 次)。

丟 5 面的骰子 10 次
圖、丟 5 面的骰子 10 次

骰子丟出 1,就在 1 號水桶上畫一筆做記號,丟出 2,就在 2 號水桶上畫一筆做記號,依此類推。

將骰子出現的點數分類計次
圖、將骰子出現的點數分類計次

將各個桶子上畫記的次數轉為百分比,不看百分比記號的話,這些數字加總起來就是 100 了,因此可以達成我們的需求。

將次數轉換為百分比
圖、將次數轉換為百分比

優點:利用水桶法可以很快得到 5 個總和為 100 的亂數,如果我們丟 5 面的骰子 100 次,則每個水桶上畫記的次數就是我們要的答案。

int min = 1;
int max = 5;
int randSeed = 0;
int arry[6] = {0};

for (int i = 0; i < 100; i++)
{
    randSeed = rand() % (max - min + 1) + min;
    arry[randSeed] += 1;
}

缺點:因為每一面出現的機率都是相同的,所以丟骰子的次數越多,得到的結果會越趨近平均值,最後可能會得到 19、19、20、21、21 這樣加總為 100 的 5 個亂數。這樣看起來有點礙眼,所以雖然這個方法很快 (程式祇要三行),但是我們還是決定換一個方式取亂數。

數字加總後轉換為百分比

洪錦男老師提出數字加總再轉換為百分比,這樣也可以得到總和為 100 的亂數。方法是先產生 5 個整數亂數。

產生 5 個亂數
圖、產生 5 個亂數

將這 5 個亂數加總起來。

將 5 個亂數加總
圖、將 5 個亂數加總

前 4 個亂數除以總和,可以得到百分比數字,我們祇取整數位就好。

每個亂數除以總和,轉換為百分比
圖、每個亂數除以總和,轉換為百分比

因為我們祇取整數位數,結果就會有一些誤差,所以我們祇用前 4 個數字去轉換為百分比,最後一個數字不轉換為百分比,就是要用來修正這個誤差。

用 100 減掉剛剛 4 個轉換出來的百分比,可以得到第 5 個亂數,這樣加起來也是總和 100。是說,這個方法讓我想到統計學自由度……

用 100 扣除前 4 個數轉換出來的百分比
圖、用 100 扣除前 4 個數轉換出來的百分比

優點:這方法很直覺,多數人都想得到。

缺點:亂數除以總和之後轉換出來的數字常常會很相似,比方說 47、48、49、50、51 這 5 個數字轉換出來後會變成 19、19、20、20、22,看起來也是不夠亂,所以再換一個方法。

計算數線上的距離

洪婉馨老師建議利用數線來取亂數,她的做法是先產生 4 個介於 1~100 的亂數。

產生 4 個介於 1~100 的亂數
圖、產生 4 個介於 1~100 的亂數

然後將這些數字標記在 0~100 的數線上,這 4 個亂數會將數線分為 5 個線段,祇要計算這每個線段的長度就可以得到我們要的亂數了。

將亂數標記在 0~100 的數線上
圖、將亂數標記在 0~100 的數線上

怎麼計算線段長度呢?很簡單啊,就計算每個數字之間的距離就可以了,這樣加總起來也是 100。

計算出每個數之間的距離
圖、計算出每個數之間的距離

優點:這方法雖然也有經過轉換,但轉換出來的數字比較分散,不會像水桶法、加總法那麼集中。

缺點:還沒觀察到。

解謎過程很有趣

現在學資料結構,寫作業的過程就好像在解謎一樣,同學們一起想點子來破解這些難關,這過程真的很有趣。不過我好像都祇是聽人家說,自己沒什麼貢獻啊! Orz