题目描述
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,4 个整数分别为 3,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29)。
输入描述:
输入格式为:
输出描述:
输出格式为:一个整数(满足条件的种数)。
示例1
输入
4 3
3 7 12 19
输出
1
解答
这道题思路简单,但实现起来却遇到了问题。我不知道怎么把每一种情况都遍历一遍,在网上查看代码,发现都是用dfs来做的。在此写下自己的一点理解,加深dfs的学习。
本题的两个知识点
(1)选数(从n中选出k个)
void dfs(int t,int sum,int l){ if(t==k) {if(sum为素数)ans++;} else for(int i = l;i<=n;i++) dfs(t+1,s+a[i],i+1); }
其中t从0开始到t-1 为t个数所以当t==k是已经了k个数
l参数是为了避免一个数多次选择
dfs的运用值得学习
(2)判断素数
判断素数可以用遍历的手段,也可以先将[2,3000]之间的素数保存在数组中提高效率
bool ss(int x){ if(x == 1||x == 0)return 0; for(int i = 2; i*i<x;i++) if(x%i==0)return 0; return 1; }代码:
#include <iostream> #include <sstream> #include <ios> #include <iomanip> #include <functional> #include <algorithm> #include <vector> #include <string> #include <list> #include <queue> #include <deque> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <climits> #include <cctype> using namespace std; #define XINF INT_MAX #define INF 0x3FFFFFFF #define MP(X,Y) make_pair(X,Y) #define PB(X) push_back(X) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define DEP(X,R,L) for(int X=R;X>=L;X--) #define CLR(A,X) memset(A,X,sizeof(A)) #define IT iterator typedef long long ll; typedef pair<int,int> PII; typedef vector<PII> VII; typedef vector<int> VI; //const int MAXN = 10010; //#define INF 0x3FFFFFFF int a[22],ans = 0; int n,k; bool ss(int x){ if(x == 1||x == 0) return 0; for(int i = 2;i*i<=x;i++) if(x%i == 0)return 0; return 1; } void dfs(int t,int sum,int l){ if(t == k){if(ss(sum))ans++;} else for(int i = l;i<=n;i++) dfs(t+1,sum + a[i],i+1); } int main() { cin>>n>>k; for(int i = 1;i <= n;i++)cin>>a[i]; dfs(0,0,1); cout<<ans<<endl; return 0; }
来源:xiaohuihuicb