顧麗紅，丁淑妍

（中國石油大學(xué)（華東） 計算機(jī)與通信工程學(xué)院，山東 青島 266580）

0 引 言

計算思維[1]概念由Jeannette M. Wing教授于2006年首次完整提出，隨后引起了國內(nèi)計算機(jī)教育界的重視。教育部計算機(jī)專業(yè)教學(xué)指導(dǎo)委員會明確提出將計算思維列入計算機(jī)專業(yè)人才的專業(yè)基本能力[2]。如何培養(yǎng)非計算機(jī)專業(yè)大學(xué)生的計算思維能力，這是擺在大學(xué)計算機(jī)基礎(chǔ)教育工作者面前的難題。目前國內(nèi)高校的C語言程序設(shè)計課程普遍存在注重知識基礎(chǔ)而忽視能力基礎(chǔ)的問題，能力的培養(yǎng)則需要引入更多能引起學(xué)生興趣的程序設(shè)計案例實踐[3-5]。近幾年相關(guān)的教研論文越來越多，大多以數(shù)值計算類為主，面向跨計算學(xué)科的廣義計算思維[6]的案例設(shè)計實踐類論文還不多見。計算機(jī)模擬通常綜合了計算機(jī)科學(xué)家和領(lǐng)域科學(xué)家的思維方式，在課程教學(xué)實踐中引入這類程序設(shè)計案例，有利于培養(yǎng)學(xué)生的計算思維能力。

1 計算思維與計算機(jī)模擬

進(jìn)入信息和數(shù)據(jù)時代，計算思維是每個人的基本技能，就像邏輯思維、數(shù)學(xué)思維、設(shè)計思維一樣，是人們認(rèn)識問題和解決問題的重要思維方式之一。計算思維能力是人們有意識地使用計算機(jī)科學(xué)家的思想、方法、技術(shù)、工具、資源、環(huán)境進(jìn)行思考和活動的能力。如何全方位培養(yǎng)這種能力是教育工作者面臨的挑戰(zhàn)。

計算機(jī)模擬通常是指用抽象模型來模擬特定系統(tǒng)的計算機(jī)程序。人們在研究、設(shè)計、構(gòu)造復(fù)雜系統(tǒng)時，往往需要設(shè)計制造一個模型來進(jìn)行各種試驗。傳統(tǒng)方法是建立數(shù)學(xué)模型或?qū)嵨锬Ｐ?，前者缺乏直觀性也不便于試驗，后者比較直觀但不夠經(jīng)濟(jì)和方便。隨著計算機(jī)的出現(xiàn)和處理能力的不斷增強(qiáng)，利用計算機(jī)來模擬各種復(fù)雜系統(tǒng)，成為重要的科學(xué)研究手段。計算機(jī)模擬的一般過程如圖1所示。

其中，①數(shù)學(xué)建模與形式化。明確模擬工作的目標(biāo)，確定模擬方案的評價準(zhǔn)則。②模擬建模。根據(jù)問題特點(diǎn)和模擬要求從穩(wěn)定性、精度和性能3個維度設(shè)計合適的算法。③程序設(shè)計。把模擬模型用計算機(jī)能執(zhí)行的程序來描述。④模擬運(yùn)行。分析運(yùn)行結(jié)果是否合適，通過前幾步查找問題，不斷修正，直到結(jié)果滿意。⑤模擬實驗和結(jié)果處理。每一個方案，采用不同隨機(jī)數(shù)序列重復(fù)多次，采用數(shù)理統(tǒng)計方法分析模擬結(jié)果的統(tǒng)計特征；不同方案，采用相同隨機(jī)數(shù)序列進(jìn)行模擬運(yùn)行，消除因隨機(jī)數(shù)序列不同而引起的差異；模擬結(jié)果圖形化、可視化，乃至虛擬現(xiàn)實環(huán)境。

圖1 計算機(jī)模擬的一般處理過程

