题目:有3只狼和3只羊要过河,只有一条船,一次最多只能坐两只动物并且每次必须有动物开船,如果某一边的狼的个数大于羊的个数,羊将被吃掉,编程给出解。
关于编程思路,参考:Java编程能力强化(2)——搜索解决方案类问题的通用解法
参考答案:
package ch1;
public class LangAndYang {
public static void main(String[] args) {
int state[] = {3,3};
// 第1、2个元素表示左岸的狼和羊的数量
new LangAndYang().next(state,null);
}
public void next(int state[],StringBuffer str){
int[] newState;
if(str==null){ //表示第一步
// 一只狼一只羊
newState = move(state,"-1-1");
next(newState,new StringBuffer("-1-1"));
// 两只狼过河
newState = move(state,"-2-0");
next(newState,new StringBuffer("-2-0"));
return;
}
if(state[0]==0 && state[1]==0){ // 全部转移到右岸了
printResult(str);
return;
}
if(str!=null && hasExist(str)){ // 看是否为死循环
return;
}
// 考虑向右转移
if(str.charAt(0)=='+'){
// 两只狼
if(state[0]>=2 && !str.substring(0,4).equals("+2+0")){
newState = move(state,"-2-0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-2-0"));
}
}
// 一只狼
if(state[0]>=1 && !str.substring(0,4).equals("+1+0")){
newState = move(state,"-1-0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-1-0"));
}
}
// 一只羊
if(state[1]>=1 && !str.substring(0,4).equals("+0+1")){
newState = move(state,"-0-1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-0-1"));
}
}
// 一只狼一只羊
if(state[0]>=1 && state[1]>=1 && !str.substring(0,4).equals("+1+1")){
newState = move(state,"-1-1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-1-1"));
}
}
// 两只羊
if(state[1]>=2 && !str.substring(0,4).equals("+0+2")){
newState = move(state,"-0-2");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"-0-2"));
}
}
}else{ // 考虑向左转移
// 两只狼
if(state[0]<2 && !str.substring(0,4).equals("-2-0")){
newState = move(state,"+2+0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+2+0"));
}
}
// 一只狼
if(state[0]<3 && !str.substring(0,4).equals("-1-0")){
newState = move(state,"+1+0");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+1+0"));
}
}
// 一只羊
if(state[1]<3 && !str.substring(0,4).equals("-0-1")){
newState = move(state,"+0+1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+0+1"));
}
}
// 一只狼一只羊
if(state[0]<3 && state[1]<3 && !str.substring(0,4).equals("-1-1")){
newState = move(state,"+1+1");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+1+1"));
}
}
// 两只羊
if(state[1]<2 && !str.substring(0,4).equals("-0-2")){
newState = move(state,"+0+2");
if(check(newState)){
next(newState,new StringBuffer(str).insert(0,"+0+2"));
}
}
}
}
/*
* 第一个参数表示状态,第二个参数表示走法,向右用-,向左用+
* 返回值表示新的状态
*/
public int[] move(int state[],String info){
int lang = 0;
try{
lang = Integer.parseInt(info.substring(0,2));
}catch(Exception e){
lang = Integer.parseInt(info.substring(1,2));
}
int yang = 0;
try{
yang= Integer.parseInt(info.substring(2));
}catch(Exception e){
yang = Integer.parseInt(info.substring(3));
}
int[] result = new int[state.length];
result[0] = state[0]+lang;
result[1] = state[1]+yang;
return result;
}
/*
* 验证状态是否合适,狼的个数不能大于羊
*/
public boolean check(int state[]){
if(state[0]>state[1] && state[1]>0){ //左边有羊,并且狼比羊多
return false;
}else if(state[0]<state[1] && state[1]<3){ // 右边有羊,并且狼比羊多
return false;
}else
return true;
}
/*
* 防止死循环,例如 先过去一只狼一只羊,然后回来一只羊,然后再过去一只狼,然后回来两只狼,就回到初始状态了
*/
public boolean hasExist(StringBuffer str){
int langSum=0;
int yangSum=0;
for(int i=0;i<str.length()/4;i++){
if(str.charAt(i*4)=='-'){
langSum += str.charAt(i*4+1)-'0';
yangSum += str.charAt(i*4+3)-'0';
}else{
langSum -= str.charAt(i*4+1)-'0';
yangSum -= str.charAt(i*4+3)-'0';
}
if(langSum==0 && yangSum==0 && i%2==1)
return true;
}
return false;
}
public void printResult(StringBuffer str){
System.out.println("-----方案------");
for(int i=str.length()/4-1;i>=0;i--){
if(str.charAt(i*4)=='-'){
System.out.println("运过去"+str.charAt(i*4+1)+"只狼,"+str.charAt(i*4+3)+"只羊");
}else{
System.out.println("---------------运回来"+str.charAt(i*4+1)+"只狼,"+str.charAt(i*4+3)+"只羊");
}
}
System.out.println();
}
}
希望大家真正把代码理解了,而不是把代码保存下来。
分享到:
相关推荐
编译原理中人狼羊菜过河通过java语言实现的程序。
利用状态转移矩阵,给出了狼羊过河问题的解法并附有相关代码及结果展示
用c++设计一个程序,自动解决“一个人带有一只羊, 一框菜和一只狼要过河, 但船上除了载一人以外, 最多每次只能再带一样东西。而当人不在场的情况下, 羊和菜在一起, 羊要吃菜, 狼和羊在一起, 狼会吃羊。问怎样...
用python编写的一款小游戏,实现人狼羊菜过河
狼羊过河问题 是最经典的问题之一 问题要求如下: 如果没有农夫看管,则狐狸会吃掉兔子,兔子会吃掉蔬菜,由于船只很小,每次最多只能带狐狸,兔子,蔬菜三者中的一个过河。判断农民是否能顺利过河?若能怎样过?
W,一头羊 G 和一篮白菜 C 从一条河的左岸渡到右岸去,而船小只能容纳 F、W、G、C 中的两个,决不能在无人看守的情况下,留下狼和羊在一起,羊和白菜在一起,应怎样渡河才能将狼、羊、白菜都运过去?
cout有一个农夫带一只羊、一筐菜和一只狼过河. "; cout如果没有农夫看管,则狼要吃羊,羊要吃菜."; cout但是船很小,只够农夫带一样东西过河。"; cout问农夫该如何解此难题?";
今天群里有人提起,就做了下,新手,做的不是很好.
狼羊白菜农夫过河程序 c++,条件语句嵌套。
数学建模-数学模型——商人过河问题.zip
最经典的狼羊菜过河问题,代码的实现。 使用C++语言实现。 属于人工智能范畴内。
一个农夫带着一只狼,一只羊和一筐菜,欲从河的左岸坐船到右岸,由于船太小,农夫每次只能带一样东西过河,并且没有农夫看管的话,狼会吃掉羊,羊会吃菜。设计一个方案,使农夫可以无损失的过河
java实现野人与传教士过河问题,需要c或者c#(有动画演示)见主页。
我是新手,闲着无聊,写个小游戏 益智类小游戏,很容易过,附源码请指教
一个人带着一匹狼、一只羊和一筐白菜要自己划船从河的北岸过河到南岸。人不在时,狼会吃羊,羊会吃白菜。只有人会划船并且每次只能带一个对象过河。此程序解决如何过河
八人过河问题的Java编程实现.pdf
假设有 N 个传教士和 N 个野人准备渡河,但只有一条能容纳 C 人的小船,1 ,为了防止野人伤害传教士,要求无论在何处,传教士的个数不得少于野人的人数(除非传教士个数为 0)。如果两种人都会划船,试设计一个算法...
SPIN和SMV工具的对比学习 ——基于农夫过河问题-附件资源
八人过河问题的Java编程实现
猎人要带一条狼、一只羊和一棵大白菜过河。船太小,一次只能带一样。但猎人不在场的情况下,狼要吃羊,羊要吃白菜。请设计一个C++程序为猎人指出一个安全的渡河放案。 资源中有c++源程序和文档说明