【牌型种数】第六届蓝桥杯省赛C/C++大学A组（递归剪枝）

蔚落 2022-11-26 11:55 126阅读 0赞

【问题描述】  
  小明被劫持到X赌城，被迫与其他3人玩牌。一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。  
  这时，小明脑子里突然冒出一个问题：如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？  
  请填写该整数，不要填写任何多余的内容或说明文字。

思路分析：这道题有两种思路可做：

1.  一共要选13张牌。**第一次选好一张牌，然后递归进入下一张牌的选择，我们每次选择都已经知道先前选择了哪些牌，当前选择牌时依次遍历13张牌，如果有的牌已经出现了四次那就跳过，否则就选该张牌然后进入下一次遍历。另外我们要回溯，因为不止一种可能，回溯就是把刚刚选中的牌给去掉，从不同方向去试探，进而找到所有可能。** 问题规模大概是 1 3 13 13^\{13\} 1313次方，基本无解。
2.  我们每一张牌都有可能都有五种可能，没被选上，以及选中1234次，那么我们就可以逐一去考虑每一种牌都有几张。当我们考虑完了13种牌并且一共也刚好选取了13张牌，我们就结束。问题规模大概 5 13 5^\{13\} 513，可以接受。

代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int ans = 0;
    
    //k表示总选了几种牌，cnt表示当前在抽取第几张牌 
    void solve(int k, int cnt) { 
    	//有可能前几种牌都选了4张，这样牌总数很容易超过13张，并不合理 
    	if(cnt > 13 || k > 13) { 
    		return ;
    	}
    	//solve(13, 13)表明已经选够13张，并且考虑了13张牌（有的牌可能一张没选） 
    	if(k == 13 && cnt == 13) { 
    		ans++;
    		return ;
    	}
    	//每一种牌都有五种可能 
    	for(int i = 0; i < 5; i++) { 
    		solve(k + 1, cnt + i);
    	}
    }
    
    int main() { 
    	solve(0, 0);
    	cout << ans;
    	return 0;
    }

答案：3598180