素数环问题 P154【回溯法】

#include<iostream>
#include<math.h>
using namespace std;

bool isPrime(int x)	//判断整数x是否是素数
{
    int n = (int)sqrt(x);
    for(int i=2; i<=n; i++)
        if(x%i == 0) return false;
    return true;
}

bool isLegal(int k, int n, int a[])	//判断位置k填写是否满足约束条件
{
    for(int i=0; i<k; i++)		//判断即将填写的值是否与填写过的重复
        if(a[i] == a[k]) return false;
    if(!isPrime(a[k]+a[k-1])) return false;	//判断相邻数之和是否为素数
    if(k==n-1 && !isPrime(a[k]+a[0])) return false;	//判断第一个和最后一个之和是否为素数
    return true;
}

void primeCircle(int n)
{
    int a[n];	//用数组a[]来存储素数环
    for(int i=0; i<n; i++)	//将数组所有元素都初始化为0
        a[i] = 0;

    a[0] = 1;
    int k = 1;
    while(k>=1)
    {
        a[k] = a[k]+1;
        while(a[k]<=n)
        {
            if(isLegal(k,n,a)) break;	//位置k可以填写整数a[k]
            else a[k] = a[k]+1;	//试探下一个数
        }

        if(a[k]<=n && k==n-1)	//求解完毕，输出素数环
        {
            for(int i=0; i<n; i++)
                cout<<a[i]<<" ";
            cout<<endl;
            return;
        }

        if(a[k]<=n && k<n-1) k++;	//填写下一个
        else a[k--] = 0;	//回溯
    }
}

int main()
{
    primeCircle(20);
    return 0;
}