专题一搜索 H - Prime Ring Problem
- 题目
A ring is composed of n (even number) circles as shown in diagram.
Put natural numbers 1, 2, . . . , n into each circle separately, and thesum 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 thering beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the aboverequirements.
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
- 思路
题目不难，对于每个数字，搜一下与它相加为质数的数就可以了，用dfs寻找每个分支，可以先预处理一次质数表（我没这么干），当然要是不嫌麻烦也可以直接预处理一次1到16的邻接表
本题逆天的地方在于离谱的格式要求，相当严格，每行数字最后不能有多余空格，每组数据后面要空一行，最后一组数据后面还不能有回车，它题目里面还没提示，以至于很多交这题的同学未通过数达到了惊人的-8-9-10-11，最多的甚至有-14
- 代码
#include
#include
#include
#include
#include
using namespace std;
int vis[18],n,ch[18];
int prime(int n)
{
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)return 0;
}
return 1;
}
void dfs(int x)//x:环里现在有几个数
{
if(x==n)
{
if(prime(ch[x]+1))
{
for(int i=1;i