基于数组的深度优先搜索二例

 写了程序一定要总结。

两个都是由别人的问题引起的。

问题1:

巧排数字，将1,2,...,19,20这20个数字排成一排，使得相邻的两个数字之和为一个素数，且首尾两数字之和也为一个素数。编程打印出所有的排法

枚举绝对要死人。。。

指数级别的时间复杂度

这里采用深度优先搜索，

程序中采用两个数组，

一个是resultArray，结果数组，标识当前结果

另一个是flagArray，状态数组，标识哪些数字已经被选取。

因为根据题意，这个结果是循环的，所以直接把结果数组的第一位置为1，

然后从第二位开始，进行深度优先搜索。

程序中有一个变量locationIndex,标识当前结果数组中已经存在选取好数字的位数。

在while循环中对locationIndex有相应的操作逻辑，循环退出条件是locationIndex == 0

程序中没有注释，有点晕。。。

上代码:

public void arrayPrime() {

int[] resultArray = new int[20];

StringBuffer result = new StringBuffer();

boolean []arrayFlag = new boolean[20];

for(int i=0;i<resultArray.length;i++) {

resultArray[i] = 0;

}

for(int i=0;i<arrayFlag.length;i++) {

//全部没有被选择

arrayFlag[i] = true;

}

//把首位置为1

resultArray[0] = 1;

arrayFlag[0] = false;

result.append(1+" ");

int locationIndex = 1;

int totalCount =0;

while(locationIndex > 0) {

int temp = findNextPrime(resultArray[locationIndex-1],resultArray[locationIndex],arrayFlag);

if(temp == 0) {

if(resultArray[locationIndex]!=0) {

arrayFlag[resultArray[locationIndex]-1] = true;

}

resultArray[locationIndex] = 0;

locationIndex--;

}else {

if(resultArray[locationIndex]!=0) {

arrayFlag[resultArray[locationIndex]-1] = true;

}

resultArray[locationIndex] = temp;

locationIndex++;

arrayFlag[temp-1] = false;

}

if(locationIndex == 20) {

locationIndex--;

//20个数都排满了,检查下

if(this.isPrimeNum(resultArray[19]+1)) {

totalCount++;

System.out.println("gg"+locationIndex+java.util.Arrays.toString(resultArray));

}

}

}

System.out.println(totalCount);

}

public int findNextPrime(int a,int b1,boolean []b) {

int start;

if(a%2==0) {

start = 1;

}else {

start = 2;

}

for(int i=start;i<21;i=i+2) {

if(this.isPrimeNum(i+a)&&b[i-1]&&(a!=i)&&i>b1) {

return i;

}

}

return 0;

}

boolean isPrimeNum(int i)

{

if(i<2) return false;

if(i==2||i==3) return true;

if(i%2==0) return false;

int temp = (int)Math.sqrt(i)+1;

for (int j = 2; j < temp; j++)

{

if (i % j == 0)

{

return false;

}

}

return true;

}

问题2:

给出1-20的20个整数，问任意多个不重复的数相加等于20的组合有多少种？

注：1+19=20；19+1=20 是一种组合！

注意任意多个这个条件，

有人说暴力枚举也能出来，对于这个问题来说，暴力枚举的时间复杂度也能接受。。。

因为是任意多个，所以while循环的退出条件有所改变，

变成了resultArray[0]==20

因为枚举到20

就可以认定程序可以退出终止了

其实这个代码里面还可以剪枝，继续优化的。

上代码:

  public void find20() {

int []resultArray = new int[20];

for(int i=0;i<resultArray.length;i++) {

resultArray[i] = 0;

}

resultArray[0] = 1;

int count = 0;

int arrayLocationIndex = 1;

int tempNumber = 1;

int locationIndex = 1;

while(locationIndex !=20) {

int temp = 0;

for(int i=0;i<arrayLocationIndex;i++) {

temp += resultArray[i];

}

if(temp > 20) {

resultArray[arrayLocationIndex-1] = 0;

resultArray[arrayLocationIndex-2] = tempNumber;

arrayLocationIndex--;

}

if(temp == 20) {

System.out.println(java.util.Arrays.toString(resultArray));

count++;

resultArray[arrayLocationIndex-1] = 0;

tempNumber = resultArray[arrayLocationIndex-2];

resultArray[arrayLocationIndex-2] = tempNumber;

arrayLocationIndex--;

arrayLocationIndex--;

}

if(temp <20) {

resultArray[arrayLocationIndex] = ++tempNumber;

arrayLocationIndex++;

}

if(resultArray[0] == 20) {

break;

}

}

System.out.println(count);

}