用java实现野人传教士过河问题

//CrossRiverQuestionjava

import javautilArrayList;

import javautilList;

public class CrossRiverQuestion {

    public static void main(String[] args) {

        CrossRiverQuestion q = new CrossRiverQuestion(5, 4);

        qsolveQuestion();

    }

    private int peoNum;

    private int savageNum;

    private List<Node> resultList = new ArrayList<Node>();

    public List<Node> solveQuestion() {

        Node n = new Node(peoNum,savageNum,0,0,0,new ArrayList<Integer>(),0,0);

        boolean dfsResult = dfs(n);

        if(dfsResult) {

            resultListadd(0,n);

            for(Node node : resultList) {

                Systemoutprintln("左岸传教士："+nodegetLeftPeo()+"左岸野人： "+nodegetLeftSavage()+" 右岸传教士： "+nodegetRightPeo()+"右岸野人："+nodegetRightSavage()+"船上传教士："+nodegetOnBoatPeoNum()+"船上野人："+nodegetOnBoatSavageNum());

            }

            return resultList;

        }

        return null;

    }

    

    public CrossRiverQuestion(int peoNum, int savageNum) {

        super();

        thispeoNum = peoNum;

        thissavageNum = savageNum;

    }

    private boolean dfs(Node n) {

        if(nhasVisited()) return false;

        naddCheckSum();

        if(ngetLeftPeo()==0&&ngetLeftSavage()==0) return true;

        if(ngetLeftPeo()<0||ngetRightPeo()<0||ngetLeftSavage()<0||ngetRightSavage()<0) {

            return false;

        }

        if(ngetLeftPeo()<ngetLeftSavage()&&ngetLeftPeo()>0) return false;

        if(ngetRightPeo()<ngetRightSavage()&&ngetRightPeo()>0) return false;

        if(ngetCURR_STATE()==ngetStateBoatLeft()) {

            Node n1 = new Node(ngetLeftPeo()-1,ngetLeftSavage()-1,ngetRightPeo()+1,ngetRightSavage()+1,ngetStateBoatRight(),ngetNodesCheckSum(),1,1);

            if(dfs(n1)) {

                resultListadd(0,n1);

                return true;

            }

            Node n4 = new Node(ngetLeftPeo()-2,ngetLeftSavage(),ngetRightPeo()+2,ngetRightSavage(),ngetStateBoatRight(),ngetNodesCheckSum(),2,0);

            if(dfs(n4)) {

                resultListadd(0,n4);

                return true;

            }

            Node n5 = new Node(ngetLeftPeo(),ngetLeftSavage()-2,ngetRightPeo(),ngetRightSavage()+2,ngetStateBoatRight(),ngetNodesCheckSum(),0,2);

            if(dfs(n5))  {

                resultListadd(0,n5);

                return true;

            }

        } 

        else {

            Node n6 = new Node(ngetLeftPeo(),ngetLeftSavage()+1,ngetRightPeo(),ngetRightSavage()-1,ngetStateBoatLeft(),ngetNodesCheckSum(),0,1);

            if(dfs(n6)) {

                resultListadd(0,n6);

                return true;

            }

            Node n7 = new Node(ngetLeftPeo()+1,ngetLeftSavage(),ngetRightPeo()-1,ngetRightSavage(),ngetStateBoatLeft(),ngetNodesCheckSum(),1,0);

            if(dfs(n7)) {

                resultListadd(0,n7);

                return true;

            }

            Node n1 = new Node(ngetLeftPeo()+1,ngetLeftSavage()+1,ngetRightPeo()-1,ngetRightSavage()-1,ngetStateBoatLeft(),ngetNodesCheckSum(),1,1);

            if(dfs(n1)) {

                resultListadd(0,n1);

                return true;

            }

            Node n4 = new Node(ngetLeftPeo()+2,ngetLeftSavage(),ngetRightPeo()-2,ngetRightSavage(),ngetStateBoatLeft(),ngetNodesCheckSum(),2,0);

            if(dfs(n4)) {

                resultListadd(0,n4);

                return true;

            }

            Node n5 = new Node(ngetLeftPeo(),ngetLeftSavage()+2,ngetRightPeo(),ngetRightSavage()-2,ngetStateBoatLeft(),ngetNodesCheckSum(),0,2);

            if(dfs(n5))  {

                resultListadd(0,n5);

                return true;

            }

        }

        return false;

    }

    public List<Node> getResultList() {

        return resultList;

    }

    

}

Nodejava

import javautilArrayList;

import javautilList;

public class Node {

    private List<Integer> nodesCheckSum = new ArrayList<Integer>();

    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) {

        thisCURR_STATE = state;

        thisleftPeo = leftPeo;

        thisleftSavage = leftSavage;

        thisrightPeo = rightPeo;

        thisrightSavage = rightSavage;

        thisnodesCheckSumaddAll(checkSumList);

        thisonBoatPeoNum = onBoatPeoNum;

        thisonBoatSavageNum = onBoatSavageNum;

    }

    public int getLeftPeo() {

        return leftPeo;

    }

    public void setLeftPeo(int leftPeo) {

        thisleftPeo = leftPeo;

    }

    public int getRightPeo() {

        return rightPeo;

    }

    public void setRightPeo(int rightPeo) {

        thisrightPeo = rightPeo;

    }

    public int getLeftSavage() {

        return leftSavage;

    }

    public void setLeftSavage(int leftSavage) {

        thisleftSavage = leftSavage;

    }

    public int getRightSavage() {

        return rightSavage;

    }

    public void setRightSavage(int rightSavage) {

        thisrightSavage = 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 1getCURR_STATE()+10getLeftPeo()+100getLeftSavage()+1000getRightPeo()+10000getRightSavage();

    }

    public void addCheckSum() {

        int checkSum = calcCheckSum();

        nodesCheckSumadd(checkSum);

    }

    public boolean hasVisited() {

        int sum = calcCheckSum();

        for (Integer checkSum : nodesCheckSum) {

            if(checkSum==sum) return true;

        }

        return false;

    }

    public List<Integer> getNodesCheckSum() {

        return nodesCheckSum;

    }

    public int getOnBoatPeoNum() {

        return onBoatPeoNum;

    }

    public void setOnBoatPeoNum(int onBoatPeoNum) {

        thisonBoatPeoNum = onBoatPeoNum;

    }

    public int getOnBoatSavageNum() {

        return onBoatSavageNum;

    }

    public void setOnBoatSavageNum(int onBoatSavageNum) {

        thisonBoatSavageNum = onBoatSavageNum;

    }

    

}

