[数据结构与算法]素数环（DFS+回溯）

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。输出时从整数1开始逆时针排列。n<=16。

样例输入:6

样例输出:

1. 1 4 3 2 5 6

2. 1 6 5 2 3 4

#include <iostream>
#include <math.h>
using namespace std;
const int N=20;
int n;
int path[N],state[N];
int isPrime(int m){
?? ?int i;
?? ?for(i=2;i<=sqrt(m);i++){
?? ??? ?if(m%i==0){
?? ??? ??? ?return 0;
?? ??? ?}
?? ?}
?? ?if(m==1){
?? ??? ?return 0;
?? ?}
?? ?return 1;
}
void dfs(int u){
?? ?if(u>n&&isPrime(path[1]+path[n])==1){
?? ??? ?for(int i=1;i<=n;i++){
?? ??? ??? ?printf("%d ",path[i]);
?? ??? ?}
?? ??? ?printf("\n");
?? ?}else{
?? ??? ?for(int i=2;i<=n;i++){
?? ??? ??? ?if(state[i]==0&&isPrime(i+path[u-1])==1){
?? ??? ??? ??? ?path[u]=i;
?? ??? ??? ??? ?state[i]=1;
?? ??? ??? ??? ?dfs(u+1);
?? ??? ??? ??? ?state[i]=0;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
int main(void){
?? ?cin.tie(0);
?? ?cin>>n;
?? ?path[1]=1;
?? ?dfs(2);
?? ?return 0;
}