素数环

/* Name: 素数环 Copyright: Author: Date: 10-07-17 20:41 Description: 素数环 时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述 有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。 为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。 输入 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。 输出 每组第一行输出对应的Case序号，从1开始。 如果存在满足题意叙述的素数环，从小到大输出。 否则输出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 */ #include<iostream> #include<cmath> using namespace std; const int N = 8; //环节点的个数 int c[N+1];//记录环节点的值 bool b[N+1]; //b[j]==0表示数字j可用 int sum = 0;//保存可以放置的方案数 bool Prime(int n); //判断是否为素数 void Print(); void DFS(int t); //递归回溯，t表示第t个节点 int main() { for (int i=1; i<=1; i++) //因为每个节点都是等价的，故可命c[1] = 1，否则将造成重复 { c[1] = i; //设置第一个节点的值 b[i] = 1; //数字i已经被使用 DFS(2); //递归处理下一个节点 b[i] = 0; //数字i还原 } return 0; } void DFS(int t) //递归回溯，t表示第t个节点 { for (int i=1; i<=N; i++) { if ((!b[i]) && Prime(c[t-1]+i)) { c[t] = i; //设置第一个节点的值 b[i] = 1; //数字i已经被使用 if (t == N) //最后一个节点，要与节点1结对处理 { if (Prime(c[t]+c[1])) Print(); } else { DFS(t+1); //递归处理下一个节点 } b[i] = 0; //数字i还原 } } } bool Prime(int n) //判断是否为素数 { for (int i=sqrt(n); i>1; i--) { if (n%i == 0) return false; } return true; } void Print() { cout << "方案" << ++sum << ": "; for(int i=1; i<=N; i++) { cout << c[i] << " "; } cout << endl; }

/* Name: 素数环 Copyright: Author: Date: 10-07-17 20:41 Description: 素数环 时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述 有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。 为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。 输入 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。 输出 每组第一行输出对应的Case序号，从1开始。 如果存在满足题意叙述的素数环，从小到大输出。 否则输出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 算法思想 : 素数环:给定n，1~n组成一个素数环，相邻两个数的和为素数。 首先偶数(2例外，但是本题不会出现两个数的和为2)不是素数， 所以素数环里奇偶间隔。如果n是奇数，必定有两个奇数相邻的情况。 所以当n为奇数时，输出“No Answer”。 当n == 1时只1个数，算作自环，输出1 所有n为偶数的情况都能变成奇偶间隔的环-----所以都有结果。 因为n的值比较小，我们可以使用打表的方法用数组prime记录前40个数字是否为素数，这样可以快速判断相邻两个数之和是否为素数。 基本思想是回溯，但是要注意第一个节点直接设置为数字1，最后一个节点，要与节点1结对处理。 */ #include<iostream> #include<cstdio> using namespace std; int prime[41]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0};//打表0-40是否为素数 const int N = 20; int c[N+1];//记录环节点的值 bool b[N+1]; //b[j]==0表示数字j可用 int sum = 0;//保存可以放置的方案数 int n; //环节点的个数 void Print(); void DFS(int t); //递归回溯，t表示第t个节点 int main() { scanf("%d", &n); while (n != 0) { if (n % 2 == 0) { sum = 0;//保存可以放置的方案数 c[1] = 1; //因为每个节点都是等价的，故可命c[1] = 1，否则将造成重复 b[1] = 1; //数字1已经被使用 DFS(2); //从第2个节点开始，递归处理下一个节点 } else { cout << "No Answer" << endl; } scanf("%d", &n); } return 0; } void DFS(int t) //递归回溯，t表示第t个节点 { for (int i=2; i<=n; i++)//因为第一个节点取数字1，故后面的节点不能再取数字1 { if ((!b[i]) && prime[c[t-1]+i]) { c[t] = i; //设置第一个节点的值 b[i] = 1; //数字i已经被使用 if (t == n) //最后一个节点，要与节点1结对处理 { if (prime[c[t]+c[1]]) Print(); } else { DFS(t+1); //递归处理下一个节点 } b[i] = 0; //数字i还原 } } } void Print() { cout << "Case " << ++sum << ": "; for(int i=1; i<=n; i++) { cout << c[i] << " "; } cout << endl; }