蓝桥杯 2015_7 牌型种数-白红宇

蓝桥杯 2015_7 牌型种数

阅读量：4216 次

发布时间：2019-05-26

本文共 1676 字，大约阅读时间需要 5 分钟。

7、牌型种数

小明被劫持到X赌城，被迫与其他3人玩牌。

一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。

这时，小明脑子里突然冒出一个问题：

如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

请填写该整数，不要填写任何多余的内容或说明文字。

有13种牌型，每种可以是0、1、2、3、4张，5种可能。

思路1：暴力（大概5秒钟）

#include
   
    #include
    
     using namespace std;int a[14];int main()	{		int ans = 0;		for(a[1] = 0; a[1] <= 4; ++a[1]){			for(a[2] = 0; a[2] <= 4; ++a[2]){				for(a[3] = 0; a[3] <= 4; ++a[3]){					for(a[4] = 0; a[4] <= 4; ++a[4]){						for(a[5] = 0; a[5] <= 4; ++a[5]){							for(a[6] = 0; a[6] <= 4; ++a[6]){								for(a[7] = 0; a[7] <= 4; ++a[7]){									for(a[8] = 0; a[8] <= 4; ++a[8]) {										for(a[9] = 0; a[9] <= 4; ++a[9]){											for(a[10] = 0; a[10] <= 4; ++a[10]){												for(a[11] = 0; a[11] <= 4; ++a[11]){													for(a[12] = 0; a[12] <= 4; ++a[12]){														for(a[13] = 0; a[13] <= 4; ++a[13]){															if(a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]+a[13] == 13){																++ans;															}														}													}												}											}										}									}								}							}						}					}				}			}		}		printf("%d",ans);				return 0;	}

思路2：dfs + 剪枝

这里用了一个全局变量sum作为回溯用，省去了记录每个位置的数组并且可以以sum > 13 为条件进行剪枝

#include
   
    #include
    
     #include
     
      using namespace std;int ans;int sum;//bool judge(int *a){//	int sum = 0;//	for(int i = 1; i <=13; ++i ){//		sum += a[i];//	}//	return sum == 13;//}void dfs(int pos)	{		if(sum > 13)			return;		if(pos > 14)			return ;		if(pos == 14){			if(sum == 13)				++ans;			return ;		}		for(int i = 0; i <= 4; ++i){			sum += i; //表示取当前牌型 i张			dfs(pos+1);			sum -= i;//回溯		}	}int main()	{		ans = 0;		dfs(1);		printf("%d\n",ans);		return 0;	}