学步园

题目链接：http://acm.hdu.edu.cn/status.php?user=hqucst&pid=1016&status=5

题目分析：把n个数排成一圈，然后两两相加为素数。由于需要把所有的情况都找出来，所以这里用递归来做，把所有情况遍历一遍。递归的思想还需要好好领悟。我记得上学期有一段时间研究了一阵，有那么一点点感觉，但不是很深刻。

whatever，今天解决了一个困扰我很久的问题，因为我在提交这道题的时候，出现了格式错误，单词不记得了。反正我搞了很久，总算解决了，窃喜ing.......

#include<iostream>     
#include<string.h>
using namespace std;

#define M 42

bool prime[M];
int a[22];
int used[22];

void Prime()
{
	memset(prime,1,sizeof(prime));
	int i,j;
	for(i = 2; i < 7; ++i)//外层循环到n的平方根就可以了
	{
		for(j = 2; j * i <= 40; ++j)
		{
			prime[j*i] = 0;
		}
	}
}

void DFS(int num, int n)
{
	if(num >= n && prime[a[n] + a[1]])
	{
		for(int i = 1; i < n; ++i)
		{
			printf("%d ",a[i]);
		}
		printf("%d\n", a[n]);
		return; 
	}

	for(int i = 2; i <= n; ++i)//遍历所有数据，用used标记该数到底有没有使用
	{
		if(!used[i] && prime[a[num] + i])//考察第num+1个符合情况的数
		{
			a[num + 1] = i;
			used[i] = 1;
			DFS(num + 1, n);
			used[i] = 0;		
		}
	}
}

void main()
{
	int n;
	int t;
	a[1] = 1;
	t = 1;
	Prime();
	while(scanf("%d",&n) != EOF)
	{
		printf("Case %d:\n", t++);
		if((n&1) == 0)
		{
			memset(used,0,sizeof(used));
			DFS(1, n);//从1开始
		}
		printf("\n");
	}
}