simulation

陽春召我以煙景,大塊假我以文章。《李白.春夜宴桃李園序》

simulation

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

範例:印出直角三角形

不加思索,窮舉試誤。

分割概念,編排步驟。

抽取概念,變成函式。

抽取差異,變成參數。

對比排比,調整參數。

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

UVa 10550

範例:排隊上車

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

分割概念,編排步驟。

抽取概念,變成函式。

對比排比,調整函式。

連同資料,變成物件。

聯想他物,發明模型。

UVa 10267 476 477 478

範例:轉骰子

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

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

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

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

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

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

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

前事之不忘,後事之師。《戰國策》

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把好朋友們聯集在一起。要判斷同一陣營,就看看大家是不是同一群好朋友;要判斷不同陣營,就看看對方的敵人是不是跟自己是同一群好朋友。由於一開始每個人都沒有敵人,所以替每個人都設定一個虛擬的假想敵。

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, reasoning, structure

前言

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

這是我個人意見。

符號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

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

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

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

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

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

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

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

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

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

後話

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

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

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

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

一、符號。

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

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

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

二、推理。

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

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

三、結構。

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

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

ansatz

擬設

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

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

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

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

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

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

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