社区讨论

c++卑微请求大佬好爸爸好妈妈看看我的dfs哪里出问题了,能编译但样例不过

P1036[NOIP 2002 普及组] 选数参与者 2已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo31lj7d
此快照首次捕获于
2023/10/23 23:18
2 年前
此快照最后确认于
2023/10/23 23:18
2 年前
查看原帖
C
#include<bits/stdc++.h>
using namespace std;
vector<int>book;
int t,z,x;
bool su(int a){
	int i;
	for( i=2;i<a;i++){
		if(a%i==0)
		return 0;
	}
	if(i==a)
	return 1;
}//判断和是否为素数,是素数则返回1 
void dfs(int cur,int k,int a[]){//cur为当前相加数字个数,k为要求k个数字相加,a[]为输入数字组成的数组 
	if(cur==k){//达到k个数相加,调用素数判断函数 
		if(su(z)){
		t++;//是素数则t计数器+1
		}
		z-=x;//减去上次加入的数字重置z 
		return;//退出递归,返回上一步 
	}
	for(int i=0;i<sizeof(a);i++){//从a数组第一个位置开始遍历到最后一个 
		if(book[a[i]==0]){//若a[i]未被访问过 
		z+=a[i];//计入和 
		x=a[i];//记录此时加入的数字 
		book[a[i]]=1;//标记a[i]已访问 
		dfs(cur+1,k,a);//进入dfs递归 
		book[a[i]]=0;//标记a[i]未访问	
		}
	}
}

int main(){
	int n,k;
	cin>>n>>k;//输入n个数字,要求选k个数字相加 
	t=0;//初始计数器为0 
	z=0;//初始和为0 
	book.assign(10086,0);//设置标记数字,元素皆为0 
	int a[n];//创建n个元素的a数组 
	for(int i=0;i<n;i++){
		cin>>a[i];
	}//输入n个数字 
	dfs(0,k,a);//调用dfs函数 
	cout<<t;//输出计数器的累计个数 
	return 0;
}

回复

6 条回复,欢迎继续交流。

正在加载回复...