欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++牌型种数题解

程序员文章站 2022-04-19 15:55:02
题目: 牌型种数 小明被劫持到X赌城,*与其他3人玩牌。 一副扑克牌(去掉大小王牌,共52张),均匀发给4个人,每个人13张。 这时,小明脑子里突然冒出一个问题:...

题目:

牌型种数

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

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

思路:1.一开始想的是直接求53张牌的全排列然后截取前13张排序后存入set,最后输出set元素个数,但这个要算好久,然后试了下深搜,还是要算好久,调试后发现是因为有好多都是可以算成一组的,只是位置不同,所有最后加了个判断,是生成的数组严格升序,不然不继续搜索,这样速度就很快了。 2.可以直接13重循环,没个元素4张,只要张数总数为13就算一种。

答案:3598180

代码1(推荐的方法):

// 牌型种数
#include 
using namespace std;

int an[13];
int res[13];
int visited[13];
set sset;

long cnt(0);

void init()
{
    for(int i=0;i<13;++i) an[i]=i+1;

    memset(visited,0,sizeof(int)*13);
}


void f(int m)
{
    if(m==0) {
        cnt += 1;
        return ;
    }else {
        for(int i=0;i<13;++i) {
            if(visited[i]<4){
                res[13-m]=an[i];
                // 这个判断很重要,避免重复排列,不然要算好久 
                if(res[13-m]代码2(循环,简单直接,但是速度没有上面深搜快):
#include  
using namespace std;  

int main()  
{  
    int a[13],cnt(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)  
                                                        {  
                                                            cnt += 1;  
                                                        }  
                                                    }  
                                                }  
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  

    cout << cnt << endl;


    return 0;  
}

代码3(最初的思路,过于暴力,算不出来,要算好久)

// 牌型种数
#include 
using namespace std;

int an[52];
set sset;

void init()
{
    for(int i=0;i<4;++i) {
        for(int j=0;j<13;++j) {
            an[13*i+j] = j+1; 
        }
    }

}

string a2s()
{
    // 截取前13张牌
    ostringstream ostr;
    sort(an,an+13);
    for(int i=0;i<13;++i) ostr << an[i];
    return ostr.str(); 
}

int main()
{


    long cnt(0);

    string ts;
    do {
        ts = a2s();
        sset.insert(ts);
    }while(next_permutation(an,an+52));

    cnt = sset.size();

    cout << cnt << endl;

    return 0;
} 
[12-m]&&res[12-m]!=0)>