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

uva-524 Prime Ring Problem 回溯法

程序员文章站 2022-06-08 17:57:39
...

uva-524 Prime Ring Problem 回溯法

回溯法搜索+素数判断
本题的输出格式及其坑,需要注意

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int vis[20];
int cur=0;
int ans[20];
int n;
bool prime(int x)
{
    if(x==2) return 1;
    if(x%2==0||x<2) return 0;
    else
        for(int i=3;i<=sqrt(x+1);i+=2)
        {
            if(x%i==0)
                return 0;
        }
     return 1;  
}
void dfs(int cur)
{   
    if(cur==n&&prime(ans[0]+ans[n-1])) //最末尾和最前元素
    {   printf("%d",ans[0]);
        for (int i = 1;i < n;i++)    printf(" %d",ans[i]);
        printf("\n");
    }
    else for(int i=2;i<=n;i++)
        {
            if(prime(i+ans[cur-1])==1&&!vis[i])
            {   ans[cur]=i;
                vis[i]=1;
                dfs(cur+1);
                vis[i]=0;

            }               
        }   
}

int main()
{
    int kase=0;
    while(~scanf("%d",&n))
    {   
        memset(vis,0,sizeof(vis));
        if(kase)
            cout<<endl;
         printf("Case %d:\n",++kase);
        ans[0]=1;
        dfs(1);

    }
    return 0;
}
相关标签: 搜索 dfs