計算機(jī)模擬的設(shè)計原則包括：①分級模擬原則。采用與任務(wù)匹配的模型或算法，合理簡化問題，突出問題的關(guān)鍵。②效率兼顧原則。在模擬的不同階段，合理調(diào)整對準(zhǔn)確度和速度的要求，提高模擬效率。③可信驗證原則。所有模擬結(jié)果應(yīng)該有可信的驗證方法或依據(jù)。

在教學(xué)實踐中，讓學(xué)生充分理解計算機(jī)模擬過程中的算法構(gòu)建、迭代修正、數(shù)理統(tǒng)計方法，以及結(jié)果圖形化和可視化的重要性，在提升學(xué)生興趣的實踐中培養(yǎng)能力。

2 蒙特卡羅方法思想

蒙特卡羅方法是一種隨機(jī)模擬方法，以概率和統(tǒng)計理論方法為基礎(chǔ)，使用隨機(jī)數(shù)（偽隨機(jī)數(shù)）解決計算問題，又稱為統(tǒng)計模擬法。因其具有概率統(tǒng)計特征而獲得數(shù)學(xué)家馮·諾依曼用賭城蒙特卡羅來命名。蒙特卡羅方法起源于1777年法國數(shù)學(xué)家蒲豐（Buffon）提出用投針試驗計算圓周率π，進(jìn)而推廣到用概率法計算不規(guī)則圖形面積，甚至用小規(guī)模抽樣調(diào)查進(jìn)行民意測驗，來預(yù)測競選的優(yōu)勝者，也是同樣的思想。當(dāng)然科學(xué)計算中的問題比這復(fù)雜很多，比如金融領(lǐng)域的交易風(fēng)險評估，問題的維數(shù)（隨機(jī)變量的個數(shù)）高達(dá)數(shù)百、幾千，問題的難度成指數(shù)增長，傳統(tǒng)數(shù)值方法難以勝任，而蒙特卡羅方法因計算復(fù)雜性不依賴于維數(shù)則可以很好地對付維數(shù)災(zāi)難。

蒙特卡羅方法具有簡單、快速、節(jié)省存儲單元的優(yōu)點(diǎn)，省卻了一般人難以掌握的復(fù)雜的數(shù)學(xué)推導(dǎo)和演算過程，而且不受問題的幾何形狀復(fù)雜性影響，適用于處理大型復(fù)雜問題。隨著計算機(jī)處理復(fù)雜系統(tǒng)的能力日益增強(qiáng)，蒙特卡羅方法的應(yīng)用也越來越廣泛。它不僅較好地解決了多重積分計算、微分方程求解、積分方程求解、特征值計算和非線性方程組求解等高難度和復(fù)雜的數(shù)學(xué)計算問題，而且在計算物理學(xué)、核物理、金融工程學(xué)、宏觀經(jīng)濟(jì)學(xué)、生物醫(yī)學(xué)、可靠性及計算機(jī)科學(xué)等廣泛的領(lǐng)域都得到成功的應(yīng)用。

在教學(xué)實踐中，通過引入蒲豐投針問題和不規(guī)則面積計算問題，學(xué)生對蒙特卡羅方法思想有了濃厚的興趣，為之后的C語言算法設(shè)計思想的養(yǎng)成打下基礎(chǔ)。

3 蒙特卡羅模擬案例設(shè)計

蒙特卡羅模擬的基本思想：當(dāng)所求問題的解是某個事件的概率，或是某個隨機(jī)變量的數(shù)學(xué)期望，或是與概率、數(shù)學(xué)期望有關(guān)的量時，通過某種試驗的方法，得出該事件發(fā)生的頻率或者該隨機(jī)變量的若干個具體觀察值的算術(shù)平均值，進(jìn)而得到問題的解。采用蒙特卡羅方法進(jìn)行計算機(jī)模擬的步驟：首先設(shè)計反映系統(tǒng)各部分運(yùn)行時邏輯關(guān)系的邏輯框圖（模擬模型），然后通過具有各種概率分布的模擬隨機(jī)數(shù)來模擬隨機(jī)現(xiàn)象。

