農(nóng)夫過(guò)河問(wèn)題的求解

#includeiostream.h

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到容城網(wǎng)站設(shè)計(jì)與容城網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、網(wǎng)站空間、企業(yè)郵箱。業(yè)務(wù)覆蓋容城地區(qū)。

#includestdio.h

#defineMAXNUM 20

typedefstruct //順序隊(duì)列類型定義

{

int f, r; //f表示頭，r 表示尾

int q[MAXNUM];//順序隊(duì)

}SeqQueue,*PSeqQueue;

PSeqQueuecreateEmptyQueue_seq( ) //創(chuàng)建隊(duì)列

{

PSeqQueue paqu = new SeqQueue;

if(paqu == NULL)

cout"Out of space!"endl;

else

paqu-f=paqu-r=0;

return (paqu);

}

intisEmptyQueue_seq( PSeqQueue paqu ) //判斷paqu 所指是否是空隊(duì)列

{

return paqu-f==paqu-r;

}

voidenQueue_seq(PSeqQueue paqu,int x) //在隊(duì)列中插入一元素 x

{

if ((paqu-r+1)%MAXNUM==paqu-f)

cout"隊(duì)列已滿."endl;

else

{

paqu-q[paqu-r]=x;

paqu-r=(paqu-r+1)%MAXNUM;

}

}

void deQueue_seq(PSeqQueue paqu) //刪除隊(duì)列頭部元素

{

if( paqu-f==paqu-r)

cout"隊(duì)列為空"endl;

else

paqu-f=(paqu-f+1)%MAXNUM;

}

intfrontQueue_seq( PSeqQueue paqu ) //對(duì)非空隊(duì)列,求隊(duì)列頭部元素

{

return (paqu-q[paqu-f]);

}

intfarmer(int location) //判斷農(nóng)夫位置對(duì)0做與運(yùn)算，還是原來(lái)的數(shù)字，用來(lái)判斷位置

{

return 0 != (location 0x08);

}

intwolf(int location) //判斷狼位置

{

return 0 != (location 0x04);

}

intcabbage(int location) //判斷白菜位置

{

return 0 != (location 0x02);

}

intgoat(int location) //判斷羊的位置

{

return 0 !=(location 0x01);

}

intsafe(int location) // 若狀態(tài)安全則返回 true

{

if ((goat(location) == cabbage(location)) (goat(location) != farmer(location)) )

return 0;

if ((goat(location) == wolf(location)) (goat(location) != farmer(location)))

return 0;

return 1; //其他狀態(tài)是安全的

}

void farmerProblem( )

{

int movers, i, location, newlocation;

int route[16]; //記錄已考慮的狀態(tài)路徑

int print[MAXNUM];

PSeqQueue moveTo;

moveTo = createEmptyQueue_seq( );//新的隊(duì)列判斷路徑

enQueue_seq(moveTo, 0x00); //初始狀態(tài)為0

for (i = 0; i 16; i++)

route[i] = -1; //-1表示沒(méi)有記錄過(guò)路徑

route[0]=0;

while(!isEmptyQueue_seq(moveTo)(route[15] == -1))//隊(duì)列不為空，路徑未滿時(shí)循環(huán)

{

location = frontQueue_seq(moveTo); //從隊(duì)頭出隊(duì)

deQueue_seq(moveTo);

for (movers = 1; movers = 8;movers= 1)

{

if ((0 != (location 0x08)) == (0 !=(location movers)))

{

newlocation = location^(0x08|movers);//或運(yùn)算

if (safe(newlocation) (route[newlocation] == -1))//判斷是否安全，以及路徑是否可用

{

route[newlocation] = location;

enQueue_seq(moveTo, newlocation);

}

}

}

}

/*打印出路徑 */

if(route[15] != -1)

{

cout"過(guò)河步驟是 : "endl;

i=0;

for(location = 15; location = 0; location= route[location])

{

print[i]=location;

i++;

if (location == 0)

break;

}

int num=i-1;

int temp[20][4];

int j;

for(i=num;i=0;i--)

{

for(j=3;j=0;j--)

{

temp[num-i][j]=print[i]%2;

print[i]/=2;

temp[0][j]=0;

temp[num+1][j]=1;

}

}

for(i=1;i=num;i++)

{

cout"\t\t\tNO ."i"\t";

if(i%2==1)

{

if(temp[i][3]!=temp[i-1][3])

cout"農(nóng)夫帶羊過(guò)南岸";

if(temp[i][2]!=temp[i-1][2])

cout"農(nóng)夫帶白菜過(guò)南岸";

if(temp[i][1]!=temp[i-1][1])

cout"農(nóng)夫帶狼過(guò)南岸";

if(temp[i][3]==temp[i-1][3]temp[i][2]==temp[i-1][2]temp[i][1]==temp[i-1][1])

cout"農(nóng)夫自己過(guò)南岸";

}

else if(i%2==0)

{

if(temp[i][3]!=temp[i-1][3])

cout"農(nóng)夫帶羊回北岸";

if(temp[i][2]!=temp[i-1][2])

cout"農(nóng)夫帶白菜回北岸";

if(temp[i][1]!=temp[i-1][1])

cout"農(nóng)夫帶狼回北岸";

if(temp[i][3]==temp[i-1][3]temp[i][2]==temp[i-1][2]temp[i][1]==temp[i-1][1])

cout"農(nóng)夫自己回北岸";

}

coutendl;

}

}

else

cout"Nosolution."endl;

}

