ps怎样做网站设计,做执法设备有哪些网站,网站制作语言,广告公司名称创意思路#xff1a;也算典型的dfs#xff0c;题目就是要求从n个数中选择k个数#xff0c;计算这k个数的和#xff0c;看这个和是否是素数。我们知道在dfs时相当于是进行全排列#xff0c;而结果要求的是组合后和的情况。根据排列和组合的关系#xff0c;他们之间差K#xf…思路也算典型的dfs题目就是要求从n个数中选择k个数计算这k个数的和看这个和是否是素数。我们知道在dfs时相当于是进行全排列而结果要求的是组合后和的情况。根据排列和组合的关系他们之间差K倍所以需要在dfs求得个数cnt后除以k。
题目 AC代码
#includealgorithm
#includeiostream
#includecstring
#includequeue
#includealgorithm
#includecmath
using namespace std;//输入nk从n个数中选k个数
int n,k;
int a[25];//记录n个数
int path[25];//记录选择的k个数
bool vis[25];//记录n个数的状态
int cnt 0;
int ss1;void dfs(int u){if(u k)//如果有k个数了{int sum0;for(int i0;ik;i){ sumpath[i];}// printf(summ%d\n,sum);//1不是素数 for(int i2;isqrt(sum);i){if(sum % i 0){return ;}}cnt;return;} //要确保每种搭配方式只出现一次for(int i0;in;i){if(!vis[i])//如果这个数没用{vis[i] true;path[u] a[i];dfs(u1);vis[i] false;path[u] 0;} }return ;
}
int main()
{scanf(%d%d,n,k);for(int i0;in;i){scanf(%d,a[i]);} for(int i1;ik;i){ss * i;// coutssendl; } dfs(0);printf(%d,cnt/ss);return 0;
} 结果