3.1 3種蒙特卡羅π的計算模擬

法國數(shù)學(xué)家蒲豐于18世紀(jì)提出投針問題：設(shè)有一個以平行且等距木紋鋪成的地板，現(xiàn)在隨意拋一支長度比木紋之間距離小的針，求針和其中一條木紋相交的概率，并以此概率可以近似計算圓周率。

蒲豐投針問題的數(shù)學(xué)建模：平行線距離為2a，針的長度為2l，且l≤a。設(shè)針投到地面上是隨機(jī)的，所以位置可以用二維隨機(jī)變量(x,θ)來描述，x為針中心的坐標(biāo)，θ為針與平行線的夾角。任意投針，就是意味著x與θ都是任意取的，但x的范圍限于[0,a]，夾角θ的范圍限于[0, π]。在此情況下，針與平行線相交的數(shù)學(xué)條件是：x≤l×sinθ。x和θ均服從均勻分布，且相互獨(dú)立，通過(x,θ)的概率密度函數(shù)求出概率分布：P= 2l/πa，所以π的近似值為：2l/aP。

蒲豐投針C語言算法設(shè)計思路：

（1）隨機(jī)生成一個介于[0,a]表示針中心坐標(biāo)的數(shù)x和一個介于[0, π]表示針與平行線的角度y；

（2）如果x≤l×siny，則表示針與平行線相交；

（3）計算π的近似值。

C語言程序設(shè)計實現(xiàn)如下：

蒲豐投針實驗的重要性在于它是第一個用幾何形式表達(dá)概率問題的例子，開創(chuàng)了使用隨機(jī)數(shù)處理確定性數(shù)學(xué)問題的先河。在教學(xué)實踐中，蒲豐實驗問題新穎奇妙，引起學(xué)生極大的興趣。為了達(dá)到舉一反三的效果，案例設(shè)計中引出蒙特卡羅思想計算π的另外兩種解法：圓中投點(diǎn)（幾何法）和隨機(jī)數(shù)互質(zhì)法。

圓中投點(diǎn)問題描述：有一正方形木板，以及內(nèi)切正方形內(nèi)接圓盤，隨機(jī)向正方形中投點(diǎn)，求點(diǎn)落在圓盤中的概率，并以此概率近似計算圓周率。

圓中投點(diǎn)數(shù)學(xué)建模：有一個以（0, 0）為中心的邊長為2的正方形，以及這個正方形中半徑為1的內(nèi)接圓，隨機(jī)向正方形中投點(diǎn)，求點(diǎn)落在內(nèi)接圓中的概率。設(shè)點(diǎn)投到木板上是隨機(jī)的，所以位置可以用二維隨機(jī)變量(x,y)來描述。任意投點(diǎn)，就是意味著x與y都是任意取的，二者的范圍限于[0, 1]。在此情況下，落在內(nèi)接圓中的數(shù)學(xué)條件是：x2+y2≤ 1。x和y均服從均勻分布，且相互獨(dú)立，求出概率分布：P= π/4，所以π的近似值為：4×P。

圓中投點(diǎn)C語言算法設(shè)計思路：

（1）隨機(jī)生成兩個介于[0, 1]區(qū)間的表示點(diǎn)坐標(biāo)的x和y；

（2）如果x2+y2≤1，則表示點(diǎn)落在內(nèi)接圓中；

（3）計算π的近似值。

C語言程序設(shè)計實現(xiàn)如下：

隨機(jī)數(shù)互質(zhì)問題描述：R·查特在1904年發(fā)現(xiàn)，兩個隨意寫出的數(shù)中，互質(zhì)的概率為6/π2，并以此概率近似計算圓周率。

