作者  bleed1979 (十三)                                       看板  C_and_CPP 
 標題  [心得][ACM] 10315 - Poker Hands                                        
 時間  Fri Jun 11 00:28:35 2010                                               
───────────────────────────────────────

撲克牌遊戲梭哈比較大小，我以往的作法是從同花順一路比到烏龍(什麼牌型都沒有)。
資料結構使用的是4 * 13的陣列。相信這也是較尋常的作法。
今次我用bit運算來實現梭哈遊戲的比較，希望能趨於高效。

題目︰http://icpcres.ecs.baylor.edu/onlinejudge/external/103/10315.html
中譯︰http://www.tcgs.tc.edu.tw/~sagit/luckycat/q10315.htm

題目的輸出為兩個玩家的手牌是黑方(前者)比較大還是白方(後者)比較大還是平手(Tie)
。
比較大小的定義請見中譯。
順子是沒有A2345，最大的順子是TJQKA。
除此之外，規則就和我們平常玩的一樣。
另外，此題允許相同的牌出現兩次以上。但不會有不合法的牌型(五張一樣)。
例如，4D 4D 7D 9D kD，視為同花，而不是一對(以最高者為之)。
比較大小是要比到底的。例如︰如果同樣是三條且三條的大小都一樣，要以廢牌決勝負。

題目定義好後，來決定資料結構。
因為只能使用條件判斷和位元運算，所以除了讀入資料是用char陣列以外，就不能再用陣
列。
以下是實做的資料結構︰

struct Poker
{
  int type;
  int suit;
  int pair1, pair2;
  int rank;
};

和

一個bool值用以判斷是否形成三張一樣。

是的，您沒看錯，主要的資料結構只需要五個int。
type決定手牌的牌型(同花順，四條...等)。
suit代表花色。
rank代表牌的數字。
pair1和pair2代表如果有兩張以上一樣的牌的話，該一樣的牌的數字大小。
葫蘆和兩對都會需要用到pair2。

以下列出所有程式實作所用到的條件式，程式是邊讀入資料邊判斷的。
函式 - 讀牌
1.花色有兩種以上就不可能是同花或同花順。
2.數字大小有重複就不可能是順子和烏龍。
3.如果需要用到pair2就不可能是一對。
4.葫蘆和兩對的分別在於three這個bool值。
5.葫蘆和兩對是可以在讀到第五張牌就馬上可以判斷的，其餘牌型需要在做進一步判斷。

函式 - 確定牌型
6.如果不是葫蘆，就做進一步判斷。
7.如果可能是同花，只有同花和同花順這兩種可能。
8.如果可能是烏龍，只有順子和烏龍這兩種可能。
9.如果是兩對要把數字較大的對指定給pair1，較小的對存在pair2。
10.如果不是兩對也不是一對，只可能是四條或三條。四條只有兩個數字，三條有三個數
字。

函式 - 兩人手牌比較大小
11.兩人牌型不同，就可以判斷輸贏。否則就是牌型相同來比較數字。
12.葫蘆的第一對和第二對的大小都一樣。否則比pair1，相等再比pair2。
13.不是葫蘆，但可能是同花順，順子，同花或烏龍，比較數字大小。
14.如果是三條或四條，比較pair1，再比廢牌。
15.如果是一對，比較pair1，再比廢牌。
16.如果是兩對，比較pair1，再比pair2，再比廢牌。

以上條件判斷式看似都是廢話，
但要將其組合起來並避免冗餘，需要一定邏輯能力加上頭腦清晰。

以下就是實作的程式碼，僅供參考。
http://codepad.org/HQoUYFgf

至於速度上，原本的0.000s，現在的0.008s。
扣除UVa那裡精準度的調整，我只能說測資太少以至於無法分出勝負。
但我相信以位元運算應該可以比較快。

最後，我不想保證這個程式100%運作正確。
但可以通過UVa的所有測資，相信具有一定程度的正確性。
同時，由於對於位元運算來比較撲克牌大小是第一次經驗，
程式應該可以再精簡，有興趣的人請自行修改。


Bleed

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.117.3
推 ilovebbs:推~