ACM-搜索-回溯法 dfs,素数环升级版

本文主要是介绍ACM-搜索-回溯法 dfs,素数环升级版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：一个数字环，任意连续的三个数字和不是7的倍数，求问环的排列方案数。
1.环状：所以1 2 与2 1是一样的。
2.顺逆时针被认为是不一样的，n=3时，1 2 3 和 3 2 1是两种方案（3 2 1 的方案等同于1 3 2）
输入：n
输出：方案数
深搜解决，但是要注意：
1.因为是环，我们为了避免重复，保证第一个数字一定为1。
2.然后因为是三个连续的和判断，我们要先遍历，试放置第二数字的情况。
3.排列中间必须注意是否被访问过，vis解决
4.本题因为顺逆时针不一样，所以直接sum输出就好。
(如果顺逆时针一样的时候，就要sum/2,但是2的时候因为第一个数字一定为1，所以不能/2，要特判。)
5.dfs回溯模板

dfs{                退出条件；（计数）for(尝试放置的数字){if(判断是否可放置）{vis标记dfs递归vis还原（为了多情况）}}}

#include<iostream>
#include<string.h>
using namespace std;
int sum=0,n;
int vis[16];
int a[16];
void dfs(int cur){if(cur==n&&((a[0]+a[n-2]+a[n-1])%7)&&((a[n-1]+a[0]+a[1])%7)){//for(int i=0;i<n;i++)cout<<a[i];//cout<<endl;sum++;return ;}else {//避免重复，起头默认1开始 for(int i=2;i<=n;i++){if(!vis[i]&&((i+a[cur-1]+a[cur-2])%7)){a[cur]=i;vis[i]=1;dfs(cur+1);vis[i]=0;}}}return;
}

这个是顺逆时针相同的，所以n==2要特判。

int main(){int t;while(cin>>n){sum=0;memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));if(n==2||n==1)cout<<1<<endl;else{a[0]=1;for(int i=2;i<=n;i++){a[1]=i;vis[i]=1;dfs(2);vis[i]=0;}cout<<sum/2<<endl;}}return 0;
}

这个是本题的答案，无需特判。

while(cin>>n){sum=0;memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));//if(n==2||n==1)cout<<1<<endl;//else{a[0]=1;for(int i=2;i<=n;i++){a[1]=i;vis[i]=1;dfs(2);vis[i]=0;}cout<<sum<<endl;//}}