隨機(jī)數(shù)互質(zhì)數(shù)學(xué)建模：任意產(chǎn)生兩個整數(shù)x和y，x和y均服從均勻分布，且相互獨(dú)立，通過數(shù)學(xué)推導(dǎo)（推導(dǎo)過程較復(fù)雜）可以求出x和y互質(zhì)的概率為：P= 6/π2，所以π的近似值為6/P的算術(shù)平方根。

隨機(jī)數(shù)互質(zhì)C語言算法設(shè)計思路：

（1）隨機(jī)生成兩個介于[0, 32 767)的x和y；

（2）如果x和y互為質(zhì)數(shù)，則統(tǒng)計變量累加1（注意特別處理生成數(shù)0的情況）；

（3）計算π的近似值。

C語言程序設(shè)計實現(xiàn)如下：

測試實驗的硬件環(huán)境：Intel i5 M540處理器，主頻2.53GHz，雙核四線程，3MB高速緩存。軟件環(huán)境：Window7旗艦版，CodeBlock 13.12 IDE環(huán)境，TDM-GCC v4.8.1編譯器。為了盡可能減少其他應(yīng)用程序?qū)y試的干擾，測試前盡可能關(guān)閉開機(jī)啟動項的應(yīng)用軟件，比如殺毒軟件、下載工具等，并禁用網(wǎng)絡(luò)。采用多次測試取均值的方法可以降低測試誤差，本實驗取10次測試的平均值，實驗結(jié)果如表1。

眾所周知，圓周率π的真值在3.141 592 6和3.141 592 7之間，假設(shè)以中間值3.141 592 65為真值，我們發(fā)現(xiàn)當(dāng)模擬的次數(shù)N為千萬次和億次的誤差分別為： 0.438‰和0.048‰， 0.235‰和0.023‰， 0.071‰和0.030‰，π的精度有了明顯的提高；當(dāng)N為10億次時，精度沒有明顯提升，求更高精度的π需要尋求其他方法。蒙特卡羅方法的收斂速度與N的算術(shù)平方根成比例，意味著要使結(jié)果精度提高一位，應(yīng)該增加一百倍的模擬計算工作量。

3.2 4種概率分布的隨機(jī)變量模擬

蒙特卡羅方法需要模擬隨機(jī)事件，即需要隨機(jī)數(shù)，那么計算機(jī)是如何產(chǎn)生隨機(jī)數(shù)的呢？隨機(jī)數(shù)是來自統(tǒng)計學(xué)的概念，真正的隨機(jī)數(shù)（真隨機(jī)數(shù)）是使用物理現(xiàn)象產(chǎn)生的，比如常見的彩票的搖號、擲錢幣、骰子、轉(zhuǎn)輪等，密碼學(xué)領(lǐng)域需要真隨機(jī)數(shù)。目前計算機(jī)產(chǎn)生的隨機(jī)數(shù)，是通過一個固定的、可以重復(fù)的算法產(chǎn)生，不是真正的隨機(jī)，但是具有類似于隨機(jī)數(shù)的統(tǒng)計特征，通常稱為偽隨機(jī)數(shù)，可以滿足蒙特卡羅方法的要求，所以默認(rèn)計算機(jī)產(chǎn)生的隨機(jī)數(shù)是隨機(jī)的。

用蒙特卡羅方法模擬系統(tǒng)或過程時，需要不同概率分布的隨機(jī)數(shù)，通常先生成均勻分布的（0, 1）隨機(jī)數(shù)，這是其他分布隨機(jī)數(shù)的基礎(chǔ)。理論上說，具有連續(xù)分布的隨機(jī)數(shù)，通過數(shù)學(xué)變換或近似等方法，可以生成其他任意分布的隨機(jī)數(shù)。設(shè)μi(i=1, 2, …)是區(qū)間[0, 1]內(nèi)的均勻分布的獨(dú)立隨機(jī)變量，而另一給定分布函數(shù)F(x)的隨機(jī)變量為則這一隨機(jī)變量xi可以由其反分布函數(shù)求得其抽樣值，即

