CCF NOI1153 素数环

xiaoxiao2021-02-28  89

问题链接:CCF NOI1153 素数环


时间限制: 1000 ms  空间限制: 262144 KB

题目描述 

  输入n(2<=n<=20),把1到n这n个数摆成一个环,要求相邻的两个数的和是一个素数。输出任意一个合法答案。

输入

  输入一行一个数n。

输出

  输出1到n的一个排列,表示一个环。如果无解,则输出-1。

样例输入

4 样例输出

1 2 3 4

数据范围限制

  2<=n<=20

提示

 


问题分析

  该问题与《UVA524 UVALive5270 HDU1016 ZOJ1457 Prime Ring Problem》几乎是同一问题,只是有解的话输出一个解,输出格式不同。

程序说明

  参见参考链接。

要点详解

DFS是常用的解题方法。


参考链接:UVA524 UVALive5270 HDU1016 ZOJ1457 Prime Ring Problem。

100分通过的C语言程序:

#include <stdio.h> #include <math.h> #include <string.h> #define N 20 int prime[N * 2]; int ans[N]; int visited[N]; int n, flag; // Eratosthenes筛选法 void sieveofe(int p[], int n) { int i, j; p[0] = 0; p[1] = 0; p[2] = 1; // 初始化 for(i=3; i<n; i++) { p[i++] = 1; p[i] = 0; } int max = sqrt(n); for(i=3; i<=max; i++){ if(p[i]) { for(j=i+i; j<=n; j+=i) //进行筛选 p[j]=0; } } } void print_result() { int i; for(i=1; i<=n; i++) { if(i != 1) printf(" "); printf("%d", ans[i]); } printf("\n"); } void dfs(int count) { int i; if(count == n) { if(prime[ans[count] + ans[1]]) { print_result(); // 输出结果 flag = 0; } } else { for(i=2; flag && i<=n; i++) if(!visited[i] && prime[i + ans[count]]) { ans[count + 1] = i; visited[i] = 1; dfs(count + 1); visited[i] = 0; } } } int main(void) { sieveofe(prime, N * 2 -1); // 初始化标志 memset(visited, 0, sizeof(visited)); scanf("%d", &n); if(n % 2 == 1) printf("-1\n"); else { // 深度优先搜索并且输出结果 ans[1] = 1; visited[1] = 1; flag = 1; dfs(1); if(flag) printf("-1\n"); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-46164.html

最新回复(0)