【DFS】素数环问题
2023-03-14 09:45:07 时间
题目:
输入正整数n,对1-n进行排列,使得相邻两个数之和均为素数,输出时从整数1开始,逆时针排列。同一个环应恰好输出一次。n<=16
如输入:
6
输出:
1 4 3 2 5 6 1 6 5 2 3 4
代码:
1 import java.util.Scanner; 2 3 public class 素数环 { 4 5 public static void main(String[] args) { 6 Scanner sc = new Scanner(System.in); 7 int n = sc.nextInt(); 8 int[] r = new int[n]; 9 r[0] = 1; 10 dfs(n, r, 1); 11 } 12 13 private static void dfs(int n, int[] r, int cur) { 14 if (cur == n && isP(r[0] + r[n - 1])) {// 填到末尾了,还有首尾相加为素数才算成功 15 print(r); 16 return; 17 } 18 19 for (int i = 2; i <= n; i++) {// 尝试用每个数字填到cur这个位置 20 if (check(r, i, cur)) {// r中没有i这个数,且和上一个数之和为素数 21 r[cur] = i;// 试着将i放在cur位置,往前走一步 22 dfs(n, r, cur + 1); 23 r[cur] = 0;// 回溯 这里回不回溯都可以 24 } 25 26 } 27 } 28 29 private static void print(int[] r) { 30 for (int i = 0; i < r.length; i++) { 31 System.out.print(r[i] + (i == r.length - 1 ? "" : " ")); 32 } 33 System.out.println(); 34 } 35 36 private static boolean check(int[] r, int i, int cur) { 37 for (int e : r) { 38 if (e == i || !isP(r[cur - 1] + i)) 39 return false; 40 } 41 return true; 42 } 43 44 private static boolean isP(int k) { 45 for (int i = 2; i * i <= k; i++) { 46 if (k % i == 0) 47 return false; 48 } 49 return true; 50 51 } 52 53 }
结果:
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的