写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：P1036 [NOIP2002 普及组] 选数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述：
输入格式：
第一行两个空格隔开的整数 n , k（1 ≤ n ≤ 20，k < n）。
第二行 n 个整数，分别为 x1, x2, ⋯, xn（1 ≤ 5 × 1061 ≤ xi ≤ 5 × 106）。
输出格式：
输出一个整数，表示种类数。
输入样例： 4 3 3 7 12 19 输出样例： 1
解题思路：
我们使用深度优先搜索的时候，
第一个要注意的点是搜索的顺序，
因为我们要保证，
我们写出的递归结构能够遍历所有情况，
在我们初学搜索的时候，我们一定要画一个递归搜索树观察，
递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）
接下来是具体思路：
题目叫我们从n个数里面选k个相加，判断是否能成素数，
然后要我们输入那n个数，
那我们先画一下递归搜索树：
根节点：（以输入n=4, k=3, 输入数据：3,7,12,19）
我们根据每个位置能放什么数据的思路
往下递归搜索：
然后我们根据题目要求，
继续递归搜索，我们发现有些组合非法，需要剪枝：
我们继续递归搜索：
最后只剩四种组合合法，
我们再判断这四种组合是否相加为素数，
接下来，我们说一下剪枝，
如果该位置已经存放的数+剩余可选的数<需要的数量就剪枝。
下面是代码实现：
代码：
//养成好习惯，包上常用头文件 #include #include #include #include using namespace std; //根据题目要求开数组 const int N = 30; //arr数组用来读入数据 int arr[N]; //st数组用来存放数据 int st[N]; int n, k; //记录素数个数并返回 int res = 0; //判断是否是素数 bool is_prime(int sum) { if(sum < 2) { return false; } for(int i = 2; i <= sum / i; i++) { if(sum % i == 0) { return false; } } return true; } void dfs(int u, int start) { //如果：(已经存放的数 + 剩余可选的数 < 需要的数量)就剪枝 if((u - 1) + (n - start + 1) < k) { return; } if(u > k) { //求和 int sum = 0; for(int i = 1; i <= k; i++) { sum += st[i]; } //判断 if(is_prime(sum)) { res++; } return; } for(int i = start; i <= n; i++) { st[u] = arr[i]; dfs(u + 1, i + 1); st[i] = 0; } } int main() { scanf("%d %d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d", &arr[i]); } dfs(1, 1); printf("%d\n", res); return 0; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
之后我还会输出更多高质量内容，欢迎收看。
文章知识点与官方知识档案匹配，可进一步学习相关知识
