当前位置：首页 > 题解目录 > 正文内容

质数环

亿万年的星光5年前 (2021-01-28)题解目录1928

【题目描述】

有一个整数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;
}


扫描二维码推送至手机访问。

版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。

分享给朋友：
返回列表

上一篇：字符全排列(2)

下一篇：数列

相关文章

【题解】2002-T2 选数

【题解】2002-T2 选数

【题目描述】已知n个整数x1,x2,……xn,以及一个整数K(K＜n)。从n个整数中任选k个整数相加,可分别 得到一系列的和。例如当n=4, =3, 4个整数分别为3,7,12,1...

【题解】公路乘车(动态规划)

【题目描述】一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。   没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<...

【题解】大整数减法

【题目描述】求两个大的正整数相减的差。【输入】共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。【输出】一行，即所求的差。【输入样例】9999...

【题解】导弹拦截

【题目描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导...

【题解】奇偶校验

【题目描述】奇偶校验(Parity Check)是一种校验代码传输正确性的方法。根据被传输的一组二进制代码的数位中“1”的个数 是奇数或偶数来进行校验。采用奇数的称为奇校验，反之，称为偶校验。现在给...

【题解】2020-T1 优秀的拆分

【题目描述】一般来说，一个正整数可以拆分成若干个正整数的和。例如，1=1,10=1+2+3+4等。对于正整数n的一种特定拆分，当且仅当在这种拆分下，n被分解为若干个不同的2的正整数次幂。注意，一个数x...

鲁ICP备20008475号

Powered By Z-BlogPHP. Theme by TOYEAN.