正文
关于java划船代码的信息
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
用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;
}
}
相关问答
Q1: 用JAVA编一个关于猛兽过河问题的程序
六种动物过河,是大小虎,大小豹,大小熊,大熊大狮大虎小熊会划船,只有一只船并且一次只能载两只动物,注意，小的旁边如果有其他大的而没有自己大的就会被欺负(大不吃大,小不吃小),怎么能使它们全过河?（最好有原代码提供，谢了~~）
附：
猛兽过河的过程为：
第一步：小熊和小虎过去————小雄回来送船
第二步：小熊和小豹过去————小熊回来送船
第三步：大豹子和大虎过去————大虎和小虎送船
第四步：小熊和大熊过去--------大豹和小豹回来送船
第五步：大豹和大虎过去-------小熊回来送船
第六步：小熊和小虎过去---------小熊回来
第七步:小熊和小豹过去
微软的一条面试题（和猛兽过河问题很相似,供参考）：
三只母鸡，三只小鸡在河东岸，一条小舟每次最多载两只鸡（大小不论）。
条件：
1、母鸡都会划船。
2、只有一只小鸡会划船，其余两只不会。
3、当小鸡母亲不在身边时，其余母鸡就会啄死这只小鸡。
其算法为：
int 过河前数组,把鸡放进去
int 过河后数组
再定义一个结构
{鸡1;
鸡2;
int *pnext;
}
及结构指针
结构指针开辟内存
void 过河(过河前数组,过河后数组,结构指针)
{if(过河前数组全为0)
{输出链表中的内容
return;
}
else
{ int i,j,m,n;
int temp过河前数组;
int temp过河后数组;
temp过河前数组=过河前数组;
temp过河后数组=过河后数组
for(i=0;i上标-1;i++)
for(j=i+1;j上标;j++)
{m=过河前数组[i];
n=过河前数组[j];
if(判取出两个数后剩下的数及这两个数满足过河条件别忘了判这两个数与过河后数组满不满足)
{把m,n放入结构;
if(判结构指针中的pnext是否为null)
是结构指针开辟内存 形成新结构组成链表;
否就把指针向下移;
把m,n放入temp过河后数组
temp过河前数组中把m,n变为0;
回河(temp过河前数组,temp过河后数组,结构指针);
}
}
}
}
void 回河(过河前数组,过河后数组,结构指针)
{int i,j,m,n;
int temp过河前数组;
int temp过河后数组;
int temp结构指针=结构指针;
temp过河前数组=过河前数组;
temp过河后数组=过河后数组;
for(i=0;i上标-1;i++)
for(j=i+1;j上标;j++)
{m=过河后数组[i];
n=过河后数组[j];
if(判取出2个数后剩下的数及这两个数满足回河条件别忘了判这2个数与过河前数组满不满足)
{把m,n放入结构;
if(判结构指针中的pnext是否为null)
是开辟内存 形成新结构组成链表;
否就把指针向下移;
把m,n放入temp过河前数组
temp过河后数组中把m,n变为0;
过河(temp过河前数组,temp过河后数组,结构指针);
}
}
temp过河前数组=过河前数组;
temp过河后数组=过河后数组;
for(i=0;i上标-1;i++)
{m=过河后数组[i];
if(判取出1个数后剩下的数及这1个数满足回河条件别忘了判这1个数与过河前数组满不满足)
{if(判temp结构指针中的pnext是否为null)
是开辟内存 形成新结构组成链表;
否就把指针向下移;
把m放入temp过河前数组
temp过河后数组中把m变为0;
过河(temp过河前数组,temp过河后数组,temp结构指针);
}
}
急求！！！
Q2: 三个商人各带一个随从乘船过河，一只小船只能容纳2人，由他们自己划船。编程序。算法框图。（流程图）
1，两个随从过去，一个随从回来。
2，再两个随从过去，一个随从回来。
3，两个商人过去，一个随从和一个商人回来。（这步是重点）
4，两个商人过去，一个随从回来。
5，两个随从过去，一个随从回来。
6，最后两个随从过去。
ok！
Q3: 猴子过河 java算法
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class Monkey {
public String[] monkeys = { "a", "b", "c", "A", "B", "C" };
Rule rule1 = new Rule1();
Rule rule2 = new Rule2();
public int count = 0;
public StringBuffer success = new StringBuffer(2000);
public void boat() {
StackString left = new StackString();
StackString right = new StackString();
for (int i = 0; i monkeys.length; i++) {
left.add(monkeys[i]);
}
go(left, right, "");
System.out.println("***********************共" + count + "种成功方案***********************");
System.out.println(success.toString());
System.out.println("***********************共" + count + "种成功方案***********************");
}
private void go(StackString left, StackString right, String s) {
for (int i = 0; i left.size(); i++) {
String monkey1 = left.get(i);
for (int j = i + 1; j left.size(); j++) {
StringBuffer sb = new StringBuffer();
String monkey2 = left.get(j);
sb.append(s);
sb.append(monkey1);
sb.append(monkey2);
sb.append("-");
sb.append(" ");
if ((rule1.isCanBoat(monkey1, monkey2, sb)) (rule2.isCanBoat(monkey1, monkey2, sb))) {
StackString nextLeft = new StackString();
StackString nextRight = new StackString();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.remove(monkey1);
nextLeft.remove(monkey2);
nextRight.push(monkey1);
nextRight.push(monkey2);
if (nextLeft.size() == 0) {
success.append(sb.toString() + nextLeft.toString() + nextRight.toString());
success.append("\n");
count++;
continue;
}
back(nextLeft, nextRight, sb.toString());
}
}
}
}
private void back(StackString left, StackString right, String s) {
for (int i = 0; i right.size(); i++) {
String monkey1 = right.get(i);
StringBuffer sb = new StringBuffer();
sb.append(s);
sb.append(monkey1);
sb.append("-");
sb.append(" ");
if (rule2.isCanBoat(monkey1, monkey1, sb)) {
StackString nextLeft = new StackString();
StackString nextRight = new StackString();
nextLeft.addAll(left);
nextRight.addAll(right);
nextLeft.push(monkey1);
nextRight.remove(monkey1);
go(nextLeft, nextRight, sb.toString());
}
}
}
public static void main(String[] args) {
Monkey monkey = new Monkey();
monkey.boat();
}
}
interface Rule {
boolean isCanBoat(String m1, String m2, StringBuffer sb);
}
class Rule1 implements Rule {
String[] childMonkeys = { "a", "b", "c" };
String[] monkeys = { "A", "B", "C" };
public boolean isCanBoat(String m1, String m2, StringBuffer sb) {
if (m1.toLowerCase().equals(m2.toLowerCase())) {
return true;
}
ListString childMonkeysList = Arrays.asList(childMonkeys);
ListString monkeysList = Arrays.asList(monkeys);
if ((monkeysList.contains(m1) monkeysList.contains(m2))
|| (childMonkeysList.contains(m1) childMonkeysList.contains(m2))) {
return true;
}
sb.append("大猴欺负小猴java划船代码！");
System.out.println(sb.toString());
return false;
}
}
class Rule2 implements Rule {
String[] smartMonkeys = { "A", "B", "C", "a" };
public boolean isCanBoat(String m1, String m2, StringBuffer sb) {
ListString smartMonkeysList = Arrays.asList(smartMonkeys);
if (smartMonkeysList.contains(m1) || smartMonkeysList.contains(m2)) {
return true;
}
sb.append("没有会划船java划船代码的猴子java划船代码！");
System.out.println(sb.toString());
return false;
}
}
Q4: 五一班的25名学生去公园划船，每条大船限坐4人，每条小船限坐3人，如果每条船都不能有空位，有多少种？
如果只是求大船小船的租用数量，那比较简单，两种方案。
如果要计算25名学生坐船的分组方案，这就是个组合问题。
两个问题一起求解，编程计算，结果如下：
附：fortran代码
关于java划船代码和的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
