纸老虎数据

#include<iostream>
using namespace std;
int n,k,sum=0;
int a[25];
void dfs(int x,int t,int su)
{
    if(t==k)
    {
        for(int i=2;i*i<=su;i++)
        {
            if(i!=su && su%i==0)
            {
                return;
            }
        }
        sum++;
    }
    for(int i=x+1;i<=n;i++)
    {
        dfs(i,t+1,su+a[i]);
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dfs(0,0,0);
    cout<<sum;
    return 0;
}

题意

从n个数中选出k个，求里面有多少组和为素数。

思路

我一开始看到这道题目是懵的……

然后我自己手枚了一下，然后试图用电脑模拟过程……

（惊讶）然后就过了？？？

首先，我们是不是先找一个数，作为第一个？

然后找第二个，第三个……

一直到第k个，然后求和？

我就在想，那是不是可以将你数到的第t个数a[x]（出于习惯，我把题目中的x数列改成a数组了）往后数，枚举每一个第t+1个数的情况？

然后当t==k（也就是数完k个数了），就求和判断。

好问题，那如何标记是否使用a[x]了呢？

我就用了一个bool数组，1就是使用了，0就是没有使用。

算出来判断。

然后用一个全局的ans算总数。

解决！

（小声）题目不难，想说明白还真不一定……

陈老师！我知道你在看题解！明天讲题选我选我就选我！（可怜巴巴）

代码

#include<iostream>
using namespace std;
int n(0);
int k(0);
int a[30]{};//题目中的x数列 
bool f[30]{};//标记此数有没有使用 
int ans(0);//总个数 
int main(){
	void dfs(int,int);//搜索函数 
	cin>>n>>k;
	for(int i(1);i<=n;i++)
		cin>>a[i];
	dfs(0,0);
	cout<<ans;
	return 0;
}
void dfs(int t/*用了多少个*/,int x/*用到多少个*/){
	bool p(int);//判断是否为素数 
	if(t==k){//加了k个数了 
		int sum(0);//和 
		for(int i(1);i<=n;i++)
			if(f[i])//如果这个数被加了 
				sum+=a[i];
		if(p(sum))//如果和为素数 
			ans++;
	}
	else{
		if(x==n)//到头了 
			return;
		for(int i(x+1);i<=n;i++){
			f[i]=1;
			dfs(t+1,i);//搜索 
			f[i]=0;//回溯 
		}
	}
}
bool p(int x){
	for(int i(2);i<x;i++)
		if(!(x%i))
			return 0;
	return 1;
}

42小代码……

提醒

要回溯哦……