「深度搜索java」深度搜索ios官方下载
本篇文章给大家谈谈深度搜索java，以及深度搜索ios官方下载对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
用java实现野人传教士过河问题
//CrossRiverQuestion.java
import java.util.ArrayList;
import java.util.List;
public class CrossRiverQuestion {
public static void main(String[] args) {
CrossRiverQuestion q = new CrossRiverQuestion(5, 4);
q.solveQuestion();
}
private int peoNum;
private int savageNum;
private ListNode resultList = new ArrayListNode();
public ListNode solveQuestion() {
Node n = new Node(peoNum,savageNum,0,0,0,new ArrayListInteger(),0,0);
boolean dfsResult = dfs(n);
if(dfsResult) {
resultList.add(0,n);
for(Node node : resultList) {
System.out.println("左岸传教士："+node.getLeftPeo()+"左岸野人： "+node.getLeftSavage()+" 右岸传教士： "+node.getRightPeo()+"右岸野人："+node.getRightSavage()+"船上传教士："+node.getOnBoatPeoNum()+"船上野人："+node.getOnBoatSavageNum());
}
return resultList;
}
return null;
}
public CrossRiverQuestion(int peoNum, int savageNum) {
super();
this.peoNum = peoNum;
this.savageNum = savageNum;
}
private boolean dfs(Node n) {
if(n.hasVisited()) return false;
n.addCheckSum();
if(n.getLeftPeo()==0n.getLeftSavage()==0) return true;
if(n.getLeftPeo()0||n.getRightPeo()0||n.getLeftSavage()0||n.getRightSavage()0) {
return false;
}
if(n.getLeftPeo()n.getLeftSavage()n.getLeftPeo()0) return false;
if(n.getRightPeo()n.getRightSavage()n.getRightPeo()0) return false;
if(n.getCURR_STATE()==n.getStateBoatLeft()) {
Node n1 = new Node(n.getLeftPeo()-1,n.getLeftSavage()-1,n.getRightPeo()+1,n.getRightSavage()+1,n.getStateBoatRight(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()-2,n.getLeftSavage(),n.getRightPeo()+2,n.getRightSavage(),n.getStateBoatRight(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()-2,n.getRightPeo(),n.getRightSavage()+2,n.getStateBoatRight(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
else {
Node n6 = new Node(n.getLeftPeo(),n.getLeftSavage()+1,n.getRightPeo(),n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),0,1);
if(dfs(n6)) {
resultList.add(0,n6);
return true;
}
Node n7 = new Node(n.getLeftPeo()+1,n.getLeftSavage(),n.getRightPeo()-1,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),1,0);
if(dfs(n7)) {
resultList.add(0,n7);
return true;
}
Node n1 = new Node(n.getLeftPeo()+1,n.getLeftSavage()+1,n.getRightPeo()-1,n.getRightSavage()-1,n.getStateBoatLeft(),n.getNodesCheckSum(),1,1);
if(dfs(n1)) {
resultList.add(0,n1);
return true;
}
Node n4 = new Node(n.getLeftPeo()+2,n.getLeftSavage(),n.getRightPeo()-2,n.getRightSavage(),n.getStateBoatLeft(),n.getNodesCheckSum(),2,0);
if(dfs(n4)) {
resultList.add(0,n4);
return true;
}
Node n5 = new Node(n.getLeftPeo(),n.getLeftSavage()+2,n.getRightPeo(),n.getRightSavage()-2,n.getStateBoatLeft(),n.getNodesCheckSum(),0,2);
if(dfs(n5)) {
resultList.add(0,n5);
return true;
}
}
return false;
}
public ListNode getResultList() {
return resultList;
}
}
Node.java
import java.util.ArrayList;
import java.util.List;
public class Node {
private ListInteger nodesCheckSum = new ArrayListInteger();
private int leftPeo;
private int rightPeo;
private int leftSavage;
private int rightSavage;
private int CURR_STATE = 0;
private int onBoatPeoNum = 0;
private int onBoatSavageNum = 0;
private final int STATE_BOAT_LEFT = 0;
private final int STATE_BOAT_RIGHT = 1;
public Node(int leftPeo, int leftSavage, int rightPeo, int rightSavage, int state, List checkSumList, int onBoatPeoNum, int onBoatSavageNum) {
this.CURR_STATE = state;
this.leftPeo = leftPeo;
this.leftSavage = leftSavage;
this.rightPeo = rightPeo;
this.rightSavage = rightSavage;
this.nodesCheckSum.addAll(checkSumList);
this.onBoatPeoNum = onBoatPeoNum;
this.onBoatSavageNum = onBoatSavageNum;
}
public int getLeftPeo() {
return leftPeo;
}
public void setLeftPeo(int leftPeo) {
this.leftPeo = leftPeo;
}
public int getRightPeo() {
return rightPeo;
}
public void setRightPeo(int rightPeo) {
this.rightPeo = rightPeo;
}
public int getLeftSavage() {
return leftSavage;
}
public void setLeftSavage(int leftSavage) {
this.leftSavage = leftSavage;
}
public int getRightSavage() {
return rightSavage;
}
public void setRightSavage(int rightSavage) {
this.rightSavage = rightSavage;
}
@Override
public String toString() {
return leftPeo+","+leftSavage+","+rightPeo+","+rightSavage+","+CURR_STATE;
}
public int getCURR_STATE() {
return CURR_STATE;
}
public void setCURR_STATE(int cURR_STATE) {
CURR_STATE = cURR_STATE;
}
public int getStateBoatLeft() {
return STATE_BOAT_LEFT;
}
public int getStateBoatRight() {
return STATE_BOAT_RIGHT;
}
public int calcCheckSum() {
return 1*getCURR_STATE()+10*getLeftPeo()+100*getLeftSavage()+1000*getRightPeo()+10000*getRightSavage();
}
public void addCheckSum() {
int checkSum = calcCheckSum();
nodesCheckSum.add(checkSum);
}
public boolean hasVisited() {
int sum = calcCheckSum();
for (Integer checkSum : nodesCheckSum) {
if(checkSum==sum) return true;
}
return false;
}
public ListInteger getNodesCheckSum() {
return nodesCheckSum;
}
public int getOnBoatPeoNum() {
return onBoatPeoNum;
}
public void setOnBoatPeoNum(int onBoatPeoNum) {
this.onBoatPeoNum = onBoatPeoNum;
}
public int getOnBoatSavageNum() {
return onBoatSavageNum;
}
public void setOnBoatSavageNum(int onBoatSavageNum) {
this.onBoatSavageNum = onBoatSavageNum;
}
}
编写一个Java程序 用1、2、3、4这四个数组成一个四位数，要求每位不能重复，输出其所有组合
方法1：
public class PaiLie {// 对一组数字进行全排列
public static void main(String[] args) {
int a[] = new int[5];
for (int i = 1; i a.length; i++)
a[i] = i;
pailie(a, 1);
}
public static void pailie(int[] a, int n) {// n 待交换数的索引
if (n a.length - 1) {
for (int i = n; i a.length; i++) {
int temp = a[i];
for (int k = i; k n; k--)
a[k] = a[k - 1];
a[n] = temp; // 把该段最右面的数移到最左面
pailie(a, n + 1);
// 还原原来序列
for (int k = n; k i; k++)
a[k] = a[k + 1];
a[i] = temp;
}
} else {
for (int j = 1; j a.length; j++)
System.out.print(a[j] + " ");
System.out.println();
}
}
}
方法2：
public class PaiLie_2 {
public static void main(String[] args) {
final int N = 4;
int a[] = new int[N + 1];
for (int i = 1; i a.length; i++)
a[i] = i;
pailie(a, 1, N);
} // 产生a[m:n]的所有排列
public static void pailie(int[] a, int m, int n) {
if (m == n) {
for (int j = 1; j = n; j++)
System.out.print(a[j] + " ");
System.out.println();
} else
for (int i = m; i = n; i++) {
swap(a, m, i);
pailie(a, m + 1, n);
swap(a, m, i);
}
}
// 交换数组中两个位置上的元素
public static void swap(int[] number, int i, int j) {
int t;
t = number[i];
number[i] = number[j];
number[j] = t;
}
}
java 深度优先搜索（回溯法）求集合的幂集
import java.util.ArrayList;
import java.util.List;
public class BackTrack {
public static void main(String[] args) {
//初始化一个集合，放在list里面
ListString list=new ArrayListString();
list.add("1");
list.add("2");
list.add("3");
list.add("f");
ListString li=new ArrayListString();
PowerSet(0,list,li);
}
//回溯法求幂集
public static void PowerSet(int i,ListString list,ListString li){
if(ilist.size()-1){System.out.println(li);}
else{
li.add(list.get(i));//左加
PowerSet(i+1,list,li); //递归方法
li.remove(list.get(i)); //右去
PowerSet(i+1, list, li);
}
}
}
注：该方法采用中序遍历二叉树（实际这棵树是不存在的）。对于第一个元素，左节点加进去，右节点去掉。对于第i一个节点，左加，右去。直到i大于元素的总个数。
输出结果：
[1, 2, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 2]
[1, 3, 4]
[1, 3]
[1, 4]
[1]
[2, 3, 4]
[2, 3]
[2, 4]
[2]
[3, 4]
[3]
[4]
[]
深度搜索java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于深度搜索ios官方下载、深度搜索java的信息别忘了在本站进行查找喔。