♐ CSP_J 组真题
2002年
2. 选数

线上OJ:

一本通:1919:【02NOIP普及组】选数 (opens in a new tab)
AcWing:5491. 选数 (opens in a new tab)
洛谷:P1036 [NOIP2002 普及组] 选数 (opens in a new tab)

核心思想:

1、使用 模板函数 isPrime() 来判断一个数是否为素数。
2、定义一个函数 dfs 来进行深度优先搜索。在dfs函数中,通过递归的方式遍历所有可能的组合,并计算每个组合的和。

如果坐标 id 超过n,则越界,返回。
如果已选了k个数,且和为素数,则 ans 加 1。
否则,就对剩余的 [id+1, n] 个数进行枚举深搜

判断素数的模板函数
bool isPrime(int a) 
{
	if(a < 2)  return false;
	for(int i = 2; i * i <= a; i++)
		if(a % i == 0)	return false;
	
	return true;
}

题解代码:

dfs深搜
#include <bits/stdc++.h>
using namespace std;
 
int n, k, ans;
int x[25];    
 
// 判断一个数是否为素数
bool isPrime(int a) 
{
	if(a < 2)  return false;
	for(int i = 2; i * i <= a; i++)
		if(a % i == 0)	return false;
	
	return true;
}
 
// (当前已选数的和,当前数的索引,已经选了几个数) 
void dfs(int sum, int id, int cnt) 
{
    if (id > n)  return;  // 如果传进来的数的索引已经超过了 n ,则越界,返回 
    else if (k == cnt && isPrime(sum))   // 否则,如果当前传进来已选的数已达到k个,且此时k个数的总和是素数 
        ans++;
    else   // 否则,继续向下深搜(此时,要枚举后续每一个元素) 
	{
        for (int i = id + 1; i <= n; i++)
            dfs(sum + x[i], i, cnt + 1);
    }
}
 
int main() 
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)   cin >> x[i];  // 存储的索引为 1~n 
 
    ans = 0;
    dfs(0, 0, 0);  // (当前已选数的和,当前数的索引,已经选了几个数) 
 
    printf("%d\n", ans);
    return 0;
}