数据结构求解素数环问题（JAVA版）：将N个自然数（1~N），使得每相邻两数之和为素数，构成一个素数环！

//【例4.3】求解素数环问题。
public class PrimeRing {
public PrimeRing(int n) //求1～n素数环
{
SeqList<Integer> ring = new SeqList<Integer>(n); //创建一个顺序表存储素数环
ring.append(new Integer(1)); //1添加到素数环中
SeqQueue<Integer> que = new SeqQueue<Integer>(n); //创建一个队列que// LinkedQueue<Integer> que = new LinkedQueue<Integer>(); //创建一个队列que
for (int i=2; i<=n; i++) //2～n全部入队
que.enqueue(new Integer(i));
// System.out.println(que.toString());

int i=0;
while (!que.isEmpty())
{
int k = que.dequeue().intValue(); //出队
// System.out.print("dequeue: "+k+"\t");
if (isPrime(ring.get(i)+k)) //判断是否为素数
{
i++;
ring.append(new Integer(k)); //k添加到素数环中
}
else
que.enqueue(new Integer(k)); //k再次入队
// System.out.println("队列: "+que.toString());
}
System.out.println("素数环: "+ring.toString());
}

public boolean isPrime(int k) //判断k是否为素数
{
if (k==2)
return true;
if (k<2 || k>2 && k%2==0)
return false;
int j=(int)Math.sqrt(k); //Math.sqrt(k)返回k的平方根值
if (j%2==0)
j--; //获得测试范围内的最大奇数
while (j>2 && k%j!=0)
j-=2;
return j<2;
}
public static void main(String args[])
{
new PrimeRing(10);
}
}
运行结果：素数环: (1, 2, 3, 4, 7, 10, 9, 8, 5, 6)

问题：上述的算法不完全，并且未求多个解，求完整（求多个解）算法！（N为10)

举报该问题

推荐答案 2013-04-22

嗯。想一下。

这个是分别以每个自然数为起点，开始遍历，结果会有重复。

比如

(1, 2, 3, 4, 7, 10, 9, 8, 5, 6)

(6, 1, 2, 3, 4, 7, 10, 9, 8, 5)
import java.util.ArrayList;
import java.util.List;
public class PrimeRing {
// 求1～n素数环
public PrimeRing(int n) {
List<Integer> src = new ArrayList<Integer>();
List<Integer> dest = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
src.add(i);
}
loop(src, dest, n);
}
public void loop(List<Integer> src, List<Integer> dest, int n) {
if (dest.size() == n) {
Integer start = dest.get(0);
Integer end = dest.get(dest.size() - 1);
if (isPrime(start + end)) {
System.out.println(dest);
}
return;
}
for (int i = 0; i < src.size(); i++) {
Integer element = src.remove(i);
if (dest.isEmpty()) {
dest.add(element);
} else {
Integer tmp = dest.get(dest.size() - 1);
if (isPrime(tmp + element)) {
dest.add(element);
} else {
src.add(i, element);
continue;
}
}
loop(src, dest, n);
src.add(i, element);
dest.remove(dest.size() - 1);
}
}
// 判断k是否为素数
public boolean isPrime(int k) {
if (k == 2)
return true;
if (k < 2 || k > 2 && k % 2 == 0)
return false;
int j = (int) Math.sqrt(k); // Math.sqrt(k)返回k的平方根值
if (j % 2 == 0)
j--; // 获得测试范围内的最大奇数
while (j > 2 && k % j != 0)
j -= 2;
return j < 2;
}
public static void main(String args[]) {
new PrimeRing(10);
}
}