素数圆环

全栈程序员-站长 • 2026年3月18日下午9:46 • 未分类 • 阅读 2

素数圆环素数圆环时间限制 1Sec 内存限制 32MB 题目描述如图所示为一个由 n 个圆圈构成的圆环将自然数 1 2 n 放入圆圈内并且要求任意两个相邻的圆圈内的数字之和为素数请问给你圆圈数你能给出放置自然数的所有正确方案吗注意圆圈中的数字一定是从 1 开始的并且连续不重复输入输入包含多组测试数据每组输

素数圆环

时间限制: 1 Sec 内存限制: 32 MB

题目描述

输入

输入包含多组测试数据。每组输入占一行，为整数n（0 < n<20），表示圆圈数。

输出

样例输入

样例输出

题意概括

给出一个数字n求使用1-n这n个数字组成一个素数环，第一个必须是1；

解题思路

这个题我是用的dfs暴力求解的。枚举所有情况，看哪一种情况符合就输出哪一种情况。

代码如下

#include 
      #include 
      #include 
      #include 
      #include 
      #define inf 0x3f3f3f3f using namespace std; int aa[50]; int line[30],n; int vis[30]; int date[20][30]; int sushu (int x) { int i; int k=(int)sqrt(x); for(i=2;i<=k;i++) if(x%i==0) return 0; return 1; } /*void dfs(int x) { printf("%d",line[x-1]); int i; if(x>n){ printf("*\n"); //if(date[line[n]][0]==1) // return ; printf("%d",line[1]); for(i=2;i<=n;i++){ printf(" %d",line[i]); } printf("\n"); return ; } for(i=0;date[line[x-1]][i]<=n;i++){ if(vis[date[line[x-1]][i]]==0) { vis[date[line[x-1]][i]]=1; line[x]=date[line[x-1]][i]; dfs(x+1); vis[date[line[x-1]][i]]=1; } } }*/ void dfs(int x) { int i; if(x>n){ if(aa[line[n]+1]==0) return ; printf("%d",line[1]); for(i=2;i<=n;i++) printf(" %d",line[i]); printf("\n"); return ; } for(i=0;date[line[x-1]][i]<=n;i++){ if(vis[date[line[x-1]][i]]==0){ vis[date[line[x-1]][i]]=1; line[x]=date[line[x-1]][i]; dfs(x+1); vis[date[line[x-1]][i]]=0; } } } int main () { int i,j,k; memset(aa,0,sizeof(aa)); memset(date,inf,sizeof(date)); for(i=3;i<=50;i++){ if(sushu(i)) aa[i]=1; } for(i=1;i<20;i++){ //printf("%d::",i); for(j=1,k=0;j<20;j++){ if(aa[i+j]){ date[i][k]=j; k++; // printf("%d ",date[i][k-1]); } } //printf("\n"); } int l=0; while(~scanf("%d",&n)){ l++; memset(vis,0,sizeof(vis)); vis[1]=1; line[1]=1; printf("Case %d:\n",l); dfs(2); printf("\n"); } return 0; }

转载于:https://www.cnblogs.com/lanaiwanqi/p/10445728.html

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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/211716.html原文链接：https://javaforall.net

赞 (0)

0 0

关于作者

全栈程序员-站长

133.5K 文章

3 粉丝

本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”

2021年安装包制作工具有哪些？好用的安装包制作软件推荐

上一篇 2026年3月18日下午9:46

win10双显卡怎么切换amd和英特尔_amd双显卡怎么设置_win8切换amd双显卡的方法步骤…

下一篇 2026年3月18日下午9:46

springsession使用_常见的使用null场景

springsession使用_常见的使用null场景目录一、同域名下相同项目(集群环境)实现Session共享1.思路2.架构图3.实现步骤一、同域名下相同项目(集群环境)实现Session共享在同一个域名下，比如：www.p2p.com同一个项目，部署了多台tomcat，这就是典型的集群。我们上一篇文章的入门案例就属于这种应用场景，只不过在实际开发的过程中，我们如果存在了tomcat集群，那么肯定会使用nginx进行负载均衡，那么这种情况下我们该如何处理。1.思路我们将上一个阶段的p2p项目实现集群部署下的Ses

全栈程序员-站长
2025年6月6日
4
PyCharm 打包生成exe文件

PyCharm 打包生成exe文件1 调出 Terminal 面板快捷方式 Alt F12 2 安装 pyinstaller 界面输入 pipinstallpy 执行安装 3 切换到目标目录 4 执行打包命令 pyinstaller F w 其中 F 是用于将所有的支持文件全部都打包在一起不显示其他的依赖文件 w 在程序运行的过程中隐藏后台控制的黑窗口例子 pyinstaller Fmain py5 项目目录下新生成 dist 文件夹中可查看生成的可执行文件

全栈程序员-站长
2026年3月27日
2
简谈基于FPGA的千兆以太网设计

简谈基于FPGA的千兆以太网设计简谈基于 FPGA 的千兆以太网设计今天给大侠带来简谈基于 FPGA 的千兆以太网设计话不多说上货今天我们来简单的聊一聊以太网以太网在 FPGA 学习中属于比较高级的内容了有些大侠肯定会感觉以太网学习起来非常不容易其实我可以告诉大家前期学习的基础打扎实了后期的学习也没那么难总之就是说难没那么难说容易也不是那么容易那么言归正传下面让我们一起来聊一聊以太网的学习说起以太网大家可能就会想到百兆以太网千兆以太网以及万兆以太网等等局域以太网从 10M 开始发展经历几多的变迁发展到现

全栈程序员-站长
2026年3月19日
3
全栈程序员

LangChain 框架下的 AI Agent 构建与部署实践

LangChain 框架下的 AI Agent 构建与部署实践

全栈程序员-站长
2026年3月15日
2
rpm包怎么打开(ubuntu rpm格式)

WPSOffice2019ForLinux发布11.1.0.9505版本了，在2020年4月9日提供了wps-office_11.1.0.9505_amd64.deb/rpm下载，支持X64、MIPS、ARM计算机架构。使用旧版本的用户可升级到新版本。WPSOffice2019ForLinux11.1.0.9505版更新内容1、WPS公共：支持金山会议，云上开会，协作无间。支持自…

全栈程序员-站长
2022年4月11日
76
Ai程序员

智能体（Agent）全景拆解指南：技术架构与业务实践深度解析

智能体（Agent）全景拆解指南：技术架构与业务实践深度解析

Ai探索者
2026年3月16日
3

发表回复

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