A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 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.
Input
n (0 < n ≤ 16)
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.
You are to write a program that completes above process.
Sample Input
6
8
Sample Output
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
题目类型：递归枚举
算法分析：从1开始生成排列并在生成过程中判断相邻两个数之和是否是素数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
/************************************************** filename :f.cpp author :maksyuki created time :2018/6/11 14:48:25 last modified :2018/6/11 15:11:57 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 66; int n, vv[maxn]; bool vis[maxn], is_prime[maxn]; bool solve(int v) { for(int i = 2; i * i <= v; i++) if(v % i == 0) return false; return true; } void dfs(int p) { if(p == n + 1 && is_prime[vv[1]+vv[n]]) { for(int i = 1; i <= n; i++) { if(i == 1) cout << vv[i]; else cout << " " << vv[i]; } cout << endl; return ; } for(int i = 2; i <= n; i++) { if(!vis[i] && is_prime[i+vv[p-1]]) { vis[i] = true; vv[p] = i; dfs(p + 1); vis[i] = false; } } } int main() { #ifdef LOCAL CFF; //CFO; #endif int id = 1; memset(is_prime, false, sizeof(is_prime)); for(int i = 1; i < maxn * 2; i++) is_prime[i] = solve(i); while(cin >> n) { if(id > 1) cout << endl; cout << "Case " << id++ << ":" << endl; memset(vv, 0, sizeof(vv)); memset(vis, false, sizeof(vis)); vis[1] = true; vv[1] = 1; dfs(2); } return 0; } |
- « 上一篇：uva10976