uva524

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

11 6月 2018

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开始生成排列并在生成过程中判断相邻两个数之和是否是素数

/**************************************************
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;
}

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

一	二	三	四	五	六	日
« 6月
	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

超客的水墨烟雨

uva524

分类目录

标签云

书签

近期评论