什么是模擬

僅僅使用較簡單的算法和數據結構的題目。

模擬顧名思義，就是按照題目的要求，一步步寫出代碼。

常見的模擬方法

a.用數學量和圖形描述問題

計算機處理的是數學量。若要用計算機解決實際問題，需要把實際問題抽象為數學量，或者數字。比如，記事本把文字按 ASCII 碼表轉換為數字儲存起 來，極品飛車把賽車的性能表示為數字，來權衡賽車的好壞。
一個漂亮的算法，需要用數學量表示出來。

有時，我們需要用更直觀的圖形來描述實際問題。

圖論就是一個絕佳的方法。圖是一種表示離散量間關系的形式，它也是一種思想，常被用于建模。同時，前人也為我們提供了很多現成的圖論算法，能夠解決很多常 見問題，這些將在之后被提到。

矩陣也是一種常見的方法。有時矩陣被表示成三角形的形式，比如“楊輝三角”。矩陣常常和數學有關，

在計算機計算時常常利用矩陣的遞推式。這也將在后面被提 到。

b.模擬計算過程

模擬方法是最常見、最直接的算法構建方法。

有些模擬算法還涉及到圖形和其他復雜的數據結構，這需要我們熟練地運用語言，巧妙地把其他關系轉化為數學量間關系。

舉例：
POJ1068

Description

Let S = s1 s2…s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2…pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2…wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).

Following is an example of the above encodings:
S (((()()())))

P-sequence 4 5 6666W-sequence 1 1 1456

Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.

Output

The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input

2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output

1 1 1 4 5 6
1 1 2 4 5 1 1 3 9

問題描述：

一組括號 (((( ) ( ) ( ) ) ) )

有兩種描述方法：

P方法：4 5 6 6 6 6 - 每一個）前，有幾個（

W方法：1 1 1 4 5 6 - 每一個)，向前數幾個是跟它匹配的(

要求是根據P求W

解題思路：

1. 雖然沒說，但是可以推測出，括號的個數是偶數;第一個一定是（，最后一個一定是）
2. P方法和W方法之間可能存在公式類的規律，但是要尋找不是特別簡單
3. 手動分析過程中，我們知道，可以模擬出推到W的過程-模擬法
4. 括號匹配，一定是stack結構
5. 思路就是：根據P還原括號數組，利用stack，推到出W

#include <iostream> #include <string> #include <stack> using namespace std; int main() {int n;cin >> n;for (int i=0; i<n; i++){int m;cin >> m;string str;int leftpa = 0;for (int j=0; j<m; j++) //使用stack，將p序列還原成括號序列{int p;cin >> p;for (int k=0; k<p-leftpa; k++) str += '(';str += ')';leftpa = p;}stack<int> s;for (string::iterator it=str.begin(); it!=str.end(); it++){//將左括號記為1，壓入棧，掃到右括號，彈出棧頂元素，將新的棧頂元素加上已掃到的右括號的數目，if (*it=='(')s.push(1);else{int p = s.top(); s.pop();cout << p << " ";if (!s.empty()) s.top() += p;}}cout << endl;}return 0; }

PS：

該程序設計當中用到了C++ STL中的stack

C++ Stack（堆棧） 是一個容器類的改編，為程序員提供了堆棧的全部功能，——也就是說實現了一個先進后出（FILO）的數據結構。

c++ stl棧stack的成員函數介紹:

empty() 堆棧為空則返回真

pop() 移除棧頂元素

push() 在棧頂增加元素

size() 返回棧中元素數目

top() 返回棧頂元素

想必搞懂了堆棧的內容，這樣類似的題應該不算難解。

總結

以上是生活随笔為你收集整理的ACM竞赛学习整理--模拟算法举例POJ1068的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。