2010.06.06 A題

テーマ:自然数の1から20を1つの環につながって、環の中でそれぞれの2つの数の和を素数にします
 

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法が使えるようだ.