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

hdu 1016 Prime Ring Problem

程序员文章站 2022-05-21 08:44:12
...

hdu 1016 Prime Ring Problem

题目传送门
简单搜索问题,这题只要每次判断填的数与前一次填的数相加不为素数,最后一个数则还要考虑与第一个数的和不为素数,这题我打表做的。比较简单

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

using namespace std;

int a[22];
bool isprime[40];
bool used[21];
void init()
{
    memset(isprime, true, sizeof(isprime));
    for(int i = 2; i <= 40; ++i)
    {
        if(isprime[i])
        {
            for(int  j = 2 * i; j <= 40; j += i)
                isprime[j] = false;
        }
    }
}
//当前要填的位置为pos,总共长度为n
void dfs(int pos, int n)
{
    //当已经填完n个数后
    if(n&1) return;
    if(pos == n + 1)
    {
        if(isprime[a[n]+1])
        {
            for(int i = 1; i <= n; ++i)
            {
                printf("%d%c", a[i], i==n ? '\n' :' ');
            }
        }
        return;
    }
    for(int i = 2; i <= n; ++i)
    {
        if(!used[i] && isprime[i+a[pos-1]])
        {
            used[i] = 1;
            a[pos] = i;
            dfs(pos+1,n);
            used[i] = 0;
        }
    }
}
int main()
{
    init();
    int n;
    a[1]  = 1;
    int cas = 1;
    while(cin >> n)
    {
        memset(used,false,sizeof(used));
        printf("Case %d:\n", cas++);
        dfs(2,n);
        printf("\n");
    }
    return 0;
}

相关标签: hdu 搜索