欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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