第六屆藍橋杯個人省賽C語言A組第六題

牌型種數

小明被劫持到X賭城，被迫與其他3人玩牌。

一副撲克牌（去掉大小王牌，共52張），均勻發給4個人，每個人13張。

這時，小明腦子裡突然冒出一個問題：

如果不考慮花色，隻考慮點數，也不考慮自己得到的牌的先後順序，自己手裡能拿到的初始牌型組合一共有多少種呢？

請填寫該整數，不要填寫任何多餘的内容或說明文字。

答案：3598180

對于A,2,3…J、Q、K這13種牌，小明拿到每種牌的張數可能為0、1、2、3或4張牌。共有5的13次方(1 220 703 125)種可能性，但其中隻有每種牌張數總和為13的組合才為正确的組合，該組合數為3 598 180。

解法一

#include <iostream> 
#include <cstdio>
#include <cstring> 
#include <algorithm> 
#include <cctype> 
#include <vector> 
#include <cstdlib>

using namespace std; 

int main() 
{
int i[20]; 
    long long ans=0; 

    for(i[1]=0;i[1]<=4;i[1]++) 
        for(i[2]=0;i[2]<=4;i[2]++)
            for(i[3]=0;i[3]<=4;i[3]++)
                for(i[4]=0;i[4]<=4;i[4]++)
                    for(i[5]=0;i[5]<=4;i[5]++) 
                        for(i[6]=0;i[6]<=4;i[6]++) 
                            for(i[7]=0;i[7]<=4;i[7]++) 
                                for(i[8]=0;i[8]<=4;i[8]++) 
                                    for(i[9]=0;i[9]<=4;i[9]++) 
                                        for(i[10]=0;i[10]<=4;i[10]++) 
                                            for(i[11]=0;i[11]<=4;i[11]++) 
                                                for(i[12]=0;i[12]<=4;i[12]++) 
                                                    for(i[13]=0;i[13]<=4;i[13]++) 
                                                    {
                                                        int t=0; 
                                                        for(int j=1;j<=13;j++) 
                                                        { 
                                                            t+=i[j]; 
                                                        } 
                                                        if(t==13) 
                                                        {
                                                            ans++;
                                                        }
                                                    } 
    cout<<ans<<endl; 
    system("pause"); 
    return 0; 
}           

解法二

#include<iostream>

using namespace std;

void perm(int cur, int& ctr, int sum); 

int main()
{
    int ctr=0;
    int sum=0;

    perm(1,ctr,sum);

    cout<<ctr<<endl;

    return 0;
} 

/**
*cur為目前考慮到哪種牌，cur=1即考慮牌型為A的情況
*ctr統計正确的組合數
*sum統計目前牌的總數是否已經超過13，如超過則無需繼續考慮子節點
*/ 
void perm(int cur, int& ctr, int sum)
{
    if(sum>13)       
        return;
    if(cur==14)     //易錯點，要将K（第13張牌）考慮完，即cur=14 
    {
        if(sum==13) //易錯點，排除總和不為13的組合方式 
            ctr++;
    }
    else
    {
        for(int i=0; i<=4; i++)
        {
            sum+=i;
            perm(cur+1,ctr,sum);
            sum-=i;
        }
    }
}           

解法二的效率要明顯優于解法一的效率。