(2015)第六届蓝桥杯省赛(软件类) C/C++ 大学A组 题解(第六题)

时间:2022-09-09 21:39:08

第六题 

题目

牌型种数

小明被劫持到X赌城,*与其他3人玩牌。
一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。
这时,小明脑子里突然冒出一个问题:
如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?

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

分析

本题的题目理解清楚了,题目才好做。题意简述一下:

因为不区分花色,只区分点数。所以52张牌共13种类型。而发到每个人手上一定有13张牌,所以他们每人手里能拿到的初始牌型组合无非就是从13种类型的52张牌里面抽出13张,因此,编号1~13的牌每种类型的取值范围是0~4,表示能取到0~4张牌。

方法1:所:13种牌,每种牌取法从0~4遍历一次,答案就出来了。可以说是暴力中的暴力法了。

方法2:当然也可以运用DFS暴力递归的回溯策略。

代码


#include <iostream>
#include<cstring>
using namespace std;

int a[13];//0~12共13种牌,a[i]表示类型为i的牌取了几张,每种类型取值范围:0~4张 

int main(int argc, char** argv) {
	memset(a,0,sizeof(a));
	int count=0;
            for(a[0]=0; a[0]<=4; a[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]++)
                                                            {
                                                                if(a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]+a[9]+a[10]+a[11]+a[12]==13)
                                                                {
                                                                    count++;
                                                                }
                                                            }
                                                        }
                                                    }
                                                }
                                            }
                                        }
                                    }
                                }    
                            }
                        }
                    }
                }
            }
    printf("%d",count);
	return 0;
}

运行结果

用了4.916s

(2015)第六届蓝桥杯省赛(软件类) C/C++ 大学A组 题解(第六题)

———————————————————华丽的分割线—————————————————

更高效的方法:DFS深搜回溯法

分析

运用DFS递归的回溯策略。main中dfs(1),即表示从第1张牌开始搜索,也就是搜索树的层数从1开始。

dfs深搜每进入下一层表示,手中牌的种类多了一种。牌数种类每增加一种,需要从0~4循环遍历,同步更新手中每张牌的牌数,

用sum来表示当前手中牌的总数,当搜索到底14层(无这一层),判断sum==13,如若是的话,这样就得到了一种组合数。ans++,记录可行的组合数。

代码



#include <iostream>

using namespace std;
int ans=0;//牌的类型组合数 
int sum=0;//每个人手里有几张牌 
//给所有的牌编号为1~13 
void dfs(int n){//n可以理解为搜索树的层数,也就是第n种牌要sum张 
	if(sum>13){
		return;
	}
	if(n==14){
		if(sum==13){//手中集齐了13张牌 
			ans++;
			return;
		}
	}
	else{
		for(int i=0;i<=4;i++){//每种类型牌的张数从0~4遍历 
			sum+=i;//手里的牌数的增加 
			dfs(n+1);//搜索进入下一层,下一种牌要几张 
			sum-=i;//回溯还原 
		}
	}
	
	
}
int main(int argc, char** argv) {
	dfs(1);//从编号为1的牌开始搜索 
	printf("%d",ans);
	return 0;
}

运行结果

用了0.2589s

(2015)第六届蓝桥杯省赛(软件类) C/C++ 大学A组 题解(第六题)