「野人过河java」野人过河小游戏中,有几种过河方法?分别描述
本篇文章给大家谈谈野人过河java，以及野人过河小游戏中,有几种过河方法?分别描述对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
java 野人过河问题
完全无难度
野人位置（X），河宽长（w）
过河方法：
runrain（x,y）{
if(x=w){
x++;
}else（）{
x=w;//刚过完河位置
}
用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;
}
}
为什么学计算机专业好多年了，就是学不会编程？
我相信很多人会有这个问题，我理解其根本原因在于学习编程和在实际场景里会编程解决问题有相当差距。比如你学习数学，在一定量的题海的辅助下加上理解原理和规律，就能开始解决实际问题，然而数学之实际问题也是习题为主，和日常生活并不大量相关。编程水平高，除了个别科学家，主要也是依靠题海战，尤其编程属于非常典型的工科，其理论知识和实践的比率大概3对7，你需要大量练习。然而，在编程的学习过程当中，你会发现学习材料和习题严重脱离实际场景，这是由于大量的学习组织者他们不是一流的实际工作者导致的。这解释了一个常见现象，书看过很多，上手什么都不会。要解决这个问题，刷题是没用的，acm也好，其他的也好。主要有两个方法，其一是去正规企业实习或者就是和前辈组成工作室，从网上接一些项目练习。主要的观点就是需要大量实际生活经验。
在JAVA中，用递规的方法求7!
;
解题时可以把渡河的过程省略掉，也就是可以忽略河的存在。
为了用 Java 解这道题，我写了 3 个类：
河边（RiverSide）、河景（RiverScene）和解题者（MACPS，即 Missionaries And Cannibals Puzzle Solver）。
问题中的传教士、野人和船都是非常简单的物件，所以就简单地用单字符字符串“m”、“c” 和 “v”来代表。
其实那三个类都很简单；它们之间的关系也很简单：
1）每个河边都能有 0 或更多的 m 和 c，及最多 1 个 v。
2）每个河景里有两个河边。
3）解题者里有两个河景：初始河景和终极河景。
解题者的任务就是要搜索出能把初始河景及终极河景连起来的河景系列。
解题者的 getSolutionSteps（ ）以递归的方式作深度优先搜索。
其它两个“类”（Combinatorics 和 Copy）都是只提供一个方法的简单类。
代码里有文档。 有不明白的地方可以问。
你可以用类似 Jacobe （）的程序恢复代码原有的缩进。
import java.util.*;
import java.io.*;
/**
* Missionaries And Cannibals Puzzle Solver.
*
* Solution to the puzzle must not violate any of the following 2 rules:
* 1) Relative headcount: cannibals can't outnumber missionaries at any point.
* 2) Boat's loading: mustn't exceed the max.
*/
public class MACPS {
public class SolutionNotFoundException extends RuntimeException
static final Object MISSIONARY = "m", // Simple representation
CANNIBAL = "c", // of objects
BOAT = "v"; // in the puzzle.
private int boat_max_load,
boat_min_load = 1; // Shouldn't be any other value.
private RiverScene firstScene,
finalScene;
// Recursively searches for a solution using Depth-First Search strategy.
// Takes a Stack containing only the first scene (root of tree).
// Returns a collection of scenes connecting the first scene to the final.
// Throws SolutionNotFoundException for obvious reason.
// Deploys the following optimization strategy:
// Transfers as much as possible from source side,
// as little as possible from target side.
private Collection getSolutionSteps( Stack takenSteps ) {
RiverScene lastScene = ( RiverScene ) takenSteps.peek( );
if( lastScene.equals( finalScene ) ) return takenSteps;
RiverScene newStep = lastScene.deepCopy( );
// To allow transfer in both directions to share the same chunk of code.
int start = boat_max_load,
stop = boat_min_load - 1,
step = -1;
RiverSide from = newStep.lside,
to = newStep.rside;
if( to.hasBoat( ) ) {
start = boat_min_load;
stop = boat_max_load + 1;
step = 1;
from = newStep.rside;
to = newStep.lside;
}
for( int nPassenger = start; nPassenger != stop; nPassenger += step ) {
Collection menCombs = new HashSet( // HashSet eliminates duplicates.
Combinatorics.combinations( from.getMenList( ), nPassenger ) );
nextComb:
for( Iterator comb = menCombs.iterator( ); comb.hasNext( ); ) {
Collection menList = ( Collection ) comb.next( );
try {
from.transferMen( to, menList );
// If it's a taken step, undo and try next combination.
for( Iterator i = takenSteps.iterator( ); i.hasNext( ); )
if( i.next( ).equals( newStep ) ) {
to.transferMen( from, menList );
continue nextComb;
}
takenSteps.push( newStep );
return getSolutionSteps( takenSteps );
}
catch( SecurityException e ) {
// Transfer didn't take place. Just try next combination.
}
catch( SolutionNotFoundException e ) {
// New step led to no solution in leaves. Undo, then next.
takenSteps.pop( );
to.transferMen( from, menList );
}
}
}
// All possible steps led to no solution, so
throw new SolutionNotFoundException( );
}
// Do setup, then kick-starts getSolutionSteps( Stack takenSteps ).
public Collection
getSolutionSteps( int nMissionary, int nCannibal, int boatCapacity ) {
if( nMissionary 0 || nCannibal 0 || boatCapacity 0 )
throw new IllegalArgumentException( "Negative argument value." );
RiverSide sourceSide = new RiverSide( nMissionary, nCannibal, true ),
targetSide = new RiverSide( 0, 0, false );
boat_max_load = boatCapacity;
firstScene = new RiverScene( sourceSide, targetSide );
finalScene = new RiverScene( targetSide, sourceSide );
if( firstScene.lside.fatal( ) ) // First scene can be valid but fatal.
throw new SolutionNotFoundException( );
Stack steps = new Stack( );
steps.push( firstScene );
return getSolutionSteps( steps );
}
public static void main( String[ ] args ) {
int nMissionary = 3,
nCannibal = 3,
boatCapacity = 2;
System.out.println(
"\nSolving the puzzle of Missionaries And Cannibals with\n" +
nMissionary + " missionaries and " + nCannibal + " cannibals " +
"and a boat that can take up to " + boatCapacity + " creatures.." );
try {
Collection steps = new MACPS( ).
getSolutionSteps( nMissionary, nCannibal, boatCapacity );
System.out.println( "\nSolution found:\n" );
for( Iterator step = steps.iterator( ); step.hasNext( ); )
System.out.println( step.next( ) + "\n" );
}
catch( SolutionNotFoundException e ) {
System.out.println( "\nNo solution found." );
}
}
}
/**
* Represents a riverside in the puzzle.
*/
class RiverSide implements Serializable {
private ArrayList men = new ArrayList( ),
boat = new ArrayList( );
public RiverSide( int nMissionary, int nCannibal, boolean withBoat ) {
men.addAll( Collections.nCopies( nMissionary, MACPS.MISSIONARY ) );
men.addAll( Collections.nCopies( nCannibal, MACPS.CANNIBAL ) );
Collections.sort( men );
if( withBoat ) boat.add( MACPS.BOAT );
}
public RiverSide deepCopy( ) {
return ( RiverSide ) Copy.deepCopy( this );
}
public Collection getMenList( ) {
return ( Collection ) Copy.deepCopy( men );
}
public boolean equals( Object otherSide ) {
RiverSide other = ( RiverSide ) otherSide;
Collections.sort( men );
Collections.sort( other.men );
return this.men.equals( other.men ) this.boat.equals( other.boat );
}
public String toString( ) {
return "BOAT" + boat + "\t" + "MEN" + men;
}
public boolean hasBoat( ) {
return ! boat.isEmpty( );
}
// Checks for violation of Rule #1.
public boolean fatal( ) {
int mCount = 0, cCount = 0;
for( Iterator i = men.iterator( ); i.hasNext( ); ) {
Object val = i.next( );
if( val.equals( MACPS.MISSIONARY ) ) ++mCount;
if( val.equals( MACPS.CANNIBAL ) ) ++cCount;
}
return mCount 0 mCount cCount;
}
// Throws SecurityException if the transfer of all men in menList
// from this to destination *will* result in violation of Rule #1.
// Else, executes the transfer.
public void transferMen( RiverSide destination, Collection menList ) {
for( Iterator i = menList.iterator( ); i.hasNext( ); )
destination.men.add( men.remove( men.indexOf( i.next( ) ) ) );
// A nice place to automate boat transfer.
_transferBoat( destination );
// Undo the transfer if it led to violation of Rule #1.
if( fatal( ) || destination.fatal( ) ) {
destination.transferMen( this, menList );
throw new SecurityException( );
}
}
// Tansfers boat from this to destination. Called only by transferMen( ).
private void _transferBoat( RiverSide destination ) {
destination.boat.add( boat.remove( 0 ) );
}
}
/**
* Combines two riversides. Serves mainly as a data object.
*/
class RiverScene implements Serializable {
RiverSide lside, rside; // Package access.
public RiverScene( RiverSide lside, RiverSide rside ) {
this.lside = lside.deepCopy( );
this.rside = rside.deepCopy( );
}
public RiverScene deepCopy( ) {
return ( RiverScene ) Copy.deepCopy( this );
}
public boolean equals( Object otherScene ) {
RiverScene other = ( RiverScene ) otherScene;
return lside.equals( other.lside ) rside.equals( other.rside );
}
public String toString( ) {
return "Left Side:\t" + lside + "\n" + "Right Side:\t" + rside;
}
}
/**
* Provides a static method to generate combinations of items taken r at a time.
*/
class Combinatorics {
public static Collection combinations( Collection items, int r ) {
if( r == 0 ) // Return [ [ ] ]. Note that [ ] denotes a List.
return Collections.nCopies( 1, new ArrayList( ) );
List copy = new ArrayList( items ), // To enable subListing of items.
result = new ArrayList( );
for( int i = 0; i copy.size( ); ++i ) {
Collection subCombs =
combinations( copy.subList( i + 1, copy.size( ) ), r - 1 );
for( Iterator iter = subCombs.iterator( ); iter.hasNext( ); ) {
// Assign [ [ items.get( i ) ] ] to subComb.
List subComb = new ArrayList( copy.subList( i, i + 1 ) );
subComb.addAll( ( List ) iter.next( ) );
result.add( subComb );
}
}
return result;
}
}
/**
* Provides a static method to perform deepcopy of object via serialization.
*/
class Copy {
public static Object deepCopy( Object o ) {
try {
ByteArrayOutputStream baos = new ByteArrayOutputStream( );
ObjectOutputStream oos = new ObjectOutputStream( baos );
oos.writeObject( o );
oos.close( );
ObjectInputStream ois =
new ObjectInputStream(
new ByteArrayInputStream( baos.toByteArray( ) ) );
return ois.readObject( );
}
catch ( Exception e ) {
throw new RuntimeException( e );
}
}
}
关于野人过河java和野人过河小游戏中,有几种过河方法?分别描述的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-11-26，除非注明，否则均为原创文章，转载请注明出处。