我以前用過的一個洗牌算法

前兩天和幾個做在線棋牌游戲的朋友聚會，聊到了洗牌算法，正好以前寫過一些撲克牌的游戲，中間做了一個洗牌算法，就寫了個例子給他們做試驗。 基本思路很簡單，就是交換法，54張牌排好，隨機選擇兩張牌交換，一般說來，只要交換次數足夠多，比如54張牌就交換54次，牌就已經洗得很爛了，呵呵，可以打牌了。如果還不放心，那double，洗108次好了。 程序還是比較簡單的，大家應該一目了然，我花了差不多半個小時左右寫出來，又測試了一下。 Code:

1. #define POKER_MAX 54            //54張撲克   
2. #define POKER_COLOR_MAX 4       //四種主花色   
3. #define POKER_POINT_MAX 13      //每種花色13張牌，J=11，Q=12，K=13   
4.   
5. #define POKER_COLOR_KING    4   //王的花色   
6. #define POKER_COLOR_0       0   //黑桃花色   
7. #define POKER_COLOR_1       1   //紅桃花色   
8. #define POKER_COLOR_2       2   //櫻花花色   
9. #define POKER_COLOR_3       3   //方塊花色   
10.   
11. #define POKER_KING_POINT_BIG    1   //大王的點數   
12. #define POKER_KING_POINT_LITTLE 0   //小王的點數   
13.   
14.   
15. typedef struct _POKER_CARD_   
16. {   
17.     short m_sID;        //全序列排列時的ID(0~53)   
18.     char m_cColor;      //撲克花色   
19.     char m_cPoint;      //撲克點數   
20. }SCard;   
21. const unsigned long SCardSize=sizeof(SCard);   
22. class CPoker   
23. {   
24. public:   
25.     CPoker()   
26.     {   
27.         //先整齊排列54張牌，按黑紅櫻方順序，每種花色按0~12順序   
28.         int i=0;   
29.         int j=0;   
30.         int nIndex=0;   
31.         for(i=0;i<POKER_COLOR_MAX;i++)   
32.         {   
33.             for(j=0;j<POKER_POINT_MAX;j++)   
34.             {   
35.                 SetPokerInfo(i,j,nIndex);   
36.                 nIndex++;   
37.             }   
38.         }   
39.         //王放在最後兩張   
40.         SetPokerInfo(POKER_COLOR_KING,POKER_KING_POINT_LITTLE,nIndex);  //小王   
41.         nIndex++;   
42.         SetPokerInfo(POKER_COLOR_KING,POKER_KING_POINT_BIG,nIndex); //大王   
43.     }   
44.     ~CPoker(){}   
45.     //一般說來，按牌總數決定洗牌次數，已經洗得很爛了   
46.     void Wash(int nTime=POKER_MAX)   
47.     {   
48.         int i=0;   
49.         for(i=0;i<nTime;i++)   
50.             Random();   
51.     }   
52.     //實際的游戲，從此處取洗好的牌張數據   
53.     bool Get(unsigned int nIndex,SCard* pCard)   
54.     {   
55.         if(POKER_MAX<=nIndex) return false;   
56.         memcpy((char*)pCard,(char*)&m_Poker[nIndex],SCardSize);   
57.         return true;   
58.     }   
59.     void PrintInfo(void)   
60.     {   
61.         int i=0;   
62.         SCard Card;   
63.         for(i=0;i<POKER_MAX;i++)   
64.         {   
65.             if(Get(i,&Card))   
66.             {   
67.                 printf("%02d - ID=%02d, Color=%d, Point=%02d\n",   
68.                     i,Card.m_sID,Card.m_cColor,Card.m_cPoint);   
69.             }   
70.         }   
71.         printf("===============\n");   
72.     }   
73. private:   
74.     //給sID指定的牌張賦值   
75.     void SetPokerInfo(char cColor,char cPoint,short sID)   
76.     {   
77.         m_Poker[sID].m_cColor=cColor;   
78.         m_Poker[sID].m_cPoint=cPoint;   
79.         m_Poker[sID].m_sID=sID;   
80.     }   
81.     //交換兩張牌   
82.     void Exchange(int a,int b)   
83.     {   
84.         char szTemp[SCardSize];   
85.         memcpy(szTemp,(char*)&m_Poker[a],SCardSize);   
86.         memcpy((char*)&m_Poker[a],(char*)&m_Poker[b],SCardSize);   
87.         memcpy((char*)&m_Poker[b],szTemp,SCardSize);   
88.     }   
89.     //隨機選取兩張牌張交換洗牌   
90.     //如果隨機數相等，發生碰撞，則b=a+1，總之不一樣就可以了。   
91.     void Random(void)   
92.     {   
93.         int a=GetRandomBetween(0,POKER_MAX);   
94.         int b=GetRandomBetween(0,POKER_MAX);   
95.         if(a==b)   
96.         {   
97.             b=a+1;   
98.             if(POKER_MAX<=b) b=0;   
99.         }   
100.         Exchange(a,b);   
101.     }   
102. private:   
103.     SCard m_Poker[POKER_MAX];   
104. };  

