1571 - 素数环 DFS深度优化搜索的应用_素数环 优化-程序员宅基地
1571 - 素数环
时间限制：1秒 内存限制：128兆
题目描述
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
输入
有多组测试数据，每组输入一个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
#include<iostream>
#include<math.h>
using namespace std;
int book[45],ans[25]; //book数组进行记录 book开大一点最大的素数也不会大于40 ；ans数组用来记录答案
int n;
int f;
int IsPrime(int x) //这个函数是用来素数判断的，当然本题的只是0-20，可以直接对素数进行打表
{
if(x<=1)
{
return 0;
}
int m=floor(sqrt(x)+0.5);
for(int i=2 ; i<=m ; i++)
{
if(x%i==0)
{
return 0;
}
}
return 1;
}
void dfs(int x,int k) //dsf深度优化搜索，这是题的核心算法；
{
if(k==n)
{
if(IsPrime(1+ans[k-1])==1) //头尾也需要判断判断这是就可以输出了
{
f=1; //这个全局变量本来是用来判断是否有答案的，如果f=0则表示没有答案输出；但是听了某位dalao说这个可有可无奇数除了1，以外都没有answer
cout<<"1 "; //输出答案
for(int i=1 ;i<n ; i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
}
return ;
}
for(int i=2 ; i<=n ; i++)
{
if((x+i)%2==0) //这个可有可无把因为素数除2以外都是奇数
{
continue;
}
if(IsPrime(x+i)==1 && book[i]==0) //判断素数和这个数是否用过
{
ans[k]=i;//ans数组记录答案
book[i]=1; //ans记录以后表示已经用过就把book数组变为 1
dfs(i,k+1); //递归
book[i]=0; //dfs核心回溯
}
}
}
int main()
{
int T=1;
while(cin>>n)
{
int data=n;
if(n==0)
{
break;
}
cout<<"Case "<<T<<":"<<endl; //题目格式输出
T++;
f=0;
if(n==1) //特判1；
{
cout<<"1"<<endl;
continue;
}
if(n%2!=0) //奇数没答案
{
cout<<"No Answer"<<endl;
continue;
}
for(int i=0 ; i<45 ; i++) //book数组没次都需要清0 要不然答案会出错
{
book[i]=0;
}
dfs(1,1); //dfs
if(f==0) //下面这个NO Answer 判断就没什么重要的了 ，可有可无吧；
{
cout<<"No Answer"<<endl;
}
}
}
来源
NYOJ
智能推荐
mysql数据库中某字段一部分乱码-程序员宅基地
文章浏览阅读904次。笔者问题：mysql表（表中数据就是乱码，可能是插入时编码问题，这个问题以后解决）导出excel时数据中有乱码（但是在页面上查看是正常的），我们希望能导出一份没有中文乱码的excel根据热力站中一次&#..._mysql中longtext字段前一半正常一半乱码
RFID防伪设计（物联网工程课程设计）DAY4---LCD屏幕显示_rfid板子设计-程序员宅基地
文章浏览阅读1k次。重点来了这个课程设计中硬件方面一共会有两个重点其中一个自然就是今天要做的OLCD屏幕的驱动第二个是RFID标签的读写由于我买的是野火的I2C OLCD屏幕，自然选择野火自带的例程进行修改，让其能够适配HAL库的开发当然既然是I2C的OLCD，那必然离不开I2C协议值得一提的是，在stm32要实现I2C，可以选择两种方式1.硬件I2C2.软件模拟I2C虽然火哥在标准库的视频中说过硬件I2C可能会存在一定的问题，但是既然买了板子，当然要用哇，不用岂不是暴殄天物。所以，我们还是在cubemx中_rfid板子设计
使用Cygwin, Cygwin/X 介绍-程序员宅基地
文章浏览阅读1.7k次。 空间Using CygwinAs noted, Cygwin provides a Unix-like environment under Windows. The installation directory (by default, c:\cygwin) is the root of the Unix-like file system, which contains bin, et..._cygwin/x
#如何查看oracle的sid_oracle 只读账号 怎么查看sid-程序员宅基地
文章浏览阅读2.5k次，点赞2次，收藏3次。#如何查看oracle的sid转载：https://www.cnblogs.com/lcword/p/8214334.html1、怎样查看Oracle的数据库名称sid用sysdba身份登录 比如 conn sys/密码 as sysdba 匿名管理员登陆执行 select name form Vdatabase;（常用的方法）或是执行select∗fromVdatabase; （常用的方..._oracle 只读账号 怎么查看sid
第3章 信息系统集成专业技术知识-程序员宅基地
文章浏览阅读6.9k次。本章考试分值 15 分主要考点：(1)、信息系统的生命周期(2)、信息系统开发方法(3)、设备、DBMS及技术选型(4)、软件需求(5)、软件设计(6)、软件测试(7)、软件维护(8)、软件复用(9)、软件质量保证及质量评价(10)、软件配置管理(11)、面向对象(12)、软件架构(13)、中间件(14)、数据仓库(15)、网络协议(16)、网络存储(17)、网络安全(18)、网络交换技术(19)、大数据(20)、云计算_信息系统集成专业技术知识
SQL Server——T-SQL基础技术_1、熟练使用t-sql语句对表进行投影、连接、选择查询 2、能根据要求-程序员宅基地
文章浏览阅读3.7k次，点赞3次，收藏7次。文章目录T-SQL基础技术基本语法格式代码准备：（可以按照我的实例自行建立数据库）1、投影查询a、投影指定的列b、投影全部列c、修改查询结果的列标题d、去掉重复行2、选择查询a.表达式比较b.范围比较c.模式匹配d.空值使用代码示例：3、连接查询a.连接谓词b.以JOIN关键字指定的连接（1）内连接（2）外连接4、统计计算5、排序查询6、子查询T-SQL基础技术T-SQL语言中最重要的部分是它..._1、熟练使用t-sql语句对表进行投影、连接、选择查询 2、能根据要求
随便推点
设计模式——代理模式详解（Java版）_java代理模式详解-程序员宅基地
文章浏览阅读5.5k次，点赞56次，收藏117次。看完这篇轻轻松松掌握代理模式_java代理模式详解
NRF52832学习笔记（20）——三轴加速度BMA423使用_hitolo下降沿触发-程序员宅基地
文章浏览阅读534次，点赞2次，收藏3次。一、简介BMA423 采用内部加速计的原始数据并在内部处理数据，从而为开发人员提供有用的结果。这可为微控制器减掉一些负载并加快开发速度。当在可穿戴健身应用中使用时，它可以检测用户是静止不动、跑步还是走路。Bosch Sensortec 为其所有传感器提供固件。在给 BMA423 上电时，它会经历一个内部上电复位 (POR) 序列。在系统 POR 之后，微控制器应运行 Bosch 的 BMA423 初始化程序，以正确配置芯片。初始化程序首先读取内部芯片 ID，并把该 ID 与存储在固件中的芯片 ID_hitolo下降沿触发
matlab交通通行量模型_KDD2020|混合时空图卷积网络：更精准的时空预测模型-程序员宅基地
文章浏览阅读439次。『运筹OR帷幄』转载作者：高德机器学习团队 高德技术报道【导读】时空预测在天气预报、运输规划等领域有着重要的应用价值。交通预测作为一种典型的时空预测问题，具有较高的挑战性。以往的研究中主要利用通行时间这类交通状态特征作为模型输入，很难预测整体的交通状况，本文提出的混合时空图卷积网络，利用导航数据大大提升了时空预测的效果(本文作者高德机器学习团队，论文已被收录到KDD2020)。论文..._stgcn matlab
微信小程序使用tensorflow做人脸识别检测卡顿的部分解决思路_tensorflow.js 微信小程序-程序员宅基地
文章浏览阅读1.4k次。在例如相机监听事件onCameraFrame里，最好是每一帧的数据更新操作上在setDate的回调里处理，，防止多次setDate，但数据还没更新完下一帧的setDate又进来，导致堵塞。清除张量，tf.dispose()在web端生效，在小程序端不能清除张量占用空间，需要挨个清除tensor.dispose()或者tf.dispose(tensor)防止内存溢出，特别是在ios上。_tensorflow.js 微信小程序
07vuex笔记 module 03_vuex模块化-程序员宅基地
文章浏览阅读119次。// App.vue<template> <div id="app"> </div></template><script>import { mapState, mapActions } from 'vuex';export default { name: 'app', computed: mapSta..._vuex模块化
TS报错整理_在赋值前使用了变量-程序员宅基地
文章浏览阅读1.6w次，点赞10次，收藏57次。记录一下最近项目中TS报错及解决一.找不到模块“images/1.png”或其相应的类型声明。报错图：原因：TS没有识别图片模块解决方法：加上图片格式声明模块????成功不报红：二.类型“unknown”上不存在属性“data”。同：类型“{}”上不存在属性“data”。报错图：原因：对象上本没有某个属性，没有语法检测到该属性（即对象属性不明确）解决方法：定义对象的接口，但是往往后端数据是不能确定的，这个时候使用第二种方法将这个对象_在赋值前使用了变量