问
  • 板块学术版
  • 楼主_XxIiAaOo_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/30 16:59
  • 上次更新2023/11/3 00:19:49
查看原帖
问
1057210
_XxIiAaOo_楼主2023/8/30 16:59

这个代码有用到回溯吗

#include<bits/stdc++.h>
using namespace std;

int n,m,a[20],b[20],num = 0,ans = 0;

bool Prime(int n){
	if(n <= 1){
		return false;
	}
	for(int i=2;i*i<=n;i++){
		if(n%i == 0){
			return false;
		}
	}
	return true;
}
void dfs(int cnt,int dep){
	if(dep > n){
		if(cnt == m){
			num = 0;
			for(int i=0;i<cnt;i++){
				num += b[i];
			}
			if(Prime(num)){
				ans++;
			}
		}
		return ;
	}
	b[cnt] = a[dep];
	dfs(cnt+1,dep+1);
	dfs(cnt,dep+1);
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(0,1);
	cout<<ans;
	return 0;
}

给出n个数,输出从中选m个数使得m个数的和为质数的方案有多少种

2023/8/30 16:59
加载中...