问题：

有3个传教士和3个野人要过河，只有一艘船，这艘船每次只能载2个人过河，且无论哪边野人的数量大于传教士的数量时，野人就会吃掉传教士。怎样让他们都安全过河？

C语言源代码：

#include <stdioh>

#include <stringh>

#define STEP_MAX 20 //来回过河的次数

#define KIND_NUM 3 //每个种类的数量

#define BOAT_NUM 2 //船的载重量

typedef enum

{

BOAT_THIS,//船在本岸

BOAT_THAT,//船在对岸

} boat_t;

typedef enum

{

ROAD_GO,//过河

ROAD_COME,//回来

} road_t;

typedef struct

{

int ye;//对岸野人数量

int man;//对岸传教士数量

boat_t boat;//船是否在对岸

} state_t;//一种局面

typedef struct

{

int ye;//野人过河数量

int man;//传教士过河的数量

road_t road;//回来或过河

} step_t;//一个步骤

state_t states[STEP_MAX]={0};

step_t steps[STEP_MAX]={0};

//判断所有的野人和传教士是否都到了对岸

bool final(state_t s)

{

const state_t cs=

{

KIND_NUM,

KIND_NUM,

BOAT_THAT

};

if(memcmp(&cs,&s,sizeof(state_t))==0)

{

return true;

}

return false;

}

//是否会发生野人杀传教士

bool bad(state_t s)

{

if(((KIND_NUM-sye)>(KIND_NUM-sman) && (KIND_NUM-sman)>0)

||(sye>sman && sman>0))

{

return true;

}

return false;

}

//第n种局面是否跟前面的相重复

bool repeat(state_t s[],int n)

{

int i;

for (i = 0; i < n; i++)

{//已经有这种情况了

if (memcmp(&states[i], &states[n], sizeof(states[i])) == 0)

{

return true;

}

}

return false;

}

void output(step_t steps[STEP_MAX],int n)

{

char kinds[KIND_NUM]={"野人","传教士"};

char routine[2]={"过河","回来"};

int i;

for (i = 0; i < n; i++)

{

if((steps[i]ye steps[i]man)>0)

{

printf("%d个%s和%d个%s%s\n",steps[i]ye,kinds[0],

steps[i]man,kinds[1],routine[steps[i]road]);

}

else if(steps[i]ye>0)

{

printf("%d个%s%s\n",steps[i]ye,kinds[0],

routine[steps[i]road]);

}

else if(steps[i]man>0)

{

printf("%d个%s%s\n",steps[i]man,kinds[1],

routine[steps[i]road]);

}

}

printf("\n");

}

//搜索过河方案(n表示过河次数)

void search(int n)

{

int i,j;

if(n>STEP_MAX)

{//步数限制太少了

printf("Step Overflow!");

return;

}

if(final(states[n]))

{//都到对岸了

output(steps,n);

return;

}

if(bad(states[n]))

{//发生了野人杀传教士了

return;

}

if(repeat(states,n))

{//与前面的局面相重复了

return;

}

if(states[n]boat==BOAT_THIS)

{//船在本岸

for (i = 0; i <= BOAT_NUM && i<=(KIND_NUM-states[n]ye); i++)

for (j = 0; j <= BOAT_NUM-i && j<=(KIND_NUM-states[n]man); j++)

{

if(i==0 &&j==0)

{

continue;

}

steps[n]ye=i;

steps[n]man=j;

steps[n]road=ROAD_GO;

memcpy(&states[n+1], &states[n], sizeof(state_t));

states[n+1]ye+=i;

states[n+1]man+=j;

states[n+1]boat=BOAT_THAT;

search(n+1);

}

}

else

{

for (i = 0; i <= BOAT_NUM && i<=states[n]ye; i++)

for (j = 0; j <= BOAT_NUM-i && j<=states[n]man; j++)

{

if(i==0 &&j==0)

{

continue;

}

steps[n]ye=i;

steps[n]man=j;

steps[n]road=ROAD_COME;

memcpy(&states[n+1], &states[n], sizeof(state_t));

states[n+1]ye-=i;

states[n+1]man-=j;

states[n+1]boat=BOAT_THIS;

search(n+1);

}

}

}

int main()

{

search(0);

return 0;

}

首先一个传教士和一个野人过河到右岸，然后传教士划船回来，再渡一个野人，到右岸后传教士下船，野人划船回到左岸将第二个传教士渡到右岸，然后第二个传教士下船，这个野人再划船回到左岸将最后一个传教士渡过到右岸，然后野人下船，传教士划船到左岸将最后一个野人渡到右岸

以上就是关于用java实现野人传教士过河问题全部的内容，包括:用java实现野人传教士过河问题、人工智能用启发式搜索解决传教士-野人（M-C）问题！环境：matlab/Vc 要可运行程序 谢谢！、设有3个传教士和3个野人，同在河的左岸，他们都要到对岸去，河里只有一条船，他们都会划船，但每次渡船等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！