simulation

撰寫程式，模擬行為。沒有前例，那就創例。

範例：印出直角三角形

不加思索，窮舉試誤。

// n 是三角形邊長 void print_triangle(int n) { // 依序窮舉每一個位置，逐一判斷要印什麼。 for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { if (i + j < n - 1) cout << ' '; else cout << '@'; } cout << '\n'; } }

分割概念，編排步驟。

void print_triangle(int n) { // 直角三角形分成多行 for (int i=0; i<n; i++) { // 一行分成兩階段：空白、三角形 for (int j=0; j<n-i-1; j++) cout << ' '; for (int j=n-i-1; j<n; j++) cout << '@'; cout << '\n'; } }

抽取概念，變成函式。

// 一行：i 是行數、n 是三角形邊長 void print_line(int i, int n) { // 一行分成兩階段：空白、三角形 for (int j=0; j<n-i-1; j++) cout << ' '; for (int j=n-i-1; j<n; j++) cout << '@'; cout << '\n'; } void print_triangle(int n) { for (int i=0; i<n; i++) print_line(i, n); }

抽取差異，變成參數。

// 一串：n 是長度、c 是字元 void print_sequence(int n, char c) { for (int i=0; i<n; ++i) cout << c; } // 一行：i 是行數、n 是三角形邊長 void print_line(int i, int n) { print_sequence(n-i-1, ' '); print_sequence(i , '@'); cout << '\n'; } void print_triangle(int n) { for (int i=0; i<n; i++) print_line(i, n); }

對比排比，調整參數。

void print_sequence(int n, char c) { for (int i=0; i<n; ++i) cout << c; } // 一行：s 是空白長度、t 是符號長度（兩者都是填充長度） void print_line(int s, int t) { print_sequence(s, ' '); print_sequence(t, '@'); cout << '\n'; } void print_triangle(int n) { for (int i=0; i<n; i++) print_line(i, n-i-1); }

經過整頓，一目了然。容易閱讀，方便維護。

UVa 10550

範例：排隊上車

等車的人排成一列。人不時抵達，隊伍增長；車不時抵達，隊伍減短。請隨時記錄排隊隊伍依序是誰。

分割概念，編排步驟。

void lineup() { string array[100000]; int head = 0, tail = 0; string command; while (cin >> command) // 讀指令 { if (command == "people") // 先處理人 { string name; // 先讀指令 cin >> name; array[tail] = name; // 再做儲存 tail++; } else if (command == "car") // 再處理車 { int seat; // 先讀指令 cin >> seat; head += seat; // 再做儲存 } } }

抽取概念，變成函式。

string array[100000]; int head = 0, tail = 0; // 人來了 void people(string name) { array[tail] = name; tail++; } // 車來了 void car(int seat) { head += seat; } // 只讀指令 void lineup() { string command; while (cin >> command) if (command == "people") { string name; cin >> name; people(name); } else if (command == "car") { int seat; cin >> seat; car(seat); } }

對比排比，調整函式。

string array[100000]; int head = 0, tail = 0; // 人來了 void come(string name) { array[tail] = name; tail++; // 對比排比之後，事情變得單純，容易考慮的更細膩。 if (tail >= 100000) assert(false); } // 人走了 void leave() { // head++; // 對比排比之後，事情變得單純，容易考慮的更細膩。 if (head < tail) head++; } // 車來了 void car(int seat) { for (int i=0; i<seat; ++i) leave(); } void lineup() { string command; while (cin >> command) if (command == "people") { string name; cin >> name; come(name); } else if (command == "car") { int seat; cin >> seat; car(seat); } }

連同資料，變成物件。

// 排隊人生 struct Line { string array[100000]; int head = 0, tail = 0; void come(string name); // 人來了 void leave(); // 人走了 void car(int seat); // 車來了 }; void Line::come(string name) { array[tail] = name; tail++; if (tail >= 100000) assert(false); } void Line::leave() { if (head < tail) head++; } void Line::car(int seat) { for (int i=0; i<seat; ++i) leave(); } void lineup() { Line line; while (cin >> command) if (command == "people") { string name; cin >> name; line.come(name); } else if (command == "car") { int seat; cin >> seat; line.car(seat); } }

聯想他物，發明模型。

struct MultipopQueue { string array[100000]; int head = 0, tail = 0; void push(string name); // 原本是人來了 void pop(); // 原本是人走了 void multipop(int n); // 原本是車來了 }; template class<T> class MultipopQueue // 資料型別抽象化（從特例變通例） { private: T array[100000]; int head, tail; public: MultipopQueue(): head(0), tail(0) {} void push(const T& name); // 用特殊語法，做補充說明 void pop(); void multipop(const int n); // 用特殊語法，做補充說明 };

UVa 10267 476 477 478

範例：轉骰子

請辨別兩顆骰子一不一樣。骰子經過旋轉後，如果六個對應的面，上面的點數皆相同，則骰子視為相同。

要辨別兩顆骰子一不一樣，一種方式是旋轉其中一顆骰子，再跟另一顆比對。必須將骰子所有可能的情形都轉出來才行。

骰子有六個面：上下前後左右。建立六個變數、或者六格的陣列，分別儲存六個面的點數。陣列的第0格存入上面的點數、第1格存左面的點數、……。當然也可以採用不同的儲存方法。

骰子有三種旋轉方向：東西方向、南北方向、時鐘方向。我個人偏好的轉法是：東西方向轉一圈，順時針方向轉一圈，南北方向轉一下，以上動作循環四次，就能轉出所有情形。

亦得採用其他轉法，最好的轉法只需轉24次，讀者可以想想看怎麼做。

亦得預先計算所有旋轉結果，儲存於lookup table，以節省旋轉時間。

// 往西轉一下 void turn_west(int dice[6]) { int temp = dice[1]; dice[1] = dice[2]; dice[2] = dice[3]; dice[3] = dice[4]; dice[4] = temp; } // 六個面是否一一對應 bool equal(int a[6], int b[6]) { for (int i=0; i<6; i++) if (a[i] != b[i]) return false; return true; } // 兩顆骰子是否相同 bool check(int a[6], int b[6]) { for (int i=0; i<4; i++) { for (int j=0; j<4; j++) { turn_west(b); if (equal(a,b)) return true; } for (int j=0; j<4; j++) { turn_clockwise(b); if (equal(a,b)) return true; } turn_north(b); if (equal(a,b)) return true; } return false; }

UVa 253 10877

範例：踩地雷

試著用程式模擬踩地雷吧！

UVa 10189 10279 11142 ICPC 4335

範例：撲克牌

試著用程式模擬各種撲克牌遊戲吧！

UVa 127 131 162 170 178 181 451 462 555

範例：下棋

試著用程式模擬各種棋吧！

UVa 220 852 10196 10363 10996 11210 1589

範例：試算表

試著用程式模擬試算表吧！

UVa 196 215 512

modeling

把問題對應到耳熟能詳的模型，套用既有模型解決新問題。

範例：平行四邊形面積

小學數學老師教過：長方形的面積是「長乘寬」。儘管不知道原因，不過這個公式肯定是正確的。那麼，請問平行四邊形面積如何計算？

把平行四邊形凸出的三角形切下來，補在另一邊，平行四邊形就變成了長方形。想要計算平行四邊形面積，可以直接套用長方形面積公式。

平行四邊形的底，就是長方形的長；平行四邊形的高，就是長方形的寬。平行四邊形的元件，一一對應到長方形。

範例：約瑟夫問題（Josephus problem）

8個人圍成一圈，現在從第一個人開始報數，數到第5人時，就殺死這第5人；然後從被殺的下一位繼續重新報數，數到第5人時，就殺死這第5人。如此不斷數5人、殺此人，直到最後會剩下一個人，請問他是誰？

數人和殺人的動作可以對應到佇列（queue）的操作。首先把每個人依序塞入佇列，接著連續pop和push 4人，接著pop第5人時，不要將他塞回佇列裡面即可！

範例：用圖論作為模型，模擬小畫家倒墨水。

以圖論的觀點來看，flood fill algorithm其實就是運用depth-first search找到connected component。

範例：system of difference constraints in linear programming

問題：給定變數x₁到xɴ，並給定一些xᵢ-xⱼ≤c的式子，作為條件限制。請判斷有沒有解，如果有解就求出其中一組解。

這個問題可以巧妙的轉換成最短路徑問題。x₁到xɴ看作是圖上的N個點，一道xᵢ-xⱼ≤c的限制式子看作是一條xⱼ到xᵢ的邊，其權重是c。

如果無解，那麼圖上有負環。如果有解，那麼圖上各點的最短路徑長度就是其中一組解。為了讓圖上各點都有最短路徑長度值，可參考Johnson's algorithm的做法。

UVa 515 ICPC 2058

範例：sentiment relation in social balance theory

從前有一位心理學者認為，人與人之間的關係，可以粗略分為兩種：互相喜歡、互相討厭。這種關係稱作sentiment relation，是一種雙向關係，而且擁有喜歡與討厭兩種類型。假使兩人之間好惡分明，沒有亦敵亦友的情況，就會形成sentiment relation。

   like            hate
A<------>B      A<------>B

另外sentiment relation還具有相當特殊的性質，有點像是transitivity、symmetry、antisymmetry的總合。這種性質的最佳寫照，諸如同仇敵愾、合縱連橫等等，翻成白話就是這樣：

1. 朋友的朋友就是我的朋友。
2. 朋友的敵人就是我的敵人。
3. 敵人的朋友就是我的敵人。
4. 敵人的敵人就是我的朋友。

在sentiment relation所形成的社交結構當中，如果產生了好與惡的矛盾，那麼這樣的社交結構就是不平衡的；如果好與惡合理，那麼這樣的社交結構就是平衡的。心理學者相信，當社交結構不平衡的時候，個體會嘗試改變自己的觀點，讓社交結構趨向平衡。

balance:

      A                A           like   like
like / \ like    hate / \ hate      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     like             like         hate   hate
 
imbalance:

      A                A           like   like
hate / \ hate    like / \ like      ----A----
    /   \            /   \         /  ha|te  \
   B-----C          B-----C       B-----C-----D
     hate             hate         like   like

後來心理學者進一步發現，當社交結構達到平衡，所有人可以分成兩大陣營，使得陣營內部的關係都是互相喜歡，陣營與陣營之間的關係都是互相討厭。

說了這麼多終於要提到重點。現在問題來了，假設社交結構是平衡的，而我們也知道一些兩兩相互喜歡、相互討厭的資訊時，我們該如何確認誰在同一陣營、誰在不同陣營呢？

一、以bipartite graph作為模型：

把社交結構看作是bipartite graph，bipartite graph的兩側分別是兩大陣營。首先利用graph traversal走訪喜歡的邊，找出所有連通分量，並各自縮成一點。然後再度利用graph traversal走訪討厭的邊，嘗試建立bipartite graph，如果無法建立則表示社交結構不平衡。

二、以disjoint sets作為模型：

當x與y是朋友：
　x及朋友、y及朋友，都是好朋友。
　x的敵人、y的敵人，都是好朋友。

當x與y是敵人：
　x及朋友、y的敵人，都是好朋友。
　x的敵人、y及朋友，都是好朋友。

把陣營看作是disjoint sets，利用merge把好朋友們聯集在一起。要判斷同一陣營，就看看大家是不是同一群好朋友；要判斷不同陣營，就看看對方的敵人是不是跟自己是同一群好朋友。由於一開始每個人都沒有敵人，所以替每個人都設定一個虛擬的假想敵。

#define _x (x + 100) // x的假想敵 #define _y (y + 100) // y的假想敵 // disjoint-sets forest int p[100 + 100]; // 前百人為本尊，後百人為假想敵。 void init() {for (int i=0; i<200; ++i) p[i] = i;} int find(int x) {return x == p[x] ? x : (p[x] = find(p[x]));} void merge(int x, int y) {p[find(x)] = find(y);} bool if_like(int x, int y) { return find(x) == find(y); // return find(_x) == find(_y); } bool if_hate(int x, int y) { return find(x) == find(_y); // return find(_x) == find(y); } // 結交朋友 void like(int x, int y) { if (if_hate(x, y)) return; // imbalance merge(x, y); merge(_x, _y); } // 樹立敵人 void hate(int x, int y) { if (if_like(x, y)) return; // imbalance merge(x, _y); merge(_x, y); }

UVa 10158 10505 10608

範例：點燈遊戲（lights out puzzle）（minimum all-ones problem）

嘗試熄滅（或點燃）所有燈。按下任何一個開關，都會連帶影響自己及其四周的燈，亮變暗、暗變亮。

無論同時按或分開按、先按或後按，造成的影響都一樣。一個開關按兩次，將相互抵銷，如同按零次。

一、以函數當作模型，函數是各盤面之間的關聯：g(舊盤面) = 新盤面，g為一種按開關的方式。這種模型相當常見，但是不適用此題。

二、以函數當作模型，函數是開關和盤面的對應關係：f(按下的開關) = 盤面，f是遊戲規則。

只要求出f的反函數，就可以用盤面判斷按下的開關。巧妙的是，f是線性函數，故可以解一次方程組來找到反函數。解一次方程組可以用「高斯消去法」。

加法運算：f(同時按下開關A和B) = f(按下開關A) + f(按下開關B)。設定成xor。
倍率運算：f(按下開關A一共k次) = k f(按下開關A)。k模二之後，設定成and。

然而f不見得有反函數，端看遊戲規則和盤面形狀。當f有反函數，無論盤面長得如何，都一定有解。當f沒有反函數時，則難以確定盤面是否有解，屬於NP-complete問題。

UVa 10309 10318 ICPC 8045

reduction

套用模型當中，有一種情況是：原問題是某一個問題的特例。套用通例，解決特例，稱作「歸約」。

因為通例相對複雜、特例相對單純，所以原問題極可能存在更快更好的解法。

範例：最短間距（minimum gap problem）

一條鐵道，沿途設站。已知里程，請找出距離最近的兩站。

以數線作為模型，鐵道對應到數線、車站對應到點座標，距離最近的兩站對應到「數線上距離最近的兩個點」。

想要解決「數線上距離最近的兩個點」，可以套用先前介紹的「平面上距離最近的兩個點」。這兩個問題的本質是相同的，前者是一維版本，後者是二維版本；前者是特例，後者是通例。

只要把每個車站的座標，增加一個維度，該維度的數值通通設定為相同數值，然後計算「平面上距離最近的兩個點」，就得到距離最近的兩站。

「數線上距離最近的兩個點」是特例、「平面上距離最近的兩個點」是通例，我們有機會替「數線上距離最近的兩個點」找到計算時間更短、更有效率的演算法。

範例：用生命遊戲作為模型，模擬生命遊戲。

前言

學習數學、學習理科，分成三個階段：符號、推理、結構。

這是我個人意見。

符號symbol

p=mv。動量等於質量乘以速度。

數學式子非常簡單，只是一個乘法式子。舉例來說，質量2，速度3，6=2×3，得到動量6，我想大家都會計算。

圖解說明也非常簡單。畫一個正方形，代表物體。畫一條斜紋橫線，代表地板。畫一個箭頭，代表速度。寫上一個m，代表質量。

但是速度是什麼？質量是什麼？這才是問題所在。

為了幫助想像，只好舉例，只好類比。

速度：實際揮動手臂。動得很快，速度快。動得很慢，速度慢。

質量：如果是在地球表面上的話，可以稱重稱出大小。

動量：乘法是n份加法。質量速度的份量越多，動量就越多。

舉例來說，車子比人類更重、更快，所以動量更大。但是車子靜止不動的話，那就沒有動量。

大家聽完這些話，連結人生經驗，激發大腦的分門別類的機制，然後大家就對動量有一點點新的感受了。

符號本身是一種代稱。然而數學概念往往沒有實物可以參照。即便是實物也往往出現不同見解。每個人只能依賴自己的感受。舉例來說，我跟你對於富裕的理解不是同一件事情，我跟你看到的紅色不是同一種紅色。符號的意義只能靠自己去揣摩。藉由他人的行為舉止，揣摩符號的意義。有如學習語言。

符號同時也是一種泛稱。我在講p = mv的時候，其實我是在講車子在動、身體在動、……。甚至是我自己都沒想過的東西。怎樣算是p = mv，怎樣不算是p = mv，需要經年累月去揣摩。

推導derivation、推理reasoning

推導就是一個東西變成另一個東西。使用100%正確的變換方法。從已經確定的東西作為前提，一直變、一直變，變出新的結論。

(0) p = mv
(1) d/dt p = d/dt mv    等號兩側同時微分，依然相等。
(2) d/dt p = m d/dt v   假設m是常數。根據分配律，依然相等。
(3) let f = d/dt p      設定新符號
    let a = d/dt v
    f = ma              牛頓運動定律

推理就是替換這段過程當中的某些東西，重新推導一遍。替換前提、替換結論、替換中間過程。

比方說很多人不瞭解什麼是微分。那麼我們替換成其他數學元件。我把「微分」替換成「平均數」與「無限微小」。

(0) p = mv

    p₁+p₂+...   m₁v₁+m₂v₂+...
(1) ————————— = —————————————     一段時間Δt的平均數
        Δt           Δt           等號兩側同加同除，依然相等。

    p₁+p₂+...     v₁+v₂+... 
(2) ————————— = m —————————       假設m不隨時間改變
        Δt           Δt           m₁ = m₂ = ...

            p₁+p₂+...
(3) let f = ————————— when Δt→0   那一段時間很短很短
                Δt   

            v₁+v₂+...
    let a = ————————— when Δt→0
               Δt

    f = ma                        牛頓運動定律

也可以替換前提、替換結論，推導Δx = vΔt + 1/2 aΔt²。

大部分教科書只會推導，不會推理。大部分教師在課堂上也只會推導，不會推理。你可以自己推理。

結構structure

結構好比書籍目錄。

比方說：微分是重中之重，應該單獨建立章節。

chapter 1: 數學基礎知識：微分
chapter 2: p = mv
chapter 3: f = ma

但是也可能是這樣：微分只是微不足道的配角。

chapter 1: p = mv
chapter 2: f = ma
   chapter 2.1: 數學基礎知識：微分

甚至也可能是這樣：額外補充一些也很重要的東西。

chapter 1: 微積分
   chapter 1.1: 微分
   chapter 1.2: 積分
chapter 2: 運動定律
   chapter 2.1: p = mv
   chapter 2.2: f = d/dt p
　　　chapter 2.2.1: f = ma

學者的腦子裡面都有好幾套結構。學者只會挑出其中一套結構寫成書籍。學者依照經驗，決定誰先誰後、誰大誰小。什麼是重點，什麼是順便，看了就知道。

做研究，本質上就是想出了一套與眾不同的結構，並且找到了結構缺失的地方，並且完善了結構。

如何建立結構呢？嘗試各種推理，然後物以類聚。

一個更複雜的例子：如何介紹台灣大學

從官方網站可以看到，台灣大學分成兩種單位：行政組織、學術單位。行政組織細分成學生事務處、教務處、總務處、圖書館、……。學術單位細分成文學院、理學院、工學院、醫學院、……。

如果你在路上遇到一個路人，你會這樣介紹台灣大學嗎？不會。你會告訴他台灣大學在台北。前門是羅斯福路，鄰近捷運公館站。後門是辛亥路，鄰近捷運科技大樓站。另一個後門在長興街，那裏是學生宿舍，只有公車。路人在意地理位置。

如果是網路筆戰，又有另外一套思路。網民在意的是文科台政北，理科四大四中，醫科台大陽明北醫。大家在意排名、在意優劣。

你得視情況拿出適合的結構。

如何選擇適當的結構呢？多聊天、多看書。

後話

先懂符號，再懂推理，最後才是結構。前面單純，後面複雜。

學者、著作，被公認為大師、經典，通常是三者之一有創新。

教師是否優秀，也可以從這三者來分析。

學生學習困難，通常是三者之一出了問題。甚至都有問題。

一、符號。

學生對應不上符號與概念。又或者，學生還沒辦法完全確定那是什麼、其他還有什麼。

舉個例子。世界上有一種長相特別的動物，馬的耳朵、犀牛的腿、豬的身體、象的鼻子。即便我這樣形容，你也不能十分確定這種動物的長相，除非你看過實物。

人生經歷豐富，時機成熟足以頓悟。有時候則是怎麼也悟不了。

二、推理。

學生不熟悉推導過程的某些東西。又或者，學生還沒習慣。

很多時候只是還沒習慣。例如籃球運動，你能看懂帶球上籃的動作，你也知道每個步驟：運球、收球、舉球、單手扶球，送球，一邊跑一邊做上述動作。萬事俱備，但是實際去做卻做不好，畢竟身體還沒習慣。數學知識也是同樣的道理，實際去算卻算不好，畢竟腦袋還沒習慣。

三、結構。

學生的知識量不足以撐起一個穩定的結構，甚至在對話過程當中不斷調整。又或者，學生的結構不是老師的結構，雞同鴨講。

例如教育部不讓台灣大學校長就任，那就需要建立第四種結構才能解釋得通。你跟學生聊體制，結果學生想的是排名：台大教授都很優秀，誰來都沒差吧，為什麼教育部需要做這種事？學生自己解釋不通，那就沒辦法弄懂。

擬設

觀察問題，回想曾經遭遇的類似問題，其具備哪些特性。一開始就假設問題已經具備此特性。採用此特性進行推理，找出其他特性、以及不可能具備的特性，藉此減少問題當中尚未解明的部分。

擬設的同義詞是「八九不離十」。擬設是「幾乎正確的假設」，只是需要實際驗證。當問題找到答案了，始能驗證擬設是正確的。

另外，如果推理出現矛盾，那就表示一開始的假設不正確。此即邏輯學當中的proof by contradiction。

另外，即便推理沒有出現矛盾，也不表示一開始的假設正確、不正確。此即邏輯學當中的false imply anything。例如「先射箭再畫靶」。得到答案之後，還是得想辦法驗證一開始的假設是正確的。

擬設的知名範例是微分方程式求解。事先假設解的形式。

已有數學定理保證特定的微分方程式有唯一解。因此，得到答案之後，代入驗算確認無誤，一定會是唯一正確答案。此時，事先假設解的形式，一定會是唯一正確形式。

有機會我再補充更多例子。一時之間沒辦法想出例子。