目錄
- 一、2個算法關鍵點
-
- 關鍵點1：洗牌算法
- 關鍵點2：查找同花順算法
- 二、運作結果
- 三、完整代碼
題目：
一張撲克牌可用結構類型描述，一副撲克牌的52張牌則是一個結構數組。
1、試編寫洗牌函數和供4人玩牌的發牌函數。
2、統計出現同花順的機率
提示：模拟發牌100000次（這個次數可用#define設定），程式最後統計如下資料
（1）出現同花順的總個數；
（2）出現同花順的發牌個數；
（3）發牌總次數；
（4）出現同花順的發牌機率。
所使用的結構：
struct card{
char shape; // 花色首字母，即’S’, ‘H’, ‘C’, 'D’四種
int value; // 牌的大小，從2開始,JQKA分别為11, 12, 13, 14
};
5張同花連号算同花順，連号規則為從2開始，到A結束。
如：7、8、9、10、J、Q、K隻能算作7~J一個同花順。
一、2個算法關鍵點
關鍵點1：洗牌算法
經典洗牌算法有很多，可以直接自行百度洗牌算法，了解一下不同的算法優劣。這裡采用一種複雜度較小的算法Knuth-Durstenfeld Shuffle算法（算法2），它是Fisher-Yates Shuffle算法（算法1）的改進版。
問題描述：将一個有N個元素有序數組a[N]亂序，即洗牌。
算法1核心：從原始數組裡随機抽取一個元素放在新的數組裡，再從原數組剩下的元素裡随機選一個元素依次放到新數組裡，如此循環，直到原始數組裡所有元素被抽取到新數組裡，完成亂序（洗牌）。
算法複雜度：時間複雜度O(N*N)，空間複雜度O(N)
優點：容易了解。
缺點：時間複雜度和空間複雜度都較大，抽取元素後還需在原數組中删去抽取掉的元素，較麻煩。
算法2核心：對算法1進行改進，不建立數組，而是在原數組内進行互換。從原始數組裡随機選一個元素，與最後一個元素a[N-1]互換。然後在除最後一個元素a[N-1]外的其他元素裡随機挑一個元素與倒數第二個元素a[N-2]互換。然後在除最後2個元素外的其他元素裡随機挑一個元素與倒數第三個元素a[N-3]互換…直到抽取完畢，完成亂序（洗牌）。
算法複雜度：時間複雜度O(N)，空間複雜度O(1)
優點：複雜度小，操作簡單。
缺點：需知道數組大小N（不過這點較容易克服）。
洗牌程式：
采用算法2，對長為5的結構化數組c[len]進行洗牌，其中num_time是為在快速循環中為srand函數賦予随機數種子用的（因為在快速循環中程式運作很快，time()傳回的時間秒數基本不變，若隻采用time(NULL)作為srand的随機數種子是遠遠不夠的）。
// 洗牌函數
// 算法：對于size為Num的數組array[Num]，len=Num。每次随機産生一個[0, len)的數字x，
// 将array[x]與數組尾端array[len-1]調換，然後len減1，重複操作。
// 複雜度：時間複雜度O(N)，空間複雜度O(1)
void Shuffle(struct card *c, int num_time)
{
int x, len = 52;
struct card temp;
// 初始化随機數種子
// srand((unsigned)time(NULL));
// 在循環中運算過快time可能不變，加上循環變量num_time保證随機數種子的不一樣。
srand((unsigned)time(NULL) + num_time);
while (len > 1)
{
x = rand() % len;
temp = c[len - 1];
c[len - 1] = c[x];
c[x] = temp;
len--;
}
}
關鍵點2：查找同花順算法
一種容易想到的算法是：
（1）發牌：洗牌後，按順序發給四個人，每人13張牌，假設某人領到的牌存在結構數組a0[13]裡。
（2）排序：先對a0[13]根據元素value值大小進行排序，冒泡、快排等算法均可，這裡因元素較少（13個）采用冒泡，若想更快可采用快排。先不分花色就進行排序，後續操作就不用排序了，可使得進一步的操作——分花色和查找順子更簡單。
（3）分花色：因不知各花色各有多少張牌，是以取最大值13,，定義4個大小為13的int型數組（C語言必須在定義數組時規定大小）。然後周遊排序後的a0[13]元素，按花色分到4個數組array裡，隻存value值，并注意儲存每個數組的元素個數。
（4）找順子：因為此人手中的13張牌按花色存到了4個int數組裡，是以問題變成了：在一個長為len的int數組array[len]裡查找5順子的個數。這裡可建立一個函數解決這個問題。
算法核心：先确認數組元素是否大于5，然後從array[0]到array[len-5]，确認每一個元素與其後4個元素構成公差為1的遞增等差數列（5連順子）。若出現一個順子，将下标元素變到目前順子後的第一個元素，在程式中為i+=4，因為i++還會再+1，是以是一共是+5。這樣就可以保證滿足題目中“7,8,9,10,J,Q,K中隻有 7~J一個順子”的要求。
（5）相加：分别計算此人4種花色數組裡的5連順子個數，并相加，即為此人手裡的同花順個數。同理，計算此次發牌後4人的同花順個數相加，即為此次發牌的同花順個數。
注意：
出現同花順個數和出現同花順的發牌次數并不相同，因為一次發牌可能有多個同花順出現。這裡的代碼運用了一個技巧，先統計每次發牌後同花順個數是否增加，若增加（改變）了，即證明此次發牌有同花順出現，出現同花順的發牌次數自增1即可。
if (Num_tong != Num_tong_org)
Num_tong_fa++;
二、運作結果
三、完整代碼
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 模拟發牌總次數
#define N 100000
// 統計個數
int Num_tong = 0; // 出現同花順個數
int Num_tong_fa = 0; // 出現同花順的發牌次數
double P_tong = 0.0; // 出現同花順的機率
// 牌的花色數組
char shapes[4] = { 'S', 'H', 'C', 'D' };
// 定義牌的結構體
struct card {
char shape;
int value;
};
// 4人各自的牌
struct card a0[13], a1[13], a2[13], a3[13];
// 初始化一副牌函數
void Init_cards(struct card *c)
{
int i, j;
for (i = 0; i < 13; i++)
{
c[4 * i].value = c[4 * i + 1].value = \
c[4 * i + 2].value = c[4 * i + 3].value = i + 2;
for (j = 0; j <= 3; j++)
{
c[4 * i + j].shape = shapes[j];
}
}
}
// 列印一副牌函數
void Print_cards(struct card *c, int len)
{
int i;
for (i = 0; i < len; i++)
{
printf("%2d: %2d %c\n", i, c[i].value, c[i].shape);
}
}
// 洗牌函數
// 算法：對于size為Num的數組array[Num]，len=Num。每次随機産生一個[0, len)的數字x，
// 将array[x]與數組尾端array[len-1]調換，然後len減1，重複操作。
// 複雜度：時間複雜度O(N)，空間複雜度O(1)
void Shuffle(struct card *c, int num_time)
{
int x, len = 52;
struct card temp;
// 初始化随機數種子
// srand((unsigned)time(NULL));
// 在循環中運算過快time可能不變，加上循環變量num_time保證随機數種子的不一樣。
srand((unsigned)time(NULL) + num_time);
while (len > 1)
{
x = rand() % len;
temp = c[len - 1];
c[len - 1] = c[x];
c[x] = temp;
len--;
}
}
// 排序函數：将發到每個人手上的牌按大小排序，便于歸類花色
void Sort_cards(struct card *c, int len)
{
int i, j;
struct card temp;
for (i = len - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (c[j].value > c[j + 1].value)
{
temp = c[j + 1];
c[j + 1] = c[j];
c[j] = temp;
}
}
}
}
// 發牌函數：洗牌後，按循環給4個人發牌
void Deal(struct card *c)
{
int i;
// 給4人發牌
for (i = 0; i < 13; i++)
{
a0[i] = c[4 * i];
a1[i] = c[4 * i + 1];
a2[i] = c[4 * i + 2];
a3[i] = c[4 * i + 3];
}
// 給4人的牌排序，以便後續分花色和查找同花順
Sort_cards(a0, 13);
Sort_cards(a1, 13);
Sort_cards(a2, 13);
Sort_cards(a3, 13);
}
// 列印數組
void Print_array(int *array, int len)
{
int i;
for (i = 0; i < len; i++)
{
printf("%d ", array[i]);
}
printf("\n");
}
// 數組同花順函數：判斷數組中是否含有同花順，傳回同花順個數
int Have_shunzi(int *array, int len)
{
int i, j;
int Num = 0, Num_org = 0;
if (len >= 5)
{
for (i = 0; i <= (len - 5); i++)
{
Num_org = Num;
for (j = i; j < i + 4; j++)
{
if (array[j + 1] == (array[j] + 1))
{
if (j == (i + 3))
{
Num++;
printf("%d %d %d %d %d\n", array[i], array[i + 1], array[i + 2], array[i + 3], array[i + 4]);
}
continue;
}
else break;
}
// 若出現同花順，将周遊下标調到後面第5個
if (Num_org != Num)
i += 4;
}
}
return Num;
}
// 結構體同花順函數：判斷某人的牌裡是否含有同花順，傳回同花順個數
int Find_cards(struct card *c, int len)
{
int i, j, k, l, m;
int array[4][13];
j = k = l = m = 0;
// 把某人手中的牌按花色分開
for (i = 0; i < len; i++)
{
if (c[i].shape == 'S')
{
array[0][j] = c[i].value;
j++;
}
else if (c[i].shape == 'H')
{
array[1][k] = c[i].value;
k++;
}
else if (c[i].shape == 'C')
{
array[2][l] = c[i].value;
l++;
}
else
{
array[3][m] = c[i].value;
m++;
}
}
// 統計各花色中出現同花順的個數
return Have_shunzi(array[0], j) + Have_shunzi(array[1], k) + Have_shunzi(array[2], l) + Have_shunzi(array[3], m);
}
// 主函數
int main(void)
{
int i;
int Num_tong_org = 0;
// 定義一副牌
struct card new_cards[52];
// 初始化牌
Init_cards(new_cards);
// 循環發牌N次，統計出現同花順的資料
for (i = 0; i < N; i++)
{
Num_tong_org = Num_tong;
Shuffle(new_cards, i);
Deal(new_cards);
Num_tong += Find_cards(a0, 13) + Find_cards(a1, 13) + Find_cards(a2, 13) + Find_cards(a3, 13);
if (Num_tong != Num_tong_org)
Num_tong_fa++;
}
// 計算出現同花順的發牌機率
P_tong = (double)Num_tong_fa / (double)N;
// 列印資訊
printf("\n");
printf("每次發牌結果資料過多，以上為出現的同花順情況。\n");
printf("\n");
printf("統計資料如下:\n");
printf("1、出現同花順的總個數: %d\n", Num_tong);
printf("2、出現同花順的發牌次數: %d\n", Num_tong_fa);
printf("3、發牌總次數: %d\n", N);
printf("4、出現同花順的發牌機率: %f\n", P_tong);
return 0;
}
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)