素数环

素数环素数环时间限制: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)


相关推荐

  • Ubuntu18.04下安装搜狗输入法「建议收藏」

    Ubuntu18.04下安装搜狗输入法「建议收藏」首先,安装Fcitx输入框架sudoaptinstallfcitx其次,上搜狗输入法官网下载Linux版本搜狗输入法(32位和64位根据自己情况,在虚拟机上用浏览器下载即可然后进入相应的下载目录,进行安装(安装过程中如果有错,运行sudoapt–fix-brokeninstall)安装成功过后,进入设置根据红色箭头进入语言安装界面,安装语言(会自…

  • 机器学习之局部加权、岭回归和前向逐步回归

    回归是对一个或多个自变量和因变量之间的关系进行建模,求解的一种统计方法,之前的博客中总结了在线性回归中使用最小二乘法推导最优参数的过程和logistic回归,接下来将对最小二乘法、局部加权回归、岭回归

    2021年12月30日
  • JavaCV开发详解之1:调用本机摄像头并预览摄像头图像画面视频(建议使用javaCV最新版本)「建议收藏」

    JavaCV开发详解之1:调用本机摄像头并预览摄像头图像画面视频(建议使用javaCV最新版本)「建议收藏」快速传送至:javacv入门指南:序章javaCV系列文章:javacv开发详解之1:调用本机摄像头视频javaCV开发详解之2:推流器实现,推本地摄像头视频到流媒体服务器以及摄像头录制视频功能实现(基于javaCV-FFMPEG、javaCV-openCV)javaCV开发详解之3:收流器实现,录制流媒体服务器的rtsp/rtmp视频文件(基于javaCV-FFMPEG)j…

  • 计算广告概述【计算广告】

    计算广告概述【计算广告】

  • jquery 获取或设置radio单选框选中值的方法

    jquery 获取或设置radio单选框选中值的方法jquery获取或设置radio单选框选中值的代码1、获取选中值,三种方法都可以:2、设置第一个Radio为选中值:3、设置最后一个Radio为选中值:4、根据索引值设置任意一个radio为选中值:5、根据Value值设置Radio为选中值6、删除Value值为rd2的Radio7、删除第几个Radio8、遍历Radio1、获取选中值,三种方法都可以:$(‘input:radio:check…

  • 国密算法概述_国密算法一定要通过硬件吗

    国密算法概述_国密算法一定要通过硬件吗国密即国家密码局认定的国产密码算法,即商用密码。国密算法是国家密码局制定标准的一系列算法。其中包括了对称加密算法,椭圆曲线非对称加密算法,杂凑算法。具体包括SM1,SM2,SM3等,其中:SM2为国家密码管理局公布的公钥算法,其加密强度为256位。其它几个重要的商用密码算法包括:SM1,对称加密算法,加密强度为128位,采用硬件实现;SM3,密码杂凑算法,杂凑值长度为32字节,和SM2算…

发表回复

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

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