2010.06.06 A题

题目：把自然数1到20连成一个环，使得环中每两个数的和为素数

 

package mlkimg.one;

import java.util.ArrayList;

public class PrimeRound {


	public static void main(String[] args) {
		PrimeRound pr = new PrimeRound();
		pr.primeRing(5);
	}

	public void primeRing(int n) {
		int[] in = new int[n];
		for (int i = 0; i < n; i++) {
			in[i] = i + 1;
		}
		boolean[] used = new boolean[n];//判断是否用过自然数
		ArrayList out = new ArrayList<Integer>();//存放满足条件自然    数的数组
		used[0] = true;
		out.add(1);//把1作为环中的第一个数

		makeRing(in, used, out, n);
	}

	public void makeRing(int[] in, boolean[] used, ArrayList out, int n) {
		int size = out.size();

		if (size == n) {
			if(isPrime((Integer)out.get(n-1)+1)){
			String s = out.toString();
			System.out.println(s);
			return;
			}
		}

		for (int i = 1; i < n; ++i) {

			int last = (Integer) out.get(size - 1);
			boolean isprime = isPrime(last + in[i]);
			if (used[i] || !isprime)
				continue;//判断自然数的是否满足条件

			out.add(in[i]);
			used[i] = true;

			makeRing(in, used, out, n);//递归调用

			used[i] = false;
			out.remove(size);//回溯
		}
	}

	public boolean isPrime(int n) {
		boolean s = true;
		if (n == 1)
			s = false;
		else if (n < 4)
			return s;
		else if (n % 2 == 0)
			s = false;
		else if (n < 9)
			return s;
		else if (n % 3 == 0)
			s = false;
		else {
			double r = Math.floor(Math.sqrt(n));
			int f = 5;
			while (f <= r) {
				if (n % f == 0 || n % (f + 2) == 0)
					s = false;
				f += 6;
			}
		}
		return s;

	}

}

 分析：这题的关键在于回溯，建立一个解空间为20的树，运用回溯找出所有的满足条件的解。（说了等于没说，呵呵）

ps：这题磨了我大半天，看来递归回溯这类问题真的很杀人脑细胞，现在在想如果是迭代的话代码会有多长呢？

这题貌似可以用les vegas法