[BFS|DFS]]HDU 1016 Prime Ring Problem


素数环问题

#include 
#include 
#define MAXSIZE 40
int n, len, tcase ;
int prime[MAXSIZE], ans[MAXSIZE], used[MAXSIZE] ;
//Prime为素数表,ans为输出表,Used标记是否已经使用
void dfs (int a)
{
    ans[len++] = a ;
    used[a] = 1 ;
    int i ;
    if (len - 1 == n)//搜索结束的条件,边界判断
    {
        if (prime[ans[1]+a])
        {
            for (i = 1 ; i < n ; ++i)
                printf ("%d ",ans[i]) ;
            printf ("%dn", ans[i]) ;
        }
    }
    else//对每个数据分别探索看是否满足条件
    {
        for (i = 2 ; i <= n ; ++i)
            if (prime[i + a] && !used[i])//相加为素数且未使用
                dfs (i) ;
    }
    --len ;
    used[a] = 0 ;
}
int main ()
{
    int i, j ;
    //以下Prime函数作用:因数标记为0;质数为16843009,就是四个int字符的1000000010000000100000001
    memset (prime, 1, sizeof (prime)) ;//此处初始化为1!!
    for (i = 2 ; i < MAXSIZE ; ++i)
        if (prime[i])
            for (j = i ; j*i < MAXSIZE ; ++j)
                prime[j*i] = 0 ;
    //
    tcase = 0 ;
    while (scanf ("%d", &n) != EOF)
    {
        memset (used, 0, sizeof (used)) ;
        len = 1 ;
        ++tcase ;
        printf ("Case %d:n", tcase) ;
        dfs (1) ;//从1开始DFS
        puts ("") ;
    }
    return 0 ;
}

发表评论