素数环

素数环素数环时间限制:1000 ms|内存限制:65535 KB难度:2素数环时间限制:1000 ms|内存限制:65535 KB难度:2

大家好,又见面了,我是你们的朋友全栈君。

素数环

时间限制:
1000 ms  |  内存限制:65535 KB
难度:
2
描述
  有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,下图就是6的一个素数环。

<span role="heading" aria-level="2">素数环

输入
  有多组测试数据,每组输入一个n(0<n<20),n=0表示输入结束。
输出
  每组第一行输出对应的Case序号,从1开始。如果存在满足题意叙述的素数环,从小到大输出。否则输出No Answer。
样例输入
6
8
3
0
样例输出
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
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
Case 3:
No Answer

思路:  dfs。先打表记录40以内是素数的数组prime,因为相邻数之和有可能最大为39,所以只需枚举到39。从2开始到n枚举哪些数是满足条件,有的话就将当前这个数记录
在a数组中,并且标记这个数已经被访问,再递归下去寻找下一个数,如果递归不满足条件的话,将当前这个数置为0。每当m==n+1时就输出当前素数环。如果给定的整数n为奇数,那么
肯定不存在素数环,(因为肯定存在两个奇数相邻,而奇数与奇数的和为偶数,所以一定不是素数环)这个节省了不少递归时间
 1 #include<stdio.h>  2 #include<string.h> //数组初始化memset()函数头文件,memset(数组名,初始值,sizeof(数组名)),C语言中#include<string.h>   3 int prime[40];//存放素数的数组,题目要求0<n<20,最多两数之和20+20=40,所以数组大小开到40就够了   4 int a[22];//储存并更新排序后的数的序列  5 int visit[22];  6 int m;//代表当前所判断的数是第几个数  7 void ifprime()//打表法将1到40之间所有的素数用1标记放入数组中对应位置,其余数用0标记  8 {  9 for(int i=2;i<=40;i++) 10 prime[i]=1; 11 prime[1]=0; 12 for(int i=2;i<=40;i++) 13 for(int j=2*i;j<=40;j+=i) 14 prime[j]=0;//偶数标记0  15 } 16 void dfs (int m,int n) 17 { 18 if(m==n+1&&prime[1+a[n]])//如果当前判断的是第n+1个数,则证明前面所有的排序均符合题意,因为是环所以要判断首尾相加是否是素数,prime[1+a[n]判断是否为素数  19  { 20 for(int i=1;i<=n;i++) 21 printf("%d ",a[i]); 22 printf("\n"); 23 return ; 24  } 25 else 26  { 27 for(int i=2;i<=n;i++)//因为题目要求从1开始输出,所以判断时从2开始回溯 28  { 29 if(!visit[i]&&prime[i+a[m-1]])//如果i没被用过且他和上一个数的和为素数,则往下执行 30  { 31 a[m]=i;//将i储存开始判断下一个数 32 visit[i]=1;//标记i已经用过 33 dfs(m+1,n);//继续对下一个数进行判断 34 visit[i]=0;//清除标志 35  } 36  } 37  } 38 } 39 int main() 40 { 41 int n,i,j,k=1; 42  ifprime(); 43 while(~scanf("%d",&n)&&n)//多组数据,当输入0时结束  44  { 45 memset(a,0,sizeof(a)); 46 memset(visit,0,sizeof(visit)); 47 a[1]=1; 48 visit[1]=1; 49 printf("Case %d:\n",k++); 50 if(n==1)//如果n是1则自己成环输出1 51 printf("1\n"); 52 else if(n%2!=0)//如果n为奇数,直接输出No Answer 53 printf("No Answer\n"); 54 else 55 dfs(2,n);//从第二个数开始向后依次判断  56  } 57 return 0; 58 }

https://blog.csdn.net/zsd201531107026/article/details/53044349

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155812.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • pycharm21.3 激活 3月最新注册码

    pycharm21.3 激活 3月最新注册码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • perl正则表达式实现大写字母转小写字母

    perl正则表达式实现大写字母转小写字母这个功能不难,但是要求必须用s///的形式,而且后面不能加第三个参数,不能是s///g这样的形式。不过可以采用多个这样的表达式。例如 s/A/a/s/B/b/s/AB/ab/…………….最终就是要求所有这些表达式组合起来,使得不论输入多少个大写字符,都会被转化为小写。我在atftpd的pcre功能中需要我将大写的请求文件转化为小写,所以需要一个rules文件

  • samba文件共享服务器,全网最详细的samba文件共享服务![通俗易懂]

    samba文件共享服务器,全网最详细的samba文件共享服务![通俗易懂]了解samba:1.samba是linux共享文件系统,将SMB(服务消息块)/CIFS(通用网络文件系统)协议在linux中进行实现,让linux、unix、windows系统之间可以相互访问文件共享。2.samba服务相关知识点:1samba是C/S(客户端/服务器)架构,2监听TCP/139及TCP/445(由smbd程序监听),监听UDP/137和UDP/138(由nmbd程序监听)…

  • C++字符串流stringstream与string知识介绍与用法小结

    C++字符串流stringstream与string知识介绍与用法小结之前总结了C++的文件输出输入流的相关知识,通过介绍底层的streambuf缓冲区,从而与stringstream流(字符串流)联系了起来,本文就对此进行简单的介绍。首先介绍string。string是C++提供的字符串类,和C类型的字符串相比,除了有不限长度的优点外,还有其他许多方便的功能,其可以看成类似STL里vector数组的一种容器,可以方便的进行数据的增删改查,并可以进行…

  • String,StringBuffer与StringBuilder的区别

    String,StringBuffer与StringBuilder的区别一、JavaString类——String字符串常量字符串广泛应用 在Java编程中,在Java中字符串属于对象,Java提供了 String类来创建和操作字符串。需要注意的是,String的值是不可变的,这就导致每次对String的操作都会生成新的String对象,这样不仅效率低下,而且大量浪费有限的内存空间。我们来看一下这张对String操作时内存变化的图:我们可…

  • 后缀[Icanhelp@cock.li].firex3m勒索病毒数据恢复方案解决方案.firex3m

    后缀[Icanhelp@cock.li].firex3m勒索病毒数据恢复方案解决方案.firex3m

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号