本文主要是介绍P1036 [NOIP2002 普及组] 选数 | JAVA 题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题目
- 解题说明
- 代码
题目
解题说明
这道题涉及典型的搜索问题,这是一个组合问题,要学会使用DFS去解决组合问题,便是解决此问题的关键。
代码
代码如下(示例):
import java.util.Scanner;public class p1036_plus {private static int[] arr;private static int count;public static void main(String[] args) {Scanner sc=new Scanner(System.in);int n=sc.nextInt(),k=sc.nextInt();arr=new int[n];for (int i = 0; i <n ; i++) arr[i]=sc.nextInt();dfs(1,0,n,k,0);System.out.println(count);}static void dfs(int index,int start,int n,int k,int sum){if(index>k){if(isPrime(sum))count++;return;}for (int i = start; i <n ; i++) {dfs(index+1,i+1,n,k,sum+arr[i]);}}static boolean isPrime(int n){for (int i = 2; i <=Math.sqrt(n) ; i++)if(n%i==0) return false;return true;}
}
这篇关于P1036 [NOIP2002 普及组] 选数 | JAVA 题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!