【一级讲解】素数环——DFS深度优先搜索

素数环

题目：从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。输出所有情况和种数

---

问题分析：

最近刚好在学深度优先搜索，就找了一些题目练练手，之前有写过一篇很粗糙的DFS文章，以啊哈算法这本书的题目为例，画图讲解了一下DFS的基本原理（尤其是回溯复原那部分）。

根据啊哈算法给的DFS模板，我又自己改进了一下，如下：

DFS模板一：
int search ( int n )
{
	if ( 符合输出最终解/边界条件 )
		输出操作;
	else
		for ( 遍历所有可能的情况 )
			if ( 符合判断条件 )
				{
					保存结果 mark[i]=1;
					继续深度搜索 search ( n+1 );
					回溯复原; 
				} 		 
} 

DFS模板二：
int search ( int n )
{
	for ( 遍历所有可能的情况 )
		if ( 符合判断条件 )
			{
				保存结果 mark[i]=1;
				if ( 符合输出最终解/边界条件 )
					输出操作;
				else 
					继续深度搜索 search ( n+1 );
				回溯复原; 
			} 		 
} 

这道题目好像只能DFS吧，就是每次放一个数字都检查是否与前一个数的和是素数，最后还要判断首尾相连的两个数。

这道题一开始贪图方便我用的i是全局变量，不知道为什么就死活运行不出来答案，然后检查了大概有1个多小时，最后小心翼翼地放入search里面就行了…不得不说挺迷的hhh

原来老师说的不到万不得已不要轻易用全局变量是对的hhh

---

代码：

#include <bits/stdc++.h>
using namespace std;

int search(int);
void print();
bool judge(int,int);

bool mark[21];
int a[21];
int ans=0;

int main()
{
	search(1);
	cout << "The total number is " <<ans;
	putchar('\n');
}

int search(int n)
{
	int i;
	for ( i=1; i<=20; i++ )
		if ( (!mark[i]) && judge(i,a[n-1]) )
		{
			a[n]=i;
			mark[i]=1;
			if ( n==20 )
				{	if ( judge(a[20],a[1]) )	print(); }
			else
				search(n+1);
			mark[i]=0;
		}
}

void print()
{
	ans++;
	int k;
	cout << "[Solution" << ans << "]:" << a[1];
	for ( k=2; k<=20; ++k )
		cout << " " << a[k]; 
	putchar('\n');
}

bool judge(int a, int b)
{
	int sum=a+b;
	int k;
	for ( k=2; k<=sqrt(sum); ++k)
		if ( sum%k==0 )
			return 0;
	return 1;
}