hdu 1016 Prime Ring Problem （dfs）

一切见注释。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool vis[22];
int n;
int ans[22];
int top;

bool isprime(int x)//判断素数
{
    for(int i=2;i<x;i++)
    if(x%i==0)return false;
    return true;
}

void dfs(int pos)
{
    if(pos==n)//如果已经把环填满 也就是所有的数和前一个数的和是素数
    {//那么我们就判断最后一个数和第一个数的和是不是素数
        if(isprime(ans[n-1]+1))//如果是  输出方案
        {
            for(int i=0;i<n;i++)
            printf("%d%c",ans[i],i==n-1?'\n':' ');
        }
        return ;//如果不是  返回
    }

    for(int i=1;i<=n;i++)//枚举这个位置放的数
    {
        if(vis[i])continue;//如果这个数已经放过
        if(!isprime(i+ans[pos-1]))continue;//如果你要尝试加入的这个数和上一个数的和不是素数 就不加进去
        vis[i]=true;//如果以上条件都不符合  那么就可以加入到这个位置   标记为已经放入
        ans[pos]=i;//放入方案中
        dfs(pos+1);//递归下一次  去下一个位置尝试放数
        vis[i]=false;//把这个数拿出来  尝试另外一种方案
    }
}

int main()
{
    int CASE=1;
    while(scanf("%d",&n)!=EOF)
    {
        top=0;
        ans[0]=1;//把 1 放入第一个位置
        vis[1]=true;//把 1 标记为已经放入环中
        printf("Case %d:\n",CASE++);//输出CASE
        dfs(1);//进入递归
        puts("");//输出换行
    }
    return 0;
}

hdu 1016 Prime Ring Problem （dfs）,布布扣,bubuko.com

hdu 1016 Prime Ring Problem （dfs）

原文：http://blog.csdn.net/u010709592/article/details/27410779