7-4 素数环

https://vjudge.net/problem/UVA-524

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

//const int maxn = 50;
int a[50] = {0};
int A[20], vis[20];
int n;

void Prime(){
    a[0] = a[1] = 1;
    for(int i = 2; i <= 31; i++){
        for(int j = 2; i*j < 31; j++){
            if(a[i*j]) continue;
            a[i * j] = 1;
        }
    }
} 

//bool isp(int p){
//  if(!a[p]) return true;
//  return false;
//}

    void dfs(int cur){
    if(cur == n && !a[A[0] + A[n-1] ]) {  //以数组A来储存数字 设置递归边界， 并测试第一个与最后一个数 
        for(int i = 0; i < n; i++){
            printf("%d ", A[i]);
        }
        printf("\n"); 
    }
    else for(int i = 2 ; i <= n ; i++){//尝试放置每个数i 
        if(!vis[i] && !a[i + A[cur-1]]){//如果i没有用过 并且与前一个数之和为素数 
            A[cur] = i ;
            vis[i] = 1;//设置使用标志 
            dfs(cur + 1);
            vis[i] = 0;//清除标志 
        }
    }
}

int main(){
    int cnt = 1;
    A[0] = 1;
    //int cur;
    Prime();
    while(scanf("%d", &n) != EOF){
        //cur = 1;
        memset(vis, 0 ,sizeof(vis));
        printf("Case %d:\n" , cnt++);
        dfs(1);
                printf("\n");
    }
    return 0;
}

就是一个简单的回溯法注意1是固定的所以传入的是数组中的第二个元素

PE...

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

//const int maxn = 50;
int a[50] = {0};
int A[20], vis[20];
int n;

void Prime(){
    a[0] = a[1] = 1;
    for(int i = 2; i <= 31; i++){
        for(int j = 2; i*j <= 31; j++){
            if(a[i*j]) continue;
            a[i * j] = 1;
        }
    }
} 

//bool isp(int p){
//  if(!a[p]) return true;
//  return false;
//}

    void dfs(int cur){
    if(cur == n && !a[A[0] + A[n-1] ]) {  //以数组A来储存数字 设置递归边界， 并测试第一个与最后一个数 
        for(int i = 0; i < n; i++){
             printf("%d%c", A[i], i == n - 1 ? '\n' : ' ');
        }
        //printf("\n"); 
    }
    else for(int i = 2 ; i <= n ; i++){//尝试放置每个数i 
        if(!vis[i] && !a[i + A[cur-1]]){//如果i没有用过 并且与前一个数之和为素数 
            A[cur] = i ;
            vis[i] = 1;//设置使用标志
            dfs(cur + 1);
            vis[i] = 0;//清除标志 
        }
    }
}

int main(){
    int cnt = 1;
    A[0] = 1;
    //int cur;
    Prime();
    while(scanf("%d", &n) != EOF){
        //cur = 1;
        if(cnt > 1) printf("\n");
        memset(vis, 0 ,sizeof(vis));
        printf("Case %d:\n" , cnt++);
        dfs(1);
        //printf("\n");
    }
    return 0;
}

PE原因是除去第一次之外要再每次输出之后添加\n 而我在尾部添加... 另外空格也是另一个点

7-4 素数环

推荐阅读更多精彩内容