hdoj 1016 Prime Ring Problem 【DFS】

本文主要是介绍hdoj 1016 Prime Ring Problem 【DFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

策略如题

链接 http://acm.hdu.edu.cn/showproblem.php?pid=1016

代码：

#include<stdio.h>
#include<string.h>
int prime[25] = {1, 1}, n, vis[25]; //vis作用：标记是否用过
int a[25];
void f()  //找出来前20的素数 判定为0
{for(int i = 2; i <= 24; i ++){if(prime[i] == 0)for(int j = i+i; j <= 24; j +=i)prime[j] = 1;}
}
void dfs(int step)
{int i;if(step == n){if(prime[a[step-1]+a[step-2]]==0&&prime[a[step-1]+1] == 0){  //这处就是判断最后一位能不能和邻接的两个环能否构成素数printf("1");for(int j = 1; j < n; j ++)printf(" %d", a[j]);printf("\n");}return ;}for(i = 2; i <= n; i ++){if(vis[i] == 0&&prime[i+a[step-1]] == 0){  //如果i没有被用并且满足跟前面一位的构成素数，就将其存到相应的数组中a[step] = i;vis[i] = 1;dfs(step+1);vis[i] = 0;}}
}
int main(){f();int v = 1;while(scanf("%d", &n) == 1){memset(vis, 0, sizeof(vis));printf("Case %d:\n", v++);a[0] = 1;vis[1] = 1;dfs(1);printf("\n");}return 0;
}

这篇关于hdoj 1016 Prime Ring Problem 【DFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---