蓝桥杯 2015省赛 C/C++ A T6

知识点

递归

题目

牌型种数

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

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

思路

本题若考虑全排列，复杂度过高。考虑各点数牌选取的个数情况，即每个点数牌可能的选取个数为{0,1,2,3,4}，这样考虑复杂度为$5^{13}\approx1e9$，并且还有剪枝，运算时间可以接受。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <sstream>
using namespace std;

int ans = 0;

void f(int k,int cnt) // k表示考虑到哪种牌，cnt表示总共分配牌数
{
    if (cnt>13||k>13) return;
    if (k==13&&cnt==13)
    {
        ans++;
        return;
    }
    for (int i=0;i<5;i++)
        f(k+1,cnt+i);
}

int main()
{
    f(0,0);
    cout << ans << endl;
    return 0;
}

// 复杂度过高仅作为参考
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <sstream>
using namespace std;

string pai[13];
int ans = 0;

int countOf(vector<string> path, string p)
{
    int cnt = 0;
    for (int i = 0; i < path.size(); i++)
        if (path[i] == p)
            cnt++;
    return cnt;
}

void f(int k, vector<string> path)
{
    if (k == 0)
    {
        ans++;
    }

    for (int i = 0; i < 13; i++)
    {
        if (countOf(path, pai[i]) == 4)
            continue;
        path.push_back(pai[i]);
        f(k - 1, path);
        path.erase(path.end() - 1);
    }
}

void i2s(int num, string &str)
{
    stringstream ss;
    ss << num;
    ss >> str;
}

int main()
{
    for (int i = 1; i <= 13; i++)
        i2s(i, pai[i - 1]);
    vector<string> v;
    f(13, v);
    cout << ans << endl;
    return 0;
}