http://acm.nyist.net/JudgeOnline/problem.php?pid=488
描述
有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。
为了简便起见,我们规定每个素数环都从1开始。例如,下图就是6的一个素数环。
如果存在满足题意叙述的素数环,从小到大输出。
否则输出No Answer。
6 8 3 0
Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 Case 3: No Answer
解法1:生成测试法(TLE)
#define RUN #ifdef RUN #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <vector> #include <list> #include <cctype> #include <algorithm> #include <utility> #include <math.h> #include <ctime> using namespace std; int is_prime(int x) { for(int i = 2; i*i <= x; i++) if(x % i == 0) return 0; return 1; } int main() { #ifndef ONLINE_JUDGE freopen("nyist488.in", "r", stdin); freopen("out.out", "w", stdout); #endif int n, A[50], isp[50]; //scanf("%d", &n); int cases = 1; while(cin>>n && n!=0){ bool noAnswer = true; cout << "Case " << cases << ":" << endl; cases++; //生成素数表,加快后面的判断 //判断第i个数是否是素数,如果isp[i]返回1则是,返回0则否 for(int i = 2; i <= n*2; i++) isp[i] = is_prime(i); //A[0]:1 //A[1]:2 //A[2]:3 //... for(int i = 0; i < n; i++) A[i] = i+1; do { int ok = 1; for(int i = 0; i < n; i++) { //如果相邻两数之和不是素数 if(!isp[A[i]+A[(i+1)%n]]) { ok = 0; break; } } if(ok) { noAnswer = false; for(int i = 0; i < n; i++) printf("%d ", A[i]); printf("\n"); } }while(next_permutation(A+1, A+n)); if(noAnswer){ cout << "No Answer" << endl; } } return 0; } #endif
解法2:回溯法+剪枝
同时注意自环的判断
#define RUN #ifdef RUN #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <vector> #include <list> #include <cctype> #include <algorithm> #include <utility> #include <math.h> #include <ctime> using namespace std; bool noAnswer; int cases = 1; #define MAXN 10000 int is_prime(int x) { for(int i = 2; i*i <= x; i++) if(x % i == 0) return 0; return 1; } int n, A[MAXN], // A数组用于保存结果 A[x]=y 第x个位置放了大小为y的数 isp[MAXN], // isp数组用于判断是否素数 isp[x]=y 大小为x的数,其素数属性为y vis[MAXN]; // vis数组用于标示第i个数是否已经被使用过了 vis[x]=y,大小为x的数,已使用性为y void dfs(int cur) { //递归边界,同时测试第一个数和最后一个数 if(cur == n && isp[A[0]+A[n-1]]) { noAnswer = false; for(int i = 0; i < n; i++) printf("%d ", A[i]); printf("\n"); } else { for(int i = 2; i <= n; i++){ if(!vis[i] && isp[i+A[cur-1]]) { A[cur] = i; //标志把数i放在cur的位置上 vis[i] = 1; //标志i已经用了 dfs(cur+1); //寻找下一个位置应该放的数 vis[i] = 0; //还原全局变量,清除标志 } } } } int main() { #ifndef ONLINE_JUDGE freopen("nyist488.in", "r", stdin); freopen("out.out", "w", stdout); #endif //生成素数表,加快后面的判断 //判断第i个数是否是素数,如果isp[i]返回1则是,返回0则否 memset(isp, 0, sizeof(isp)); //isp[2] = isp[3] = isp[5] = isp[7] = isp[11] = isp[13] = isp[17] = isp[19] = isp[23] = isp[29] = isp[31] = isp[37] = 1; for(int i = 2; i <= 20*2; i++){ isp[i] = is_prime(i); } A[0] = 1; while(scanf("%d",&n) && n!=0){ noAnswer = true; cout << "Case " << cases << ":" << endl; cases++; memset(vis, 0, sizeof(vis)); //自环的情况 if(n==1) { printf("%d\n",A[0]); continue;} //重要的剪枝!!! //如果n为奇数,存在不等于2的偶数,不为素数,可以直接排除 // 奇+偶=奇 // 奇+奇=偶 // 偶+偶=偶 if(n%2 != 0) { printf("No Answer\n"); continue;} dfs(1); if(noAnswer){ cout << "No Answer" << endl; } } return 0; } #endif
相关推荐
NYIST数据结构实验指导书样本.doc
NYIST_数据结构实验指导书.pdf
NYIST-linux应用开发实验指导书.doc
NYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书.docxNYIST-数据结构实验指导书....
1. 声明一个Circle类,有 1) 数据成员Radius(半径) 2) 成员函数GetValue()用来给半径赋值 3) 成员函数GetArea()计算圆的面积 在主函数中创建一个Circle类的对象进行测试,显示出面积。 2. 声明一个tree类,有 ...
nyist-studentonline-project:学生在线app用户行为分析源码
《南阳理工二手交易平台 | Secondary trading platform For Nyist》 Just For Share | 仅仅分享 使用申明 禁止用来盈利 前前后后开发2年时间啦 感谢你的支持,麻烦点个star,辛苦 将本项目拉取到本地之后,立刻执行...
给n个点,m条边,让构建一个有向无环无重边的图,并且图的最短路是素数,最小生成树也是素数。 思路: 题意的可塑造性很强,我们可以让最小生成树就是最短路,呢么我们现在就是给最小生成树找一个素数,很明显最小生成...
题意: 给n个位置,q次操作,每次对操作可以改变i位置的数,定义f(i,j)=ai∗a(i+1)∗…∗aj.f(i,j) = ai * a(i+1) * … * aj.f(i,j)=ai∗a(i+1)∗…∗aj. 求整个区间中所有子区间乘积的和对10007取模 ...
c++ 课程设计任务书 c++ nyist
域名服务器建立实例 1. 实例环境 假设我们需要建立一台应用于以下情况的一个主...3. 域名服务器的IP定为202.102.240.65主机名为ns1.nyist.net 4. 校园网通过huwei8016交换机与Internet连接。 5. 要解析的服务器有:
source insight 插件合集, 非常适用的Sourceinsight插件,提高效率事半功倍 http://www.cnblogs.com/wangqiguo/p/3713211.html http://blog.csdn.net/nyist327/article/details/39935379
我的第二个小应用程序#1.0版本 作者:java2班 许江川@2007.1.1 版权所有:◎ 2006~2007 nyist.2006.java2.浪迹天涯 Softwere http://xjch4539.googlepages.com此程序为共享产品,使用之前请先阅读介绍!
本文实例为大家分享了C语言... Author: nyist_xiaod Date : 2012.5.8 */ #include #include #include #include <stdlib> #define Print_Head_Num puts(班级 姓名 语文 数学 英语 总成绩) #define Print_Head_C
//FileName:class.php //Summary: Access数据库操作类 //Author: forest //CreateTime: 2006-8-10 //LastModifed: //copyright (c)2006 freeweb.nyist.net/~chairy [email]chaizuxue@163.com[/email] // ...
//FileName:class.php //Summary: Access数据库操作类 //Author: forest //CreateTime: 2006-8-10 //LastModifed: //copyright (c)2006 //http://freeweb.nyist.net/~chairy //[email]chaizuxue@163.com...
南阳理工学院OJ第1版解题报告V1.0.pdf