UVa 524 Prime Ring Problem

想法：
    用backtracking找出各種可能的組合方式，詳細看底下code：

	#include <cstdio>
	using namespace std;
	int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41};
	int N, Case = 0, ans[20] = {1};
	bool isPrime(int a)
	{
	for (int n : prime)
	if (n == a) return true;
	return false;
	}
	void backtracking(int L, bool visit[])
	{
	if (L == N) {
	if (!isPrime(ans[N-1] + 1)) // 確認頭+尾是否為質數
	return;
	printf("1");
	for (int i = 1; i < N; ++i)
	printf(" %d", ans[i]);
	printf("\n");
	return;
	}
	for (int i = 2; i <= N; ++i) {
	if (visit[i]) continue;
	if (isPrime(i + ans[L - 1])) {
	visit[i] = 1;
	ans[L] = i;
	backtracking(L + 1, visit);
	visit[i] = 0;
	}
	}
	}
	int main()
	{
	while (scanf("%d", &N) != EOF) {
	if (Case++) putchar('\n');
	printf("Case %d:\n", Case);
	bool visit[20] = {0};
	backtracking(1, visit);
	}
	}

view raw [UVa] 524 Prime Ring Problem.cpp hosted with ❤ by GitHub