int main() /*主函數(shù)*/

{

farmerProblem();

return 0;

}

農(nóng)夫過(guò)河問(wèn)題，從JAVA代碼看算法

好繁瑣...一堆if else...你不覺(jué)得很麻煩嗎? 我給你提個(gè)思路. 你每個(gè)Goods object里面都設(shè)置一個(gè)天敵的list.

Goods?g?=?new?Goods("Sheep");

g.setEnemy(Arrays.asList(new?String[]{"wolf"?}));

Goods?g2?=?new?Goods("Cabbage");

g2.setEnemy(Arrays.asList(new?String[]{"Sheep"?}));

Goods?g3?=?new?Goods("Wolf");

g3.setEnemy(Arrays.asList(new?String[]{}));

這樣你的在check isFriendly的時(shí)候, 只要檢測(cè)2個(gè)物品的enemyList里面沒(méi)有自己就可以了.

return?!good1.getEnemyList().contains(good2.getName())??!good2.getEnemyList().contains(good1.getName());

java版農(nóng)夫過(guò)河

先把羊帶過(guò)去

回去

把狼帶過(guò)去

把羊帶回去

把白菜帶過(guò)去

回去

把羊帶過(guò)去

農(nóng)夫過(guò)河問(wèn)題(java)

這個(gè)是偶寫的 你可以參考下 寫的有點(diǎn)多 你自己優(yōu)化下吧 之前還不知道農(nóng)夫過(guò)河是啥意思 不過(guò)后來(lái)知道了 如果有問(wèn)題的話可以馬上說(shuō)的 你的50分偶要定咯??！(可以直接運(yùn)行)

import java.util.Iterator;

import java.util.LinkedList;

public class AcrossTheRiver {

// 定義三個(gè)String對(duì)象

public static final String rabbitName = "Rabbit";

public static final String wolfName = "Wolf";

public static final String cabbageName = "Cabbage";

// 判斷兩個(gè)貨物之間關(guān)系是否友好 寫的麻煩了一點(diǎn)= =..

public static boolean isFriendly(Goods goods1, Goods goods2) {

if (goods1 != null) {

if (goods1.getGoodsName().trim().equals(rabbitName)) {

if (goods2 == null) {

return true;

} else {

return false;

}

} else if (goods1.getGoodsName().trim().equals(wolfName)) {

if (goods2 == null || goods2.getGoodsName().trim().equals(cabbageName)) {

return true;

} else {

return false;

}

} else if (goods1.getGoodsName().trim().equals(cabbageName)) {

if (goods2 == null || goods2.getGoodsName().trim().equals(wolfName)) {

return true;

} else {

return false;

}

} else {

return false;

}

} else {

return true;

}

}

// 我就直接寫在主方法里了

public static void main(String[] args) {

boolean isSuccess = false;

LinkedListGoods beforeCrossing = new LinkedListGoods();

LinkedListGoods afterCrossing = new LinkedListGoods();

beforeCrossing.add(new Goods(rabbitName));

beforeCrossing.add(new Goods(cabbageName));

beforeCrossing.add(new Goods(wolfName));

while (!isSuccess) {

Goods goods1 = beforeCrossing.getFirst();

System.out.println(goods1.getGoodsName() + " 被取走了");

beforeCrossing.removeFirst();

if (beforeCrossing.isEmpty()) {

afterCrossing.addLast(goods1);

isSuccess = true;

System.out.println("全部移動(dòng)完畢！");

} else {

IteratorGoods it = beforeCrossing.iterator();

Goods[] beforeCro = new Goods[2];

for (int i = 0; it.hasNext(); i++) {

beforeCro[i] = it.next();

System.out.println(beforeCro[i].getGoodsName() + " 留了下來(lái)");

}

if (isFriendly(beforeCro[0], beforeCro[1])) {

if (afterCrossing.isEmpty()) {

afterCrossing.addLast(goods1);

System.out.println(goods1.getGoodsName() + " 被成功的放到了對(duì)岸");

} else {

Goods goods2 = afterCrossing.getFirst();

if (isFriendly(goods1, goods2)) {

afterCrossing.addLast(goods1);

System.out.println(goods1.getGoodsName() + " 被成功的放到了對(duì)岸");

} else {

beforeCrossing.addLast(goods2);

afterCrossing.removeFirst();

System.out.println(goods1.getGoodsName() + " 與 "

+ goods2.getGoodsName() + "并不和睦 于是把 " + goods2.getGoodsName()

+ "帶了回來(lái) 并將 " + goods1.getGoodsName() + " 留了下來(lái)");

}

}

} else {

beforeCrossing.addLast(goods1);

System.out.println("很可惜 留下來(lái)的兩個(gè)東西并不和睦 于是 " + goods1.getGoodsName()

+ " 又被放了回去");

}

}

}

}

}

// 貨物類

class Goods {

// 貨物名稱

private String goodsName;

// 默認(rèn)構(gòu)造方法

public Goods(String goodsName) {

this.goodsName = goodsName;

}

// 獲得貨物名稱

public String getGoodsName() {

return goodsName;

}

}