C语言素数环 DFS +回溯

#include<cstdio>
#include<cstring>
using namespace std;
int n;
int a[21];
int su[101];
 
int visit[200];
void DFS(int c)
{
    a[0]=1;// 初始为1
    if(c==n&&!su[a[0]+a[n-1]])//  如果 c==n  则结束     如果 第一个与最后一个和也为素数 则 输出
    {
        for(int i=0; i<n-1; i++)
            printf("%d ",a[i]);
        printf("%d",a[n-1]);
        printf("\n");
    }
    else
    {
        for(int i=2; i<=n; i++)
            if(!visit[i]&&!su[i+a[c-1]])//  如果  次数 与前一个数相加为素数 且没被拜访过 则  赋值
            {
                a[c]=i;
                //printf("%d   ",a[c]);
                visit[i]=1;//  标记
                DFS(c+1);//  继续查找下一行
                visit[i]=0;//回溯
            }
    }
}
 
int main()
{
    int t=1;
    for(int i=2; i<9; i++)
        for(int j=i*i; j<50; j+=i)
            su[j]=1;//赋值 1-50 内的非素数为1
    while(scanf("%d",&n)!=EOF)
    {
        printf("Case %d:\n",t++);
        memset(visit,0,sizeof(visit));
        DFS(1);
        printf("\n");
 
    }
    return 0;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。