P1036 选数

题目链接

题目分析：
排列组合，将同一组中的所有数据相加得到一个新的数，这些数组成一个集合，统计集合中素数的个数。很明显暴力枚举所有情况，取的个数都不确定，当然不是写一堆循环啦！！！怎么枚举对于我们来说可能是个很大的问题。

循环不行那就肯定递归了，递归不需要确定循环的次数，只需要给出终止的条件即可，终止条件那肯定就是要取的个数与已取的个数相等或者是能取的个数超出了已有的个数，这样的话只能判断一种情况，因此我们需要回溯到前一个状态跳过执行终止条件的情况，取下一个数。递归执行遍历所有情况，判断这些数有多少个数为素数。(很经典的dfs)

判断素数的方法(数论)：根据数论理论可以把数字分成6个大部分，6i,6i+1,6i+2,6i+3,6i+4,6i+5，也就是说数字x%6计算的值一定是0,1,2,3,4,5这6个数字，而6i,6i+2,6i+3,6i+4一定就是合数，它们都有除了1之外的因数，只有6i+1和6i+5可能是素数，因而一旦判定数字大于等于且6取模结果为0,2,3,4就可以判定不是素数。(本题的话为了防止测数，我将1也作为素数)

对测试样例的分析(图比较乱????,将就看哈~):

AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[21],n,sum,k;
//n为数的个,k为取数的个数,数组a存储n个数,sum用来记录素数个数 
//判断素数 
int check(int temp) {
	if(temp==1||temp==2||temp==3) {
		return 1;
	} else if(temp%6!=1&&temp%6!=5) {
		return 0;
	}
	for(int i=5; i<=sqrt(temp); i+=6) {
		if(temp%i==0||temp%(i+2)==0) {
			return 0;
		}
	}
	return 1;
}
//深度优先遍历 
//参数：数组下标；取得数的和；取得数的个数 
void dfs(int x,int all,int count) {
	if(x==n+1||count==k) {
		if(count==k) {
			//cout<<all<<endl;
			sum+=check(all);
		}
	} else {
		dfs(x+1,all+a[x],count+1);
		dfs(x+1,all,count);
	}
}
int main() {
	cin>>n>>k;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	dfs(1,0,0);
	cout<<sum<<endl;
	return 0;
}