魔法師過河java代碼 魔法師過河java代碼怎么寫

猴子過河 java算法

import?java.util.Arrays;

創(chuàng)新互聯(lián)公司長期為1000多家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為迎江企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)，迎江網(wǎng)站改版等技術(shù)服務(wù)。擁有10年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

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("大猴欺負(fù)小猴！");

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("沒有會劃船的猴子！");

System.out.println(sb.toString());

return?false;

}

}

用JAVA編一個關(guān)于猛獸過河問題的程序

六種動物過河,是大小虎,大小豹,大小熊,大熊大獅大虎小熊會劃船,只有一只船并且一次只能載兩只動物,注意，小的旁邊如果有其他大的而沒有自己大的就會被欺負(fù)(大不吃大,小不吃小),怎么能使它們?nèi)^河?（最好有原代碼提供，謝了~~）

附：

猛獸過河的過程為：

第一步：小熊和小虎過去————小雄回來送船

第二步：小熊和小豹過去————小熊回來送船

第三步：大豹子和大虎過去————大虎和小虎送船

第四步：小熊和大熊過去--------大豹和小豹回來送船

第五步：大豹和大虎過去-------小熊回來送船

第六步：小熊和小虎過去---------小熊回來

第七步:小熊和小豹過去

微軟的一條面試題（和猛獸過河問題很相似,供參考）：

三只母雞，三只小雞在河?xùn)|岸，一條小舟每次最多載兩只雞（大小不論）。

條件：

1、母雞都會劃船。

2、只有一只小雞會劃船，其余兩只不會。

3、當(dāng)小雞母親不在身邊時，其余母雞就會啄死這只小雞。

其算法為：

int 過河前數(shù)組,把雞放進(jìn)去

int 過河后數(shù)組

再定義一個結(jié)構(gòu)

{雞1;

雞2;

int *pnext;

}

及結(jié)構(gòu)指針

結(jié)構(gòu)指針開辟內(nèi)存

void 過河(過河前數(shù)組,過河后數(shù)組,結(jié)構(gòu)指針)

{if(過河前數(shù)組全為0)

{輸出鏈表中的內(nèi)容

return;

}

else

{ int i,j,m,n;

int temp過河前數(shù)組;

int temp過河后數(shù)組;

temp過河前數(shù)組=過河前數(shù)組;

temp過河后數(shù)組=過河后數(shù)組

for(i=0;i上標(biāo)-1;i++)

for(j=i+1;j上標(biāo);j++)

{m=過河前數(shù)組[i];

n=過河前數(shù)組[j];

if(判取出兩個數(shù)后剩下的數(shù)及這兩個數(shù)滿足過河條件別忘了判這兩個數(shù)與過河后數(shù)組滿不滿足)

{把m,n放入結(jié)構(gòu);

if(判結(jié)構(gòu)指針中的pnext是否為null)

是結(jié)構(gòu)指針開辟內(nèi)存 形成新結(jié)構(gòu)組成鏈表;

否就把指針向下移;

把m,n放入temp過河后數(shù)組

temp過河前數(shù)組中把m,n變?yōu)?;

回河(temp過河前數(shù)組,temp過河后數(shù)組,結(jié)構(gòu)指針);

}

}

}

}

void 回河(過河前數(shù)組,過河后數(shù)組,結(jié)構(gòu)指針)

{int i,j,m,n;

int temp過河前數(shù)組;

int temp過河后數(shù)組;

int temp結(jié)構(gòu)指針=結(jié)構(gòu)指針;

temp過河前數(shù)組=過河前數(shù)組;

temp過河后數(shù)組=過河后數(shù)組;

for(i=0;i上標(biāo)-1;i++)

for(j=i+1;j上標(biāo);j++)

{m=過河后數(shù)組[i];

n=過河后數(shù)組[j];

if(判取出2個數(shù)后剩下的數(shù)及這兩個數(shù)滿足回河條件別忘了判這2個數(shù)與過河前數(shù)組滿不滿足)

{把m,n放入結(jié)構(gòu);

if(判結(jié)構(gòu)指針中的pnext是否為null)

是開辟內(nèi)存 形成新結(jié)構(gòu)組成鏈表;

否就把指針向下移;

把m,n放入temp過河前數(shù)組

temp過河后數(shù)組中把m,n變?yōu)?;

過河(temp過河前數(shù)組,temp過河后數(shù)組,結(jié)構(gòu)指針);

}

}

temp過河前數(shù)組=過河前數(shù)組;

temp過河后數(shù)組=過河后數(shù)組;

for(i=0;i上標(biāo)-1;i++)

{m=過河后數(shù)組[i];

if(判取出1個數(shù)后剩下的數(shù)及這1個數(shù)滿足回河條件別忘了判這1個數(shù)與過河前數(shù)組滿不滿足)

{if(判temp結(jié)構(gòu)指針中的pnext是否為null)

是開辟內(nèi)存 形成新結(jié)構(gòu)組成鏈表;

否就把指針向下移;

把m放入temp過河前數(shù)組

temp過河后數(shù)組中把m變?yōu)?;

過河(temp過河前數(shù)組,temp過河后數(shù)組,temp結(jié)構(gòu)指針);

}

}

急求?。?！

用java實(shí)現(xiàn)野人傳教士過河問題

//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;

}

}

文章標(biāo)題：魔法師過河java代碼 魔法師過河java代碼怎么寫
當(dāng)前URL：http://bm7419.com/article26/dohjicg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、網(wǎng)站導(dǎo)航、、自適應(yīng)網(wǎng)站、全網(wǎng)營銷推廣、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)