2002NOIP普及组真题 2. 选数

线上OJ：

【02NOIP普及组】选数

核心思想：

1、使用 模板函数 isPrime() 来判断一个数是否为素数。
2、定义一个函数 dfs 来进行深度优先搜索。在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;
}

题解代码：

#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;
}