HDOJ 1016 Prime Ring Problem(DFS深度优先搜索)

HDACM 1016

此题采用 深搜+剪枝+递归 的办法来求解

import java.util.Scanner;public class Main{private static boolean noPrimes[];public static void main(String[] args) {noPrimes = new boolean [40];noPrimes[1] = true;for (int i = 2; i < noPrimes.length; i++) {if (noPrimes[i]) {continue;}for (int j = i*2; j < noPrimes.length; j+=i) {if (noPrimes[j]) {continue;}noPrimes[j] = true;}}int k = 1;Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int ans[] = new int[n];boolean used[] = new boolean[n+1];used[1] = true;ans[0] = 1;System.out.println("Case "+k+":");DFS(ans,used,1,n);System.out.println();k++;}sc.close();}private static void DFS(int[] ans, boolean[] used, int index, int n) {if (index==n) {System.out.print(ans[0]);for (int i = 1; i < n; i++) {System.out.print(" "+ans[i]);}System.out.println();}for (int i = 2; i <= n; i++) {if (!used[i]) {if (noPrimes[i+ans[index-1]]) {continue;}used[i] = true;ans[index] = i;if (index==n-1) {if (noPrimes[ans[0] + ans[index]]) {used[i] = false;continue;} }DFS(ans, used, index+1, n);//递推used[i] = false;}}}
}