其實主要就是Wash這個函數，默認是洗54遍，當然，調用者如果高興，多洗幾遍也沒問題，呵呵。 用Get函數拿指定的撲克張子來用。 我試了一下，沒什麼問題，呵呵，刺激一下大家哈，從我測試代碼看，又是0bug。 不過，這段代碼有個問題，就是不是多線程安全的，起碼，一個線程洗牌，另外一個線程拿牌，會出錯。所以，我根據《0bug-C/C++商用工程之道》裡面的“資源鎖”概念，又封裝了一個加鎖的線程安全版。 Code:

1. class CPokerWithLock   
2. {   
3. public:   
4.     CPokerWithLock(){}   
5.     ~CPokerWithLock(){}   
6.     void Wash(int nTime=POKER_MAX)   
7.     {   
8.         m_Lock.Lock();   
9.             m_Poker.Wash(nTime);   
10.         m_Lock.Unlock();   
11.     }   
12.     bool Get(unsigned int nIndex,SCard* pCard)   
13.     {   
14.         bool bRet=false;   
15.         m_Lock.Lock();   
16.             bRet=m_Poker.Get(nIndex,pCard);   
17.         m_Lock.Unlock();   
18.         return bRet;   
19.     }   
20.     void PrintInfo(void)   
21.     {   
22.         m_Lock.Lock();   
23.             m_Poker.PrintInfo();   
24.         m_Lock.Unlock();   
25.     }   
26. private:   
27.     CPoker m_Poker;     //"資源鎖"概念，私有聚合，所有公有方法加鎖，確保安全性   
28.     CMutexLock m_Lock;  //這是《0bug-C/C++商用工程之道》裡面的跨平台安全鎖，見6.2小節，P226頁   
29. };  

嗯，這個加鎖版本不是必須的，只有當多線程環境時才需要。CMutexLock這個類我這裡就懶得提供了，有書的朋友，自己去查書吧。 嗯，最後，給段測試代碼，大家可以看看效果。 Code:

1. inline void TestCPoker(void)   
2. {   
3.     CPokerWithLock Poker;   
4.     srand((unsigned int)time(NULL));   
5.     Poker.PrintInfo();   
6.     Poker.Wash();   
7.     Poker.PrintInfo();   
8.     Poker.Wash();   
9.     Poker.PrintInfo();   
10. }  

上述代碼在VS2008下測試成功。有興趣的朋友，可以自己試試。嗯，如果沒有書的朋友，CPokerWithLock Poker;這句話可以改為CPoker Poker;，直接用非線程安全版本就好了。 大家看看，有什麼問題歡迎討論哈。 =======================================================
在線底價購買《0bug-C/C++商用工程之道》
直接點擊下面鏈接或拷貝到浏覽器地址欄）
http://s.click.taobao.com/t_3?&p=mm_13866629_0_0&n=23&l=http%3A%2F%2Fsearch8.taobao.com%2Fbrowse%2F0%2Fn-g%2Corvv64tborsvwmjvgawdkmbqgboq---g%2Cgaqge5lhebbs6qzlfmqmttgtyo42jm6m22xllqa-------------1%2C2%2C3%2C4%2C5%2C6%2C7%2C8%2C9%2C10%2C11%2C12%2C13%2C14%2C15%2C16%2C17%2C18%2C19%2C20---40--coefp-0-all-0.htm%3Fpid%3Dmm_13866629_0_0 肖舸
 

本文出自 “肖舸的blog” 博客，請務必保留此出處http://tonyxiaohome.blog.51cto.com/925273/302220