Skip to content

14053: 【原4053】Prime Ring

题目

题目描述

author: 肖云轩 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4053

Description

给定一个整数N，请你将1,2,3...N组成一个首尾相接的环，使得任意两个相邻的数之和为素数。

请按字典序输出所有可能方案。若无合法方案请输出"None"。

由于数字组成的是一个首尾相接的环，规定输出时从1的位置开始按照顺时针输出。

例如:

  • -2-3-4-1- 请输出为 1 2 3 4
  • -3-2-1-4- 请输出为 1 4 3 2

Input Format

一行,一个整数N。 (2 <= N <= 16)

Output Format

1-k行，按字典序输出k个答案，使用空格间隔N个数字
若没有答案输出None

Sample Input

4

Sample Output

1 2 3 4  
1 4 3 2

数据范围

对于40%的数据 (2 <= N < 10)  
对于100%的数据 (2 <= N <= 16)

BugenZhao's solution 

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

bool notPrime[] = {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};

int nums[20];
bool vis[20];
bool flag;
int N;

void search(int current) {
    if (current == N) {
        if (notPrime[nums[0] + nums[N - 1]]) {
            for (int i = 0; i < N; ++i) {
                printf("%d ", nums[i]);
            }
            printf("\n");
            flag = true;
        }
    } else {
        for (int i = 2; i <= N; ++i) {
            if (!vis[i] && notPrime[i + nums[current - 1]]) {
                nums[current] = i;
                vis[i] = true;
                search(current + 1);
                vis[i] = false;
            }
        }
    }
}

int main() {
    cin >> N;
    if (N % 2 == 1) {
        printf("None\n");
        return 0;
    }

    for (int i = 1; i <= N; ++i) {
        nums[i - 1] = i;
    }

    search(1);
    if (!flag) {
        printf("None\n");
    }

    return 0;
}

FineArtz's solution 

/* Prime Ring */
#include <iostream>
#include <cmath>
using namespace std;

bool canplace[17][17];
bool beplaced[17];
int a[20];
int n;

bool isp(int x){
    if (x == 2) return true;
    for (int i = 2; i <= trunc(sqrt(x)) + 1; ++i)
        if (x % i == 0) return false;
    return true;
}
bool check(int a[], int n){
    for (int i = 0; i <= n - 1; ++i)
        if (!isp(a[i] + a[i + 1])) return false;
    return true;
}

void dfs(int x){
    if (x == n + 1){
        for (int i = 1; i <= n; ++i)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 2 - x % 2; i <= n; i += 2){
        if (!beplaced[i] && canplace[i][a[x - 1]]){
            if (x == n && !canplace[i][1]) continue;
            beplaced[i] = true;
            a[x] = i;
            dfs(x + 1);
            a[x] = 0;
            beplaced[i] = false;
        }
    }
}
int main(){
    cin >> n;
    if (n % 2 != 0){
        cout << "None" << endl;
    }
    for (int i = 2; i <= n; ++i)
        for (int j = 1; j < i; ++j){
            if (isp(i + j)) canplace[i][j] = true;
            else canplace[i][j] = false;
            canplace[j][i] = canplace[i][j];
        }
    a[1] = 1;
    beplaced[1] = true;
    dfs(2);
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstdio"
using namespace std;

bool not_num[50] = { 0 };
struct edge {
    int num = 0;
    int to[20] = { 0 };

    void add_edge(int pos) {
        to[num++] = pos;
    }
};
edge edges[20];
bool visited[20] = { 0 };
int route[20] = { 0 };
int n;
int cnt = 0;

void DFS(int num, int pos) {
    if (num == 0) {
        if (pos == 1) {
            ++cnt;
            printf("%d", route[0]);
            for (int i = 1; i < n; ++i)
                printf(" %d", route[i]);
            printf("\n");
        }
        return;
    }
    if (visited[pos])
        return;
    visited[pos] = true;
    route[n - num] = pos;
    for (int i = 0; i < edges[pos].num; ++i) {
        DFS(num - 1, edges[pos].to[i]);
    }
    visited[pos] = false;
    route[n - num] = 0;
}

int main() {
    //计算质数
    int max_k = 40;
    for (int i = 2; i <= max_k / 2 + 1; ++i) {
        if (not_num[i])
            continue;
        for (int j = i * 2; j <= max_k; j += i)
            not_num[j] = true;
    }

    cin >> n;

    //计算质数路径
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j)
                continue;
            if (!not_num[i + j])
                edges[i].add_edge(j);
        }
    }

    DFS(n, 1);
    if (cnt == 0)
        printf("None");

    return 0;
}

