Freddy's Blog

[问题描述]:


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

[输出]：
格式为：一个整数（满足条件的种数）。
 
[输入输出样例]:
输入：choose.in
4 3
3 7 12 19
输出：choose.out
1

【分析】
排列組合問題，直接深度優先搜索（遞歸）即可。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int sum=0;//當前總和
int num[21];
int n,k;
int tot=0;

bool prime(int num)
{
	if (num==1)return false;
	for (int i=2;i<=(int)sqrt(double(num));i++)
		if (num%i==0)
			return false;
	return true;	
}


void dg(int dep,int loc)
{
	if(k-dep>n-loc) return;
	if (dep==k+1)
	{
		if (prime(sum))
			tot++;
	}
	if (dep<k+1)
	{
		for (int i=loc;i<=n;i++)
		{
			sum+=num[i];
			dg(dep+1,i+1);
			sum-=num[i];
		}
	}
}

int main()
{
	freopen("choose.in","r",stdin);
	freopen("choose.out","w",stdout);
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		cin>>num[i];
	dg(1,1);
	cout<<tot<<endl;
	return 0;
}

正在连接评测机...

已连接到评测机

正在编译...

编译成功

运行完成

运行时间 0.028 s

平均内存使用 275 KB

测试点通过状况 AAAAA

得分：100

恭喜你通过了全部测试点!