锐客网

  1. 首页 > it技术 > >

算法|回溯算法——洛谷p1036

算法javaleetcode回溯

//判断质数 static boolean isPrime(int num){ if (num == 0||num==1) return false; if (num == 2 || num == 3) return true; if (num % 6 != 1 && num % 6 != 5) return false; int end = (int) Math.pow(num,1.0/2 ); for (int i = 5; i <= end; i += 6) { if (num % i == 0 || num % (i + 2) == 0) return false; } return true; } static void rcs(List sum,List list,int k,int idx,int[] arr){ if(list.size()==k+1){ sum.add(list.get(0)); //加入k个数后,将和加入sum }else { //从idx开始为本层所能取的数,遍历添加 for (int i = idx; i < arr.length; i++) { list.add(arr[i]); list.set(0,list.get(0)+arr[i]); //修改组合的和 rcs(sum,list,k,i+1,arr); list.set(0,list.get(0)-arr[i]); //还原初始状态,再添加下一个 list.remove(list.size()-1); } } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); int[] arr=new int[n]; for (int i = 0; i < n; i++) { arr[i]=sc.nextInt(); } List sum=new ArrayList<>(); //存储每种组合的和 List list=new ArrayList<>(); //存储组合 list.add(0); //第一个数为组合的和 rcs(sum,list,k,0,arr); //回溯 int ans=0; for (int i = 0; i < sum.size(); i++) { if(isPrime(sum.get(i))) ans++; } System.out.println(ans); }

【算法|回溯算法——洛谷p1036】

    推荐阅读


    上一篇：算法练习|第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组（第一场真题 + 部分题解）

    下一篇：2021第十二届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组