均勻分布隨機(jī)變量算法設(shè)計思路：已知連續(xù)型隨機(jī)變量在有限區(qū)間內(nèi)取值，則其概率密度函數(shù)為其分布函數(shù)為知所以

指數(shù)分布隨機(jī)變量算法設(shè)計思路：已知連續(xù)型隨機(jī)變量在有限區(qū)間內(nèi)取值，則其概率密度函數(shù)為故其分布函數(shù)為知若(1-μ)是（0, 1）均勻分布隨機(jī)數(shù)，則可用下式簡化為

正態(tài)分布隨機(jī)變量算法設(shè)計思路：已知連續(xù)型隨機(jī)變量服從正態(tài)分布N(μ, σ2)，其概率密度函數(shù)為取區(qū)間（0, 1）上兩個均勻分布隨機(jī)數(shù)μ1和μ2，利用二元函數(shù)變換可得到個獨(dú)立的標(biāo)準(zhǔn)正態(tài)分布隨機(jī)變量。

表1 三種蒙特卡羅π的計算模擬結(jié)果

泊松分布隨機(jī)變量算法設(shè)計思路：泊松分布源自二項分布，在二項分布的伯努利試驗中，如果試驗次數(shù)n很大，二項分布的概率p很小，且乘積λ=np比較適中，則事件出現(xiàn)的次數(shù)的概率可以用泊松分布來逼近。泊松分布是離散型概率分布，表示固定尺度的連續(xù)區(qū)間上給定的事件發(fā)生次數(shù)的概率，其中n可以看作無窮大，泊松分布單位時間內(nèi)隨機(jī)事件發(fā)生的次數(shù)滿足泊松分布，比如電話交換機(jī)接收到呼叫的次數(shù)、汽車站臺的候客人數(shù)、機(jī)器出現(xiàn)故障的次數(shù)、自然災(zāi)害發(fā)生的次數(shù)、DNA序列的變異數(shù)等。

在C語言程序設(shè)計中，利用計算機(jī)產(chǎn)生的均勻分布隨機(jī)數(shù)，通過概率積分變換算法可以比較容易得到滿足其他概率分布的隨機(jī)變量。C語言中產(chǎn)生隨機(jī)數(shù)，通常用到兩個函數(shù)：srand()和rand()。srand()用來為計算機(jī)產(chǎn)生隨機(jī)數(shù)設(shè)置seed種子，否則每次程序運(yùn)行產(chǎn)生的隨機(jī)數(shù)序列是一樣的。避免這種情況的通常方法是采用計算機(jī)的當(dāng)前時間作為seed種子，因為時間是在不斷變化的。rand()函數(shù)隨機(jī)生成滿足均勻分布的[0,RAND_MAX]（RAND_MAX 為 0x7fff，即 32 767）之間的整數(shù)。如果要使范圍大一點(diǎn)，可以通過產(chǎn)生幾個隨機(jī)數(shù)的線性組合來實現(xiàn)任意范圍內(nèi)的均勻分布隨機(jī)數(shù)，而且經(jīng)過一定的四則運(yùn)算和取模運(yùn)算，可以比較容易地得到任意區(qū)間的隨機(jī)變量，比如：均勻分布、指數(shù)分布、正態(tài)分布和泊松分布。

產(chǎn)生高精度均勻分布隨機(jī)數(shù)。用rand()函數(shù)產(chǎn)生隨機(jī)數(shù)，需要對精度有所認(rèn)知。rand()的隨機(jī)數(shù)分辨率為32 767，兩個也就是65 534，如果需要要產(chǎn)生（-1 000, 1 000）之間且精度為4位小數(shù)點(diǎn)的均勻分布，則分辨率要求為1 000×10 000×2=20 000 000，這樣顯然遠(yuǎn)遠(yuǎn)不夠，但可以用兩個隨機(jī)數(shù)的乘法來達(dá)到精度要求，C語言程序設(shè)計片段如下。

