Java 递归、DFS、回溯
大家好，又见面了，我是你们的朋友全栈君。
DFS/回溯算法
如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖之前做出的选择），且可以用递归枚举法实现，则它的工作方式可以用解答树来描述。
全排列问题
输出数字1~N所能组成的所有全排列
public class A {
/** * 全排列 * * @param args */
static Vector<Integer> vector = new Vector<>();
static int N = 0;
static boolean[] isUsed = new boolean[100];
public static void main(String[] args) {
N = 3;
dfs(0);
}
static void dfs(int n) {
if (n >= N) {
for (Integer integer : vector) {
System.out.print(integer);
}
System.out.println();
return;
}
for (int i = 1; i <= N; i++) {
if (isUsed[i]) {
continue;
}
vector.add(i);
isUsed[i] = true;
dfs(n + 1);
Integer integer = vector.lastElement();
vector.remove(integer);
isUsed[i] = false;
}
}
}素数环问题
将1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
例如数字1-6所组成的一个素数环，用数组表示是[1, 4, 3, 2, 5, 6]（第一位固定为1）
图一：
图二、
public class B {
static int N = 6;
static Vector<Integer> vector = new Vector<>();
static boolean[] isUsed = new boolean[100];
/** * 1 - n 之间的 * 素数环 * * @param args */
public static void main(String[] args) {
System.out.println(8 & 1);
vector.add(1);
dfs(1);
}
static void dfs(int n) {
// 打印结果
if (n >= N) {
int temp = vector.firstElement() + vector.lastElement();
if (isPri(temp) == false) {
return;
}
for (Integer integer : vector) {
System.out.print(integer);
}
System.out.println();
}
for (int i = 2; i <= N; i++) {
if (isUsed[i]) {
continue;
}
int temp = vector.get(n - 1) + i;
// 剪枝
if (isPri(temp) == false) continue;
vector.add(i);
isUsed[i] = true;
dfs(n + 1);
isUsed[i] = false;
Integer lastElement = vector.lastElement();
vector.remove(lastElement);
}
}
static boolean isPri(int n) {
int ans = n & 1;
if (ans == 0) {
return false;
} else {
return true;
}
}
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/156770.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
