质数环
【题目描述】
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下面就是6的一个素数环。
1 4 3 2 5 6
1 6 5 2 3 4
【输入描述】
有多组测试数据，每组输入一个n（0<n<20）,n=0表示输入结束。
【输出描述】
每组第一行输出对应的Case序号，从1开始。如果存在满足题意叙述的素数环，从小到大输出。否则输出No Answer。
【样例输入】
6 8 3 0
【样例输出】
Case1: 1 4 3 2 5 6 1 6 5 2 3 4 Case2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 1 4 7 6 5 8 3 2 1 6 7 4 3 8 5 2 Case3: No Answer
【题目分析】
(1)搜索回溯的题目。从1开始，每个位置有N种不同的可能，只要填进去的数合法就行。
(2)合法指的是与前面的数不同，与左边相邻的和是一个素数
(3)最后一个数还要与第一个判断。
【参考代码】
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans[100],flag[100]; //输入数，结果数组，标记数组
//判断两个数的和是不是素数函数
int prime(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;
}
//打印输出函数
int print()
{
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
//搜索回溯算法
int search(int k)
{
int i;
for(i=1;i<=n;i++) //n个数
if( prime(ans[k-1],i) && (flag[i]==0)) //判断与前一个数是否构成素数及这个数当前是不是可用
{ ans[k]=i;
flag[i]=1; //标记当前这个数使用过了
if(k==n) //到达边界
{
if( prime(ans[n],ans[1])) //严重最后一个和第一个
print();
}
else
search(k+1);
flag[i]=0;
}
}
int main()
{
cin>>n;
search(1); //从第一个位置开始找
return 0;
}
但是你运行上面的代码后发现和结果不一样，因为题目要求每个序列必须从1开头。所以还要再改一下，我们稍微改下if判断条件就可以实现了。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans[100],flag[100]; //输入数，结果数组，标记数组
//判断两个数的和是不是素数函数
int prime(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;
}
//打印输出函数
int print()
{
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
//搜索回溯算法
int search(int k)
{
int i;
for(i=1;i<=n;i++) //n个数
if( prime(ans[k-1],i) && (flag[i]==0)) //判断与前一个数是否构成素数及这个数当前是不是可用
{ ans[k]=i;
flag[i]=1; //标记当前这个数使用过了
if(k==n) //到达边界
{
if( prime(ans[n],ans[1]) && ans[1]==1) //严重最后一个和第一个
print();
}
else
search(k+1);
flag[i]=0;
}
}
int main()
{
cin>>n;
search(1); //从第一个位置开始找
return 0;
}
(adsbygoogle = window.adsbygoogle || []).push({});