从1到20这20个数摆成一个环，要求相邻的两个数的和是一个素数。 【算法流程】 1、数据初始化； 2、递归填数：判断第i个数填入是否合法； A、如果合法：填数；判断是否到达目标（20个已填完）： 是，打印结果；不是，递归填下一个；（剪枝条件） B、如果不合法：选择下一种可能
#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> using namespace std; bool b[21]={0}; //判断i是否出现在素数环中 int total=0,a[21]={0}; //a记录素数环中的每一个数 int search(int t); //回溯过程。形参表示素数环中的数的编号 int print(); //输出方案 bool pd(int,int); //判断素数 int search(int t){ //寻找所有解 int i; for (i=1;i<=20;i++) //有20个数可选 if (pd(a[t-1],i)&&(!b[i])){ //判断与前一个数是否构成素数及该数是否可用 a[t]=i; //素数环中的第t个数 b[i]=1; //i进入素数环 if (t==20) { //一个解 if (pd(a[20],a[1])) print();} else search(t+1); b[i]=0; } } int main(){ search(1); cout<<total<<endl; //输出总方案数 } int print(){ total++; cout<<"<"<<total<<">"; for (int j=1;j<=20;j++) cout<<a[j]<<" "; cout<<endl; } bool pd(int x,int y){ int k=2,i=x+y; while (k<=sqrt(i)&&i%k!=0) k++; if (k>sqrt(i)) return 1; else return 0; }