问题描述：从1到18这18数摆成一个环，要求相邻的两个数的和是一个素数。
思路：1.找出给定范围内素数的值
2.以1为起始位置，利用递归和深度搜索，找到这18个数；注意，还要保证最后一个位置上的数和第一个位置上的数相加也为素数
3.对已使用过的数，赋值1，表明已不能再被使用了
#include <iostream> #include <cstdio> #include <cstring> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ char bUsed[20]; //判断素数环中位置是否已被占用 int a[20]; //存放素数环中的元素，以便输出 char bIsP[40]; //存放40以内的素数 int nN=4; //素数环实际个数 void GetPrime(void) { //找出40以内的素数，并存入bIsP[]中，非素数位置赋0值（这里素数的值由数组的位置表示） memset(bIsP+2,1,38*sizeof(char)); //将bIsP+2中的字符全部设置为1，为申请新的内存做初始化工作；也为后面判断素数赋上1值 for(int i=2;i<7;++i) //这里的7是通过对40开根号得到的 { if(bIsP[i]==0) continue; for(int j=i*i;j<40;j+=i) bIsP[j]=0; } } bool dfs(int nlevel) { //开始找每个位置的值，使相邻两个值相加为素数 if(nlevel==nN) { if(bIsP[a[0]+a[nN-1]]==0) //当nlevel到达最后一个位置时，还要判断它与第一个位置上的值相加是否为素数 return false; // 此函数不能运行 for(int i=0;i<nN-1;++i) //若为素数，将这nN个数全部输出 printf("%d ",a[i]); printf("%d ",a[nN-1]); return true; } for(int i=1;i<=nN;++i) // { if(bUsed[i]==1) //若该位置被占用就进入下一次循环 continue; if(bIsP[i+a[nlevel-1]]==0) //若该位置的数与前一位置上的数相加不为素数，则进入下一个循环 continue; a[nlevel]=i; bUsed[i]=1; //值i被占用，后面选值时不能再用此值 if(!dfs(nlevel+1)) //等价于if(dfs(nlevel+1)==0），也就是说bool型的dfs为假时执行下面的语句 bUsed[i]=0; else return true; } } int main(void) { GetPrime(); //调用函数找出1~40之间的素数 a[0]=1; //第一个位置放1 bUsed[1]=1; dfs(1); //调用函数并输出值 printf(" "); return 0; }
疑问：为什么存放素数的数组要用字符型的？