#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
using namespace std;
bool b[11]= {0};
int total=0,a[11]= {0};
int search(int);//回溯过程
int print();//输出方案
bool pd(int,int);//判断素数
int main()
{
search(1);
cout<<total<<endl;//输出总方案数
}
int search(int t)
{
int i;
for (i=1; i<=10; i++)//有20个数可选
if (pd(a[t-1],i)&&(!b[i]))//判断与前一个数是否构成素数及该数是否可用
{
a[t]=i;
b[i]=1;//跟着i标记
if (t==10)
{
if (pd(a[10],a[1]))
print();
}
else
search(t+1);
b[i]=0;
}
}
int print()
{
total++;
cout<<"<"<<total<<">";
for (int j=1; j<=10; 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;
}
以上是网上博客解决素数环的问题，我一直比较疑惑的点是最终的输出结果为什么只有1，2，3，5，7开头的，4，6，8，9，10开头的呢
当前结果6 1 10 7 4 9 2 3 8 5
当前结果6 1 10 7 4 9 8 3 2 5
当前结果6 1 10 9 2 5 8 3 4 7
当前结果6 1 10 9 8 5 2 3 4 7
比如以上也是满足的
另外一个穷举法
#include<iostream>
#include<algorithm>
using namespace std;
int A[100], isp[100], n;//isp是素数表，用于存放素数
int is_prime(int x){
for(int i = 2; i < x; i++){
if(x % i == 0) return 0;
}
return 1;
}
void printPrime(){
//生成第一个排列，顺序排列， A[1] = 1 A[2] = 2
for(int i = 1; i <= n; i++){
A[i] = i;
}
do{
bool ok = true;
for(int i = 1; i < n; i++){
int index = A[i]+A[i+1];
if(!isp[index]){
ok = false;
break;
}
}
//第一个和最后一个数的和
if(!isp[A[1] + A[n]]){
ok = false;
}
if(ok){
cout << "当前结果";
for(int i = 1; i <= n; i++){
cout << A[i] << " ";
}
cout << endl;
}
} while(next_permutation(A+2, A+n+1));//第一个一定为1不变，只更新第2个到最后1个的排列
} //因为A[0]=0,A[1]=1
int main(){
cin >> n;
//记录1~n*2的值是否为素数
for(int i = 2; i <= n*2; i++){
isp[i] = is_prime(i);
}
printPrime();
}
穷举法却可以有1到10开头的都有，我想不明白第一个程序为什么不能输出全部，实在想不明白，希望大佬指点一下，
全部评论
(0) 回帖