抽签 递归【蓝桥杯真题】(c++实现)

抽签

X星球要派出一个5人组成的观察团前往W星。

其中:

A国最多可以派出4人
A国最多可以派出4人
A国最多可以派出4人
。。。

那么最终派往W星的观察团会有多少种国别的不同组合呢?

输入格式
第一行N,以下N行代表N个国家最多可派出人数Ai。
输出格式
最多多少种派法ANS,ANS为一个整数。
输出规模
1<N<10000
1<AI<10000
示例输入
6
4
2
2
1
1
3
示例输出
101

我的思路

  • 本题思路理解:X星球N个国家,每个国家都可以派出人数,但是不能派出大于最多人数的人数并且不能派出大于5的数,求所有国家按此规范派出人数会产生多少种组合。
  • 可以使用暴力破解判断所有组合,然而比赛时需要节省时间,所以使用递归(本题参考蓝桥学苑2016届B组试题,个人检查无误,本地运行有误)。

算法展示

#include <iostream>
using namespace std;
int a[10000],N,i,ans = 0;
void findAns(int a[],int start,int An)//国家可派出数组a,当前派出第start国家,已经组合An人 
{
    if(start == N)//找到最后一个国家后 
    {
        if(An == 5) ans++;//如果组合人数An等于派出人数5; 
        return;    
    }

    for(i = 0;i<=a[start];i++)//派出第n个国家人数的人数,需检查人数是否满足规范 
    {
        findAns(a,start+1,An+i);//查找下一个国家,记录已经组合数An
    }    
}
int main()
{
    //输入规模及数据 
    cin>>N;    
    for(i = 0;i < N;i++)
    {
        cin>>a[i];
    }
    findAns(a,0,0); 
    
    cout<<ans<<endl;
    return 0;
}

上文链接:凑算式 全排列 【蓝桥杯真题】(c++实现)

评论

暂无评论