回溯经典之素数环问题

问题描述：假定有从1...n这n(n<=16)个数，求其中一个序列，使得相邻两个数的和是素数，并且第一个和最后一个数也是素数

思路

1.我们可以假定已经有一个序列满足任意两个数之和是素数

2.下一步要做的就是扩充这个序列，即从剩下的数中寻找一个数，使得这个数和既定序列中最后一个数的和是素数

3.如果这个数是最后一个数，那么判断它和第一个数相加的结果是否为素数，如果是，就打印序列，否则什么也不做

因为要求的是环，我们可以假定从任意一个数开始，这里假设从1开始

/*=============================================================== @Author: ray @Created Time : 一  1/21 10:35:44 2013 @File Name: 1.cc @Description:================================================================*/#include <iostream>using namespace std;bool vis[16];int isp[32] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1};void dfs(int a[], int cur,int n) {  if (cur == n) {    if (isp[a[0] + a[n-1]]) {      for (int i = 0; i <= n-1; i++)        cout << a[i] << " ";      cout << endl;    }  } else for (int i = 2; i <= n; i++) {    if (!vis[i] && isp[a[cur-1]+i]) { //判断i放入集合中是否满足序列的要求      a[cur] = i;      vis[i] = true;//将i放入      dfs(a, cur + 1, n);      vis[i] = false;//以i为cur的序列访问完毕,将i移出    }  }}int main() {  int a[16];  a[0] = 1;  dfs(a, 1, 16);  return 0;}