正文
HDOJ-ACM1016(JAVA) 字典序全排列，并剪枝
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
转载声明：原文转自http://www.cnblogs.com/xiezie/p/5576273.html
题意：
一个环是用图中所示的n个圆组成的。把自然数1、2、……、n分别放入每个圆中，并在相邻的圆中的数值总和为一个质数。
注：第一圈数应该是1。
输出：
输出格式显示为下面的示例。每一行代表在环里圆中的数从1开始顺时针和逆时针。数字的数量必须满足上述要求。按字典顺序打印解决方案。
你是写一个程序，完成上述过程。
每一种情况下打印一条空白线。
题目分析：
首先，因为需要遍历多次，质数不可能每次判断的时候都重新计算，应该生产质数表（0<n<20，因此质数表中的质数小于40）。
java算法如下：
/*
* 输入数字，作为序号传入
* 判断是否质数
* */
static boolean isAPrimeInForty(int num){
if(isPrimes[num]==1){
return true;
}
return false;
} /*
* 生产序号为0-39的0，1序列
* 1代表为质数
* 0代表为非质数
* */
static int[] isPrimes = createPrimes(); static int[] createPrimes(){
int[] primes = new int[40];
for(int i = 2 ; i != 40 ; i ++ ){
if(isAPrime(i)){
primes[i] = 1;
}
}
return primes;
} //判断是否质数
static boolean isAPrime(int num){
int len = (int) (Math.sqrt(num)+1);
for(int i = 2 ; i != len ; i ++){
if(num%i==0){
return false;
}
}
return true;
}
解题：
第一次，由于最近搞了全排列，我的解题思路是：将所有数进行字典序全排列（由于数字是顺序输入数组，我在字典序排列中省去了排序的过程），并判断是否符合题中条件。如果是则存储（因此，顺时针逆时针都包括）或者直接输出。
结果：Time Limit Exceeded----------不过我相信这样做答案一定是正确的
代码如下：
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int n;
int count = 1;
while(scan.hasNextInt()){
n = scan.nextInt();
System.out.println("Case "+ count+++ ":" );
int[] nums = new int[n];
for(int i = 0 ; i != n; i ++){
nums[i] = i+1;
}
getAllPermutationsAndCheck(nums,1,n-1);
System.out.println();
}
scan.close();
}
static boolean isAnswer(int[] nums){//判断数组是否符合条件
int len = nums.length;
for(int i = 0 ; i != len ; i ++ ){
int sum = nums[i%len] + nums[(i+1)%len];
if(!isAPrimeInForty(sum)){
return false;
}
}
return true;
}
static boolean isAPrime(int num){//判断是否质数
int len = (int) (Math.sqrt(num)+1);
for(int i = 2 ; i != len ; i ++){
if(num%i==0){
return false;
}
}
return true;
}
static void getAllPermutationsAndCheck(int[] cs,int start,int len){//cs为字典序数组
if(cs==null)
return;
while(true)
{
if(isAnswer(cs)){
for(int j = 0 ; j != cs.length; j ++){
if( j == cs.length -1){
System.out.print(cs[j]);
break;
}
System.out.print(cs[j] + " ");
}
System.out.println();
}
int j=start+len-2,k=start+len-1;
while(j>=start && cs[j]>cs[j+1])
--j;
if(j<start)
break;
while(cs[k]<cs[j])
--k;
swap(cs,k,j);
int a,b;
for(a=j+1,b=start+len-1;a<b;++a,--b)
{
swap(cs,a,b);
}
}
}
static boolean isAPrimeInForty(int num){//判断是否质数
for(int i = 0 ; i != 12 ; i ++ ){
if(num>primes[i]){
continue;
}
if(num==primes[i]){
return true;
}
if(num<primes[i]){
return false;
}
}
return false;
}
static int[] primes = createPrimes();
static int[] createPrimes(){
int[] primes = new int[12];
int count = 0;
for(int i = 2 ; i != 40 ; i ++ ){
if(isAPrime(i)){
primes[count] = i;
count++;
}
}
return primes;
}
static void swap(int[] nums , int i , int j){
int t;
t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
当然，当我全排列10个数的时候，秒输出，当我全排列12个数的时候，半天都输出不了~
只能说明：全排列是最差的暴力破解，没有进行剪枝
下面一个思路是：深度搜索
同样是字典序全排列（不过是从1-n的全排列，有了具体场景）
但是在字典序全排列过程中，进行剪枝，遇到一个前后相加不为质数的就跳过（省去了后面的全排列）
结果：Accepted 执行占用时间：2698MS 执行占用内存：13940K
具体java算法如下：
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] arg){
Scanner scan = new Scanner(new BufferedInputStream(System.in));
int n;
int count = 1;
answer[0] = 1;
while(scan.hasNextInt()){
n = scan.nextInt();
System.out.println("Case "+ count+++ ":" );
checkAndOutput(n,1);
System.out.println();
}
scan.close();
}
static int[] answer = new int[21];
static int[] isUsed = new int[21];
static void checkAndOutput(int n,int index) {//index为数组的序号
int len = n+1;
int last = n-1;
if(index == n){
for(int i=0; i != n ; i ++ ){
if(i == last){
System.out.println(answer[i]);
return;
}
System.out.print(answer[i]+" ");
}
}
for(int i = 2 ; i != len ; i ++ ){//数组序号为index的遍历
if(isUsed[i] == 0){
if(!isAPrimeInForty(i + answer[index-1])){
continue;
}
isUsed[i]=1;
answer[index] = i;
if(index==last){
if(!isAPrimeInForty(1+ answer[index])){//增加一步头尾相加判断
isUsed[i]=0;
continue;
}
}
checkAndOutput(n,index+1);
isUsed[i]=0;
}
}
}
/*
* 输入数字，作为序号传入
* 判断是否质数
* */
static boolean isAPrimeInForty(int num){
if(isPrimes[num]==1){
return true;
}
return false;
}
/*
* 生产序号为0-39的0，1序列
* 1代表为质数
* 0代表为非质数
* */
static int[] isPrimes = createPrimes();
static int[] createPrimes(){
int[] primes = new int[40];
for(int i = 2 ; i != 40 ; i ++ ){
if(isAPrime(i)){
primes[i] = 1;
}
}
return primes;
}
//判断是否质数
static boolean isAPrime(int num){
int len = (int) (Math.sqrt(num)+1);
for(int i = 2 ; i != len ; i ++){
if(num%i==0){
return false;
}
}
return true;
}
static void swap(int[] nums , int i , int j){
int t;
t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
