HDU——1016 Prime Ring Problem
程序员文章站
2022-05-21 08:46:09
...
A ring is compose of n circles as shown in diagram. Put natural number 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.
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. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
大致意思是:
有一个n个点组成的环,在每一点中在 1~n中选取一个数字 使得该点与相邻的点 的和是一个素数(第一个点必须是1)
举例 n=6时
其中一种可能为:1 4 3 2 5 6
满足第一个点是1,且 1+4=5为素数,4+3=7为数数,3+2=5为素数(依次类推) 当最后一个数时与第一个数相加
AC代码如下:
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn=25;
int a[maxn]; //用来保存数字环
int n;
bool isok[maxn]; //用来标记某个数字是不是已经选过了
bool isprime(int x) //用来判断该数是不是素数
{
if(x==1)
return false;
else
for(int i=2;i<=sqrt(x);i++)
if(!(x%i))
return false;
return true;
}
void dfs(int k)
{
if(k==n && isprime(a[k-1]+a[0]) ) //递归的结束条件 如果递归到最后一个点,且最后一个点也满足情况就输出
{
for(int i=0;i<n;i++)
if(i)
cout<<' '<<a[i];
else cout<<a[i];
cout<<endl;
}
else
{
for(int i=2;i<=n;i++) //第一个点的数字已经确定,所以就从2~n开始找
{
if(!isok[i]) //如果这个数前面没有标记过 那么就采用这个数
{
a[k]=i;
isok[i]=true;
}
else //说明这个数之前标记过了,那么就继续找数
continue;
if(isprime(a[k]+a[k-1])) //放入该点后是素数
dfs(k+1); //继续下一个点
isok[i]=false; //最后将标记取消!(重要!!)
}
}
}
int main()
{
memset(isok,0,sizeof(isok));
a[0]=1;
int kase=1;
while(cin>>n)
{
cout<<"Case "<<kase++<<':'<<endl;
dfs(1);
cout<<endl;
}
return 0;
}