农夫过河问题的心得体会

农夫过河问题

方案：农夫先把羊运过河，第二次再把菜运过河，此时又把羊捎回，第三次放下羊，同时把豺狗运过河，第四次把羊运过河．

农夫过河问题（一个小细节）

如果location是1的话，只有和1001&才为真，其他都为假，因为其他数的个位都是0

农夫过河问题

左岸------------ 右岸 狼，菜，羊，人---------- 带羊-> 狼，菜----------羊，人 <-独自 狼，菜，人----------羊 带狼-> 菜----------狼，人，羊 <-带羊 羊，菜，人----------狼 带菜-> 羊----------狼，人，菜 <-独自 羊，人----------狼，菜 带羊-> ----------狼，菜，人，羊

农夫过河问题。

急急急

程序就是求解农夫问题：农夫带着一狼，和一些菜过河。

河边只有一船，一次农夫带一样东西。

无人时，狼要吃羊，羊要吃菜，程序将找出所有农夫过河的方案。

首先要表示狼，羊，菜和农夫所在的位置，4者的位置有本岸和对岸两种情况，分别用0和1表示，4者，所以用一个有4元素的数组。

为了要记录每一步，程序中使用了一个二维数组a[MAX_STEP][4]，记录每一步4者所在位置。

第一步就是a[0]，第二布是a[1]...而，a[0][0]就表示第一步狼在本岸(0)还是对岸(1)，a[0][1]表示第一步羊在本岸还是对岸......为了记录每一次农夫过河时的状态，使用了一个数组b[MAX_STEP]，数组中的元素的值可能为-1, 0, 1, 2，分别表示农夫在过河时，是空手，带狼，带羊，带菜。

第一步的状态是狼，羊，菜和农夫都在本案，所以a[0][0]到a[0][3]都是0，本来应该初始化一下，但a是全局变量，所以自动初始化为0，所以程序中省下了这一步。

search是一个递归函数，通过不断的查找可能的下一步，找出一个方案，是一种深度优先搜索。

a[iStep][0] + a[iStep][1] + a[iStep][2] + a[iStep][3] == 4意味着第 iStep时，a[iStep][0]到a[iStep][3]都为1，表示4者都到了对岸。

所以输出结果。

for (i = 0; i < iStep; i++) { if (a[i][3] == 0) { printf(%s到对岸\\\ , name[b[i] + 1]); } else { printf(%s回本岸\\\ , name[b[i] + 1]); } } 输出每一步a[i][3]是农夫在本岸还是对岸，如果为0，在本岸，下一步肯定是到对岸，所以打印...到对岸，而name[b[i]+1]找出对应带的东西的描述。

for (i = 0; i < iStep; i++) { if (memcmp(a[i], a[iStep], sizeof(a[i])) == 0) { return; } } 判定是否会死循环，如果当前状态在以前出现过，那么就会出现死循环。

用当前这步的状态a[iStep]和以前的所有步a[i] (i=0; i

memcmp是内存比较函数，可以用于比较数组，返回值为0，表示数组中所有值相同。

如果相同，就直接返回，不再查找。

if (a[iStep][1] != a[iStep][3] && (a[iStep][2] == a[iStep][1] || a[iStep][0] == a[iStep][1])) { return; } 判定羊会吃菜，或狼会吃羊的情况。

当农夫和羊在一起的时候，狼不会吃羊，羊也不会吃菜，所以当农夫和羊不在一起(a[iStep][1] != a[iStep][3])时，才可能发生“吃”的状态。

而且“吃”的情况必须是在菜和羊在一起(a[iStep][2] == a[iStep][1])或者羊和狼在一起(a[iStep][0] == a[iStep][1])发生吃的情况是，返回，不再查找。

for (i = -1; i <= 2; i++) { b[iStep] = i; memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); a[iStep + 1][3] = 1 - a[iStep + 1][3]; if (i == -1) { search(iStep + 1); } else if (a[iStep][i] == a[iStep][3]) { a[iStep + 1][i] = a[iStep + 1][3]; search(iStep + 1); } } 但现在，已经确保了上一步是“安全”的，可以继续查找。

-1, 0, 1, 2分别表示渡河时4种情况，空手，带狼，带羊，带菜。

memcpy(a[iStep + 1], a[iStep], sizeof(a[iStep + 1])); 复制当前步的数组到下一步。

农夫的状态肯定会发生改变，所以a[iStep + 1][3] = 1 - a[iStep + 1][3]; 因为当a为0或1时，a = 1 - a会使a在0和1之间切换。

如果i== -1，表示空手，狼，羊，菜的状态都不会发生改变，所以直接搜索下一步(search(iStep + 1); )否则要被带过去的东西(0, 1, 2分别表示0, 1, 2)的状态需要改变。

要带的东西必须和农夫同在本案或对岸(a[iStep][i] == a[iStep][3])，才可能带得了。

只有在这种情况下，使要带的东西的状态和农夫相同(a[iStep + 1][i] = a[iStep + 1][3];)，并开始下一步的搜索(search(iStep + 1))。

