典型的dfs,建议书写递归代码时层次应与形参列表中自己所标志的层次相对应,否则很容易混乱
import java.util.Scanner;
public class P1036 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int k = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
dfs(arr, k, 1, arr[i], i);
}
System.out.println(num);
}
static int num = 0;// 质数的个数 java中的全局变量
/**
* @param arr 存放数据的数组
* @param k 挑选 k 个整数
* @param count 表示递归层数,也就是选择数据的个数
* @param sum 表示上层递归所选数字之和与此层所选数字之和
* @param index 所选数字索引
*/
private static void dfs(int[] arr, int k, int count, int sum, int index) {
if (count == k) {
if (isPrime(sum)) {
num++;
}
return;
}
for (int i = index + 1; i < arr.length; i++) {
dfs(arr, k, count + 1, sum + arr[i], i);
}
}
/**
* 判断一个数是否为质数
*
* @param n 待判断数字
* @return 是质数返回 true 否则返回 false
*/
public static boolean isPrime(int n) {
if (n == 1) {
return false;
}
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
所涉及到的还有质数筛的内容
标签:arr,return,int,质数,P1036,param,++,洛谷 From: https://www.cnblogs.com/ChuenSan/p/17178599.html测试案例:
4 3
10 11 12 13
0