Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order. You are to write a program that completes above process. Print a blank line after each case.
Sample Input
6 8
Sample Output
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 这里是一个典型的深搜问题，这里如果用Boolean打表，调用import java.util.Arrays;在杭电上提交会超时 import java.util.Scanner; public class Main { public static void main(String[] args) { int Case=0; Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n= sc.nextInt(); int color[] = new int[n]; int arr[] = new int[n]; int prant[] = new int [n]; int count=0; //Arrays.fill(color,false); for(int i=0;i<arr.length;i++){ arr[i]=i+1; //初始化所有数据 color[i]=-1; } Case++; System.out.println("Case "+(Case)+":"); dfs(arr,color,prant,count,0); System.out.println(); } } public static void dfs(int[] arr,int[] color,int[] prant,int count,int m){ count++; if(count==arr.length && prime(prant[0],arr[m])){ //第一个数与最后一个数相加的和也是素数 prant[count-1] = arr[m]; for(int i=0;i<arr.length-1;i++){ System.out.print(prant[i]+" "); } System.out.println(prant[arr.length-1]); } for(int i=0;i<arr.length;i++){ color[m]=1; if(prime(arr[m],arr[i]) && color[i]==-1){ color[i]=1; prant[count-1]=arr[m]; dfs(arr,color,prant,count,i); color[i]=-1; } } } //判断素数 public static boolean prime(int i,int j){ int sum=i+j; for(int k=2;k*k<=sum;k++){ if(sum%k==0){ return false; } } return true; } }