农夫过河问题

商人过河问题，tc2.0试通过：#include #include #include void dwframe(){ window(1,1,25,80); textbackground(LIGHTBLUE); textcolor(YELLOW); clrscr(); gotoxy(2,2); printf(┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓); gotoxy(2,3); printf(┃); gotoxy(76,3); printf(┃); gotoxy(2,4); printf(┃); gotoxy(76,4); printf(┃); gotoxy(2,5); printf(┃); gotoxy(76,5); printf(┃); gotoxy(2,6); printf(┃); gotoxy(76,6); printf(┃); gotoxy(2,7); printf(┃); gotoxy(76,7); printf(┃); gotoxy(2,8); printf(┃); gotoxy(76,8); printf(┃); gotoxy(2,9); printf(┃); gotoxy(76,9); printf(┃); gotoxy(2,10); printf(┃); gotoxy(76,10); printf(┃); gotoxy(2,11); printf(┃); gotoxy(76,11); printf(┃); gotoxy(2,11); printf(┃); gotoxy(76,11); printf(┃); gotoxy(2,12); printf(┃); gotoxy(76,12); printf(┃); gotoxy(2,14); printf(┃); gotoxy(76,14); printf(┃); gotoxy(2,15); printf(┃); gotoxy(76,15); printf(┃); gotoxy(2,16); printf(┃); gotoxy(76,16); printf(┃); gotoxy(2,17); printf(┃); gotoxy(76,17); printf(┃); gotoxy(2,18); printf(┃); gotoxy(76,18); printf(┃); gotoxy(2,19); printf(┃); gotoxy(76,19); printf(┃); gotoxy(2,20); printf(┃); gotoxy(76,20); printf(┃); gotoxy(2,21); printf(┃); gotoxy(76,21); printf(┃); gotoxy(2,22); printf(┃); gotoxy(76,22); printf(┃); gotoxy(2,23); printf(┃); gotoxy(76,23); printf(┃); gotoxy(2,24); printf(┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛);}void helpf() { dwframe(); gotoxy(25,4); printf(^_^欢迎使用商人过河游戏

^_^); gotoxy(4,6); printf(游戏说明：); gotoxy(5,7); printf(三个商人带着三个随从和货物过河，船每次最多只能载两个人，); gotoxy(5,8); printf(要求在过河期间，任一岸上商人的人数要大于或等于随从的人数，); gotoxy(5,9); printf(否则随从会杀掉商人抢走货物。

); gotoxy(5,11); printf(游戏操作：（1）依次输入过河的商人和随从人数；); gotoxy(5,12); printf( （2）非法输入按键将重新开始。

); gotoxy(2,13); printf(┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫);}char a[6];char b[6];void printcase(char a[],char b[]){ int i,j,xa,xb,x0,ya,yb,y0; xa=xb=x0=ya=yb=y0=0; gotoxy(11,14); printf(此岸 彼岸\\\ ); for(i=0;i<6;i++) { if(a[i]=='A') xa++; else if (a[i]=='B') xb++; else if(a[i]=='0') x0++; } gotoxy(11,15); for(i=1;i<=xa;i++) printf(商人 ); gotoxy(11,16); for(i=1;i<=xb;i++) printf(随从 ); gotoxy(11,17); for(i=1;i<=x0;i++) printf( ); for(j=0;j<6;j++) { if(b[j]=='A') ya++; else if(b[j]=='B') yb++; else if(b[j]=='0') y0++; } gotoxy(31,15); for(j=1;j<=ya;j++) printf(商人 ); gotoxy(31,16); for(j=1;j<=yb;j++) printf(随从 ); gotoxy(31,17); for(j=1;j<=y0;j++) printf( ); if(xa==0 && xb==0 && ya==3 && yb==3) { gotoxy(15,21); printf(恭喜你

你已成功帮助商人安全过河

按任意键退出...); getch(); window(1,1,25,80); textbackground(BLACK); textcolor(LIGHTGRAY); clrscr(); exit(0); }}void main(){ int i,x,y,key,ca,cb,j,aA,aB,bA,bB; char ch;Start: helpf(); gotoxy(15,16); printf(请按任意键开始游戏（按Q键退出）...); ch=getch(); if(ch=='Q'||ch=='q') { window(1,1,25,80); textbackground(BLACK); textcolor(LIGHTGRAY); clrscr(); exit(0); } helpf(); for(i=0;i<3;i++) a[i]='A'; for(i=3;i<6;i++) a[i]='B'; for(i=0;i<6;i++) b[i]='0'; printcase(a,b); while(1) { gotoxy(20,18); printf(输入去彼岸商人的人数： ); scanf(%d,&x); gotoxy(20,18); printf(输入去彼岸随从的人数： ); scanf(%d,&y); for(ca=0,cb=0,i=0;i<6;i++) { if(a[i]=='A') ca++; else if(a[i]=='B') cb++; } if(x<0 || x>ca || y<0 || y>cb || x+y<1 ||x+y>2) { gotoxy(15,21); printf(输入有误

按任意键重新开始...); getch(); goto Start; } for(i=1;i<=x;i++) { for(j=0;j<6;j++) if(a[j]=='A') { a[j]='0'; break; } } for(i=1;i<=x;i++) { for(j=0;j<6;j++) if(b[j]=='0') { b[j]='A'; break; } } for(i=1;i<=y;i++) { for(j=0;j<6;j++) if(a[j]=='B') { a[j]='0'; break; } } for(i=1;i<=y;i++) { for(j=0;j<6;j++) if(b[j]=='0') { b[j]='B'; break; } } for(aA=0,aB=0,i=0;i<6;i++) { if(a[i]=='A') aA++; else if(a[i]=='B') aB++; } for(bA=0,bB=0,i=0;i<6;i++) { if(b[i]=='A') bA++; else if(b[i]=='B') bB++; } if((aA==3) ||(bA==3) || (aA==aB) || (bA==bB)) { helpf(); printcase(a,b); } else { gotoxy(15,21); printf(商人被杀，按任意键重新开始...); getch(); goto Start; } gotoxy(20,18); printf(输入回此岸商人的人数： ); scanf(%d,&x); gotoxy(20,18); printf(输入回此岸随从的人数： ); scanf(%d,&y); for(ca=0,cb=0,i=0;i<6;i++) { if(b[i]=='A') ca++; else if(b[i]=='B') cb++; } if(x<0 || x>ca || y<0 || y>cb || x+y<1 || x+y>2) { gotoxy(15,21); printf(输入有误

按任意键重新开始...); getch(); goto Start; } for(i=1;i<=x;i++) { for(j=0;j<6;j++) if(b[j]=='A') { b[j]='0'; break; } } for(i=1;i<=x;i++) { for(j=0;j<6;j++) if(a[j]=='0') { a[j]='A'; break; } } for(i=1;i<=y;i++) { for(j=0;j<6;j++) if(b[j]=='B') { b[j]='0'; break; } } for(i=1;i<=y;i++) { for(j=0;j<6;j++) if(a[j]=='0') { a[j]='B'; break; } } for(aA=0,aB=0,i=0;i<6;i++) { if(a[i]=='A') aA++; else if(a[i]=='B') aB++; } for(bA=0,bB=0,i=0;i<6;i++) { if(b[i]=='A') bA++; else if(b[i]=='B') bB++; } if((aA==3) ||(bA==3) || (aA==aB) || (bA==bB)) { helpf(); printcase(a,b); } else { gotoxy(15,21); printf(商人被杀，按任意键重新开始...); getch(); goto Start; } }}

