小明被劫持到X赌城,被迫与其他3人玩牌。
一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。
这时,小明脑子里突然冒出一个问题:
如果不考虑花色,只考虑点数,也不考虑自己得到的牌的先后顺序,自己手里能拿到的初始牌型组合一共有多少种呢?请填写该整数,不要填写任何多余的内容或说明文字。
思路:
使用DFS来模拟抓牌的过程。
cur:抓牌次数(递归深度)此处范围为(1~13)分别代表(A~K)十三张牌
sum:抓的总牌数
i:每次抓的牌数(分别为0~4)就是对于当前cur指定的牌可选择一张不抓,也可选择四张全要。
cnt:用来记录有效的组合。
退出递归条件:
1.当前sum已经超过十三张牌(此时终止,避免多跑无用的递归)。
2.当前cur达到13(表示已经遍历了一遍(A~K))(此时如果sum为13则为正确解,cnt++)。
下面给出cpp代码:
#include "cstdio"
int cnt = 0;
void dfs(int cur,int sum)
{
if(sum > 13)
{
return;
}
if(cur == 13)
{
if(sum == 13)
{
cnt++;
}
return;
}
for(int i=0; i<=4; i++)
{
dfs(cur+1,sum+i);
}
}
int main()
{
dfs(0,0);
printf("%d", cnt);
return 0;
}
运行结果:
3598180