[HDOJ1016]Prime Ring Problem

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

原题：

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

输入N个数字，求1到N这N个数字连成环以后两两相加均为素数的所有情况。

非常经典的DFS题。

 

 

#include <iostream> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int n; int cir[21]; int prime[41]; int vis[21]; int isPrime(int x) {int i;int sqx = sqrt((float)x);for(i = 2; i <= sqx; i++){if(x % i == 0){    return 0;}}return 1; }void dfs(int x) {int i;if(x == n && prime[cir[1]+cir[n]])    //make a circle     {for(i = 1; i < n; i++){printf("%d ", cir[i]);}printf("%d\n", cir[n]);return ;}for(i = 2; i <= n; i++){if(vis[i] == 0 && prime[cir[x]+i]){cir[x+1] = i;vis[i] = 1;dfs(x+1);vis[i] = 0;    //reset         }} }int main() {int i, Case = 1;for(i = 1; i < 41; i++)    //list primes.     {if(isPrime(i)){prime[i] = 1;}}while(scanf("%d", &n) != EOF && n){printf("Case %d:\n", Case++);memset(vis, 0, sizeof(vis));cir[1] = 1;vis[1] = 1;dfs(1);printf("\n");}return 0; }

 

转载于:https://www.cnblogs.com/kirai/p/4515941.html

总结

以上是生活随笔为你收集整理的[HDOJ1016]Prime Ring Problem的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。