C++搜索与回溯算法之选数

选数

题目描述

已知 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。

输入

n,k （1≤n≤20，k＜n） x1,x2,...,xn（1≤<=xi≤<=5000000）

输出

一个整数（满足条件的种数）。

样例输入

4 3 3 7 12 19

样例输出

1

解题

  这道题相当于在n集合中k个数的全排列的基础上加上了判定素数了，但是不能把同一种排列调换顺序，并且不用输出所有排列方案。根据这种想法，我们可以很快写出代码，就像这样：

#include<cmath> #include<iostream> using namespace std; int n,k,x[21],num[21],cnt; bool check() { int sum=0; for(int i=1;i<=k;i++) sum+=num[i]; for(int i=2;i<=sqrt(sum);i++) if(sum%i==0) return 0; return 1; } void dfs(int a,int last) { for(int i=last;i<=n;i++) { num[a]=x[i]; if(a==k&&check()) cnt++; else dfs(a+1,i+1); } } int main() { cin>>n>>k; for(int i=1;i<=n;i++) cin>>x[i]; dfs(1,1); cout<<cnt; }

    但是，我们也可以省去num数组直接定义全局变量sum，在dfs的语句里直接用sum加上x[i]，这样省了计算总量的时间，也省了一个数组的空间，一举两得，代码如下：

#include<cmath> #include<iostream> using namespace std; int n,k,x[21],sum,cnt; bool check() { for(int i=2;i<=sqrt(sum);i++) if(sum%i==0) return 0; return 1; } void dfs(int a,int last) { for(int i=last;i<=n;i++) { sum+=x[i]; if(a==k&&check()) cnt++; dfs(a+1,i+1); sum-=x[i]; } } int main() { cin>>n>>k; for(int i=1;i<=n;i++) cin>>x[i]; dfs(1,1); cout<<cnt; } 怎么样，是不是简单多了？(～￣▽￣)～