q4x3's solution 

/**
 * dfs
 **/
#include <stdio.h>
#include <iostream>

using namespace std;

int p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

bool isPrime(int a) {
    for(int i = 0;i < 11;++ i) {
        if(a == p[i]) return 1;
    }
    return 0;
}

int n, a[20], vis[20];

void dfs(int x) {
    if(x == n + 1 && isPrime(a[1] + a[n])) {
        for(int i = 1;i <= n;++ i) {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }
    for(int i = 2;i <= n;++ i) {
        if(!vis[i] && isPrime(a[x - 1] + i)) {
            vis[i] = 1;
            a[x] = i;
            dfs(x + 1);
            vis[i] = 0;
        }
    }
}

int main() {
    cin >> n;
    if((n == 1) || (n == 3) || (n == 5) || (n == 7) || (n == 9) || (n == 11)|| (n == 13) || (n == 15)) {
        cout << "None" << endl;
    } else {
        a[1] = 1;
        dfs(2);
    }
    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int rec[20];
int _is_prime[1000] = { 0 };
bool used[20] = { 0 };
int N;

bool is_prime(int i) {
    if (_is_prime[i] == 0) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                _is_prime[i] = 2;
                return false;
            }
        }
        _is_prime[i] = 1;
        return true;
    } else {
        return _is_prime[i] == 1;
    }
}

bool found = false;
int dfs(int n) {
    if (n > N) {
        if (is_prime(rec[N] + rec[1])) {
            found = true;
            for (int i = 1; i <= N; i++) printf("%d ", rec[i]);
            printf("\n");
        }
        return 1;
    }
    for (int i = 1; i <= N; i++) {
        if (!used[i]) {
            if (is_prime(rec[n - 1] + i)) {
                rec[n] = i;
                used[i] = true;
                dfs(n + 1);
                used[i] = false;
            }
        }
    }
    return 0;
}

int main() {
    cin >> N;
    used[1] = true;
    rec[1] = 1;
    dfs(2);
    if (!found) cout << "None" << endl;
    return 0;
}

victrid's solution 

#include <cstring>
#include <iostream>
using namespace std;
//Is the cout's problem?
//下次再不printf我直播吃屎
bool sum_is_prime[17][17] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                             0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
                             0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
                             0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
                             0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0,
                             0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,
                             0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0,
                             0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,
                             0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0,
                             0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 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, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,
                             0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,
                             0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
                             0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0,
                             0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,
                             0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0};

bool visited[17] = {0};
int storage[17]  = {0};
bool gotcha      = false;
int dfs(int num, int depth, int total) {
    depth += 1;
    visited[num]   = true;
    storage[depth] = num;
    if (depth == total) {
        if (sum_is_prime[1][num]) {
            for (int i = 1; i <= depth; i++) {
                printf("%d ", storage[i]);
            }
            printf("\n");
            gotcha = true;
        } else {
            visited[num] = false;
            return 0;
        }
    }
    for (int i = 2 + (num & 1) ^ 1; i <= total; i += 2)
        if (sum_is_prime[num][i] && (!visited[i]))
            dfs(i, depth, total);
    visited[num] = false;
    return 0;
}
int main() {
    int total;
    cin >> total;
    if (total & 1) {
        cout << "None" << endl;
        return 0;
    }
    dfs(1, 0, total);
    if (!gotcha)
        cout << "None" << endl;
    return 0;
}