农夫过河有什么实际意义，与现实生活问题相结合的运用

我个人认为这个游戏有什么实际意义是因人而言的，每人都生活方式和对生活的追求都不同，人生就像游戏；start（开始）---process(过程）----THE END（结束）哈哈

农夫过河问题求解。

看起来貌似好复杂的样子

农夫过河问题。

这个是偶写的 你可以参考下 写的有点多 你自己优化下吧 之前还不知道农夫过河是啥意思 不过后来知道了 如果有问题的话可以马上说的 你的50分偶要定咯

(可以直接运行)import java.util.Iterator; import java.util.LinkedList; public class AcrossTheRiver { \\\/\\\/ 定义三个String对象 public static final String rabbitName = Rabbit; public static final String wolfName = Wolf; public static final String cabbageName = Cabbage; \\\/\\\/ 判断两个货物之间关系是否友好 写的麻烦了一点= =.. 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; LinkedList beforeCrossing = new LinkedList(); LinkedList afterCrossing = new LinkedList(); 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(全部移动完毕

); } else { Iterator 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() + 留了下来); } if (isFriendly(beforeCro[0], beforeCro[1])) { if (afterCrossing.isEmpty()) { afterCrossing.addLast(goods1); System.out.println(goods1.getGoodsName() + 被成功的放到了对岸); } else { Goods goods2 = afterCrossing.getFirst(); if (isFriendly(goods1, goods2)) { afterCrossing.addLast(goods1); System.out.println(goods1.getGoodsName() + 被成功的放到了对岸); } else { beforeCrossing.addLast(goods2); afterCrossing.removeFirst(); System.out.println(goods1.getGoodsName() + 与 + goods2.getGoodsName() + 并不和睦 于是把 + goods2.getGoodsName() + 带了回来 并将 + goods1.getGoodsName() + 留了下来); } } } else { beforeCrossing.addLast(goods1); System.out.println(很可惜 留下来的两个东西并不和睦 于是 + goods1.getGoodsName() + 又被放了回去); } } } } } \\\/\\\/ 货物类 class Goods { \\\/\\\/ 货物名称 private String goodsName; \\\/\\\/ 默认构造方法 public Goods(String goodsName) { this.goodsName = goodsName; } \\\/\\\/ 获得货物名称 public String getGoodsName() { return goodsName; } }