《算法設計程式設計實驗：大學程式設計課程與競賽訓練教材》——第2章 模拟法的程式設計實驗

模拟法原本是科學實驗的一種方法，即先在實驗室裡設計出與研究現象或過程（原型）相似的模型，然後根據模型和原型之間的相似關系，間接地研究原型的規律性。這種實驗方法後來被引入到計算機程式設計。原因是要求程式設計解決的許多問題具有不确定的性質，有些問題甚至很難建立數學模型，或者很難建立遞推、遞歸、枚舉、回溯法等常用算法。在這種情況下，一般采用模拟政策，即程式設計模拟某個過程，通過改變數學模型的各種參數，進而觀察變更這些參數所引起過程狀态的變化，由此展開算法設計。計算機模拟一般從形成問題到最後模拟實驗需經過七個步驟（如圖2-1所示）：

1）形成問題，明确模拟的目的和要求。

2）盡可能收集和處理與問題相關的資料。

3）形成數學模型。找出影響問題解決的各個要素，并描述它們在各時刻的狀态的有關變量（一般包括輸入變量、狀态變量和輸出變量）或參數；确定各要素之間互相作用和影響的規則，即描述變量之間的函數關系。選擇參數和變量的時候，還須考慮它們能否辨識或求解，以及模型最後是否适于檢驗。注意，模型一般分為兩種：

重制型，即模型能重制真實的過程或性能。

預測型，即模型能有效預測未來的趨勢。

由于模拟過程一般是随時間或指令的順序變化的，是以通常采用按時序模拟或按指令行事的方法。

4）根據收集的資料确定或估計模型中的參數，并選擇模型的初始狀态。

5）設計算法，編制程式。

6）程式驗證，檢驗程式與數學模型之間的一緻性,以及輸入量的合理性。

7）進行模拟實驗，對給定的輸入在計算機上執行程式。分析結果資料，收集和整理實驗結果并作出解釋。必要時可改變輸入量或部分模型結構，重新進行實驗。

程式設計模拟的形式一般有兩種：

1）随機模拟：題目給定或者隐含某一機率，設計者利用随機函數設定某一範圍的随機值，将符合機率的随機值作為參數。然後根據這一模拟的數學模型展開算法設計。由于解題過程借助了計算機的僞随機數發生數，其随機的意義要比實際問題中真實的随機變量稍差一些，是以模拟效果有不确定的因素。

2）過程模拟：題目不給出機率，要求程式設計者按照題意設計數學模型的各種參數，觀察變更這些參數所引起過程狀态的變化，由此展開算法設計。模拟效果完全取決于過程模拟的真實性和算法的正确性，不含任何不确定因素。由于過程模拟的結果無二義性，是以acm競賽大都采用過程模拟。

本章着重介紹過程模拟，展開三種模拟方法的實驗：

1）直叙式模拟。

2）篩選法模拟。

3）構造法模拟。