利用[0, 1]區(qū)間的均勻分布可以產(chǎn)生指數(shù)分布隨機(jī)數(shù)，C語言程序設(shè)計片段如下。

利用[0, 1]區(qū)間的均勻分布可以產(chǎn)生正態(tài)分布隨機(jī)數(shù)（Box Muller方法），C語言程序設(shè)計片段如下。

利用[0, 1]區(qū)間的均勻分布可以產(chǎn)生泊松分布隨機(jī)數(shù)，Knuth算法設(shè)計思路：

1）l賦初值e-λ，k賦初值0，p賦初值1.0；

2）生成(0, 1)區(qū)間均勻分布隨機(jī)數(shù)u，p賦值為p*u，k累加1；

3）如果p>l，則重復(fù)2），直至不滿足條件；

4）返回k-1。

C語言程序設(shè)計片段如下：

實驗軟硬件環(huán)境同上，實驗結(jié)果如圖2（頻率曲線圖）。

從4種分布的頻率曲線圖可以看出，通過線性組合和四則運(yùn)算，計算機(jī)產(chǎn)生的偽隨機(jī)數(shù)可以滿足蒙特卡羅方法的要求，在實際生產(chǎn)、生活和工程項目中可以大量應(yīng)用。

4 結(jié) 語

蒙特卡羅模擬有很多專門的工具軟件，比如Mathmetica、MatLab、SPSS、CrystalBall等，其功能強(qiáng)大且容易使用。本文僅從C程序設(shè)計課程教學(xué)和實踐環(huán)節(jié)的需要，提出通過計算機(jī)模擬隨機(jī)事件引導(dǎo)學(xué)生對計算思維的認(rèn)知和培養(yǎng)學(xué)生動手實踐的能力。大數(shù)據(jù)時代需要培養(yǎng)更多理解概率論和數(shù)理統(tǒng)計原理的融合型復(fù)合人才，建議大學(xué)計算機(jī)基礎(chǔ)課程教學(xué)工作者根據(jù)學(xué)生的專業(yè)背景設(shè)計更多跨學(xué)科領(lǐng)域且體現(xiàn)計算思維思想的案例庫進(jìn)行交流和分享。下一步將在本文工作的基礎(chǔ)上，從大數(shù)據(jù)分析的角度，研究設(shè)計諸如投資風(fēng)險分析、隨機(jī)庫存預(yù)測等進(jìn)一步培養(yǎng)計算思維理能力的綜合型教學(xué)案例。

圖2 計算機(jī)生成的4種分布隨機(jī)數(shù)的頻率曲線圖

[1]Wing J M. Computational thinking[J]. Communications of the ACM, 2006, 49(3): 33-35.

[2]教育部高等學(xué)校計算機(jī)科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會. 高等學(xué)校計算機(jī)科學(xué)與技術(shù)專業(yè)人才專業(yè)能力構(gòu)成與培養(yǎng)[M]. 北京: 機(jī)械工業(yè)出版社, 2010.

[3]顧麗紅, 李傳秀, 吳少剛. 培養(yǎng)計算思維能力的矩陣乘法C語言程序設(shè)計案例探究[J]. 計算機(jī)教育, 2016(1): 149-152.

[4]姚天昉. 在程序設(shè)計課程中引入“計算思維”的實踐[J]. 中國大學(xué)教學(xué), 2012(2): 61-62.

[5]陳文智, 陳越, 莊越挺. 面向系統(tǒng)設(shè)計能力培養(yǎng)的教學(xué)改革探索[J]. 計算機(jī)教育, 2013(20): 70-76.

[6]蔣宗禮. 計算思維之我見[J]. 中國大學(xué)教學(xué), 2013(9): 5-10.