学步园

一道很入门的深搜回溯题http://acm.hdu.edu.cn/showproblem.php?pid=1016

没有优化剪枝，执行时间较长，但可以ac

#include <iostream>
#include <math.h>
using namespace std;
int n,id=0; //n为输入，id为输出的case编号
int depth = 0; //记录递归的层数，每一层对应填入的一个值的位置
int solution[21]; //解数组，因为1已经填入，因此保存除了1之外的数字的顺序，下标从0开始
int used[21]; //记录元素是否已经使用过了，下标从1开始到n对应n个元素

//判断一个数是否为素数
bool isPrime(int num)
{
    for(int i=2 ; i<=sqrt(num) ; ++i)
    {
        if(num % i == 0)
        {
            return false;
        }
    }
    return true;
}
//深搜回溯，依次填入 2到n
void PrimeRing(int curr )
{
    if(depth == n-1 && isPrime(curr+1)) //终止条件，若已经填入了n-1个数字（1认为已经填入了） 且最后一个与1相加素数
    {
        cout << "1";  //从1开始，1第一个输出
        for(int i=0 ; i<n-1 ; ++i)  //输出结果
        {
            cout << " " << solution[i];
        }
        cout << endl;
        return ;
    }
    for(int i=2 ; i<=n ; ++i)
    {
        if(used[i]==0 && isPrime(curr + i)) //若i没被使用，且和为素数
        {
            solution[depth] = i;
            depth++;       //深度增加1
            used[i] = 1;   //使用状态置1
            PrimeRing(i); //深搜
            used[i] = 0;   //回溯后使用状态为0；
            depth--;    //回溯后深度减少1
        }
    }
    return ;
}
int main()
{
    while(cin >> n)
    {
        for(int i=0 ; i<=n ; ++i) //初始化使用状态数组
            used[i] = 0;
        used[1] = 1; //从1开始，1肯定被使用
        cout << "Case " << ++id << ":" << endl;
        PrimeRing(1);
        cout << endl;
    }
    return 0;
}