3thweek.c uva 524.prime ring problem

题意：

输入正整数n，把整数1，2，3，……，n组成一个环，使得相邻的两个整数之和均为素数。输出时从整数1 开始逆时针排列。同一个环应恰好输出一次。n<=16。

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和回溯法。

 

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

int is_prime(int x)
{
    for(int i = 2; i*i <= x; i++)  // 注意：i<=sqrt(x)。
        if(x % i == 0) 
            return 0;

        return 1;
}

int n, A[50], isp[50], vis[50];

void dfs(int cur)
{
    if(cur == n && isp[A[0]+A[n-1]] )  //最后一个数字需要单独判断。
    {
        for(int i = 0; i < n; i++)
        {
            if(i != 0) printf(" ");  //控制每次第一个数字前不输出空格
            printf("%d", A[i]);
        }
        printf("
");
    }
    else for(int i = 2; i <= n; i++)  //放置每个数i
        if(!vis[i] && isp[i+A[cur-1]])  //如果i没有被用过，并且和前一个数的和为素数
        {
            A[cur] = i;
            vis[i] = 1;//设置使用标志
            dfs(cur+1);
            vis[i] = 0;//清除标志
        }
}

int main()
 {
    int kase = 0;
    while(scanf("%d", &n) == 1 && n > 0)
    {
        if(kase > 0)
            printf("
");
        printf("Case %d:
", ++kase);

        for(int i = 2; i <= n*2; i++)
            isp[i] = is_prime(i);

        memset(vis, 0, sizeof(vis));  //清零操作
        A[0] = 1;    //题目要求每组第一个数字为1
        dfs(1);
    }
    return 0;
}