Simulation

Simulation

Simulation就是「模擬」。撰寫程式,去模擬一個行為。

通常一個Simulation的問題,會詳述定義程式的功能與效果,並且規定一套固定的運作流程,程式必須有樣學樣、執行動作。程式設計人員不需要額外設計複雜的演算法,只需要照著題目的描述,建構適當的資料結構來儲存資訊,撰寫行為相仿的程式碼,就可以了。

Simulation主要是在考驗程式設計人員編寫程式碼的功力,而非考驗程式設計者的急智和創意。Simulation可說是程式設計的基本功──問題說得清清楚楚,不用設計複雜的演算法,只要照著規定做就好。這類題目很適合程式設計的初學者。

Simulation的問題有時相當難纏。若是問題規定的錯綜複雜,那麼寫起程式碼就會相當累人。若是一不小心犯了錯誤,只能望著那長篇大論、雜亂無章的程式碼,從中找出錯誤所在,相當痛苦。

另外,有一些目前尚未解決的經典題目,像是著名的Josephus Problem,由於目前沒有好的演算法,所以大家遇到了這種問題,就只能乖乖的照著題目的要求來做。這一類的題目也就變成了Simulation的題目。

UVa 10550

Dice Rotation

Dice Rotation

有兩個骰子,上面的點數順序,可能是亂的或是重複的。請辨別兩個骰子一不一樣。骰子經過旋轉後,如果六個對應的面,上面的點數皆相同,則骰子視為相同。

骰子一共有六個面──上下前後左右。我們可以用六個變數,來個別存六個面上頭的點數。用陣列也行。

讓陣列的第0格存入上面的值、第1格存左面的值,以此類推。當然也可以採用不同的方法來存。

若要讓骰子旋轉,則有三種旋轉方向。一、水平方向,二、垂直方向,三、順時鐘/逆時鐘方向。若要寫成程式,也不難。這裡示範水平方向朝西的旋轉。

要辨別兩個骰子一不一樣,則必須好好的旋轉其中一顆骰子,再跟另一顆比對。必須將骰子所有可能的情形都轉出來才行。我個人偏好這麼個轉法:水平方向轉一圈,順時針方向轉一圈,垂直方向轉一下,將以上動作連續做四次。如此可轉出所有情形。當然也可以採用不同的方法來轉。

這裡來點題目。

UVa 253 10877

Card Game

Card Game

撲克牌相信大家都玩過。也常見到有人用程式模擬一場撲克牌遊戲。首先,我們可以去wolfram math world找尋撲克牌的資料。

撲克牌的介紹:http://mathworld.wolfram.com/Cards.html

各種不同的撲克牌遊戲:http://mathworld.wolfram.com/topics/CardGames.html

資料結構

要用程式模擬一場撲克牌遊戲,最基本的,得先想出要怎麼洗牌、發牌、紀錄每個人的持牌、判斷牌型等等。先談談牌吧!撲克牌共四種花色,每種花色共十三張,總共五十二張牌(我們暫不考慮鬼牌)。最簡單的方法就是將牌由一號開始編號到五十二號,這樣每一張牌都有獨特的編號可以辨別它。這只要使用 int 型態的變數,就可以儲存牌的資訊了。有一個不錯的編碼方法就是:卡片的編號 = 卡片的花色 * 13 + (卡片數字-1)(規定梅花為0、方塊為1、愛心為2、黑桃為3)。當然也可以根據遊戲的性質,採用不同的編碼方法。

要儲存卡片資訊,可以使用一個簡單的struct。

為了程式碼閱讀方便,可以使用enum當作數值名稱。

或者用 const 變數。

網路上另外還有許多深奧的方法,大家可以自行搜尋資料。

發牌和洗牌

先將所有的牌都放進一個陣列中(或link list),然後利用亂數隨便交換就可以了。【待補random permutation】

紀錄持牌

可以使用陣列(或link list)。

判斷牌型

由於每一種牌型都相當特殊,所以只能個別模擬。這裡有牌型的列表:http://mathworld.wolfram.com/Poker.html

這裡提供一個判斷牌型的小技巧。牌型大部分都是以同樣數字,或者連續數字組成的。所以你可以先將手牌依照編號排序之後,再來進行牌型的判斷。這樣會方便許多。

還有一個小技巧,是關於順子的部分。順子會有10 J Q K A的這種順子出現,然而我們知道A是1點,它有時也可以當作比K還大的點來用;但是順子卻又不循環,也就是沒有K A 2 3 4的這種順子。要解決這個問題,你可以新增一張點數為14點的牌,當順子為A 1 2 3 4的時候,就將A視做1點;當順子為10 J Q K A的時候,就將A視做 14點。如此也解決了K A 2 3 4 = 13 14 2 3 4 = 13 1 2 3 4的這種順子的問題。

比較牌型大小

要判斷兩副手牌到底誰大誰小,事實上有點麻煩。有一個不錯的方法,就是用分數來計算:事先制定好每種牌型的分數,比較好的牌型分數比較高。要是遇到同一種牌形,就找出數字最大、數字重複最多的,將這張牌的數字、花色,乘上牌型的分數。這樣就可以比較牌型大小。另外也可以替一副手牌打分數,比較兩副手牌孰好孰壞。

結語

Card Game是程式設計的經典問題,網路上也可以找到很多設計的方法。我對Card Game淺見寡聞,亦黔驢技窮。若是對這方面有興趣,可以到國外的論壇找找看,相信會有更多更好的設計方法。當然我也不忘要提供題目。

UVa 127 131 162 170 178 181 451 462 555

Board Game

Board Game

使用棋盤進行的遊戲。例如象旗、西洋棋、將旗、圍棋、五子棋、黑白棋。我並不專精棋類遊戲的程式,所以今後慢慢整理吧!有緣便會更新的。

這裡整理了一些棋類遊戲的問題,有些我也沒做過。

UVa 220 852 10196 10363 10996

The Game of Life

生命遊戲

生命遊戲是相當有名的數學問題。你可以以關鍵字「數學 生命遊戲」來搜尋資料。英文有個專有名詞叫做cellular automation,你也可以試著去找這方面的資料。

以下是我從網路上面找到的規則。現在有一個二維的方格平面,每個格子都有一個細胞,可能是活的,可能是死的。而我們知道一開始的狀態是怎麼樣的。這個平面的狀況會隨時間變動,規則如下:

復活:一個死的細胞,若是它的八個鄰居,有三個細胞是活的,則在下一刻復活。
存活:一個活的細胞,若是它的八個鄰居,有兩個或三個細胞是活的,則在下一刻存活。
死於孤單:一個活的細胞,若是它的八個鄰居,只有零個或一個細胞是活的,則在下一刻死亡。
死於擁擠:一個活的細胞,若是它的八個鄰居,有四個以上的細胞是活的,則在下一刻死亡。

實作程式碼

我們可以弄兩張地圖,第一張地圖儲存現在這個時刻的狀態,第二張地圖儲存下一個時刻的狀態。然後兩張地圖交替使用,以節省記憶體空間。可以嘗試將一個細胞延展的過程寫成一個函式,以利於程式碼的閱讀。

為了讓地圖能夠交叉利用、節省空間,將程式碼做點修正。

這裡提供兩個網頁,有Applet可以玩,相當有趣:http://www.bitstorm.org/gameoflife/http://www.math.com/students/wonders/life/life.html

這裡提供一些類題。

UVa 447 457 10443 10507