【一級講解】素數環——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;
}