一位老农带着猫、狗、鱼过河,河边有一条船,每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时,狗会咬猫,猫会吃鱼,当老农和猫狗鱼在一起时,则不会发生这种问题。编程解决猫狗鱼过河问题。
对于这个问题,一下是在网上看到的解决办法,但是有些地方不是太懂,能否请高人指教一二,主要是其中涉及的知识点。和思路 ,他们是怎样产生的idea.
import java.util.*;
public class MaoGouYu
{
List<String> left = new ArrayList<String>(); //表示河正岸
List<String> right = new ArrayList<String>(); //表示河对岸
public MaoGouYu() //初始化,老农、猫、狗、鱼都在河正岸准备渡河
{
left.add("person");
left.add("fish");
left.add("dog");
left.add("cat");
}
//渡河方法,解决思路:猫不能和其他动物单独在一起
//第一步:老农带着猫渡河
//第二步:把猫放在对岸,老农自己回去接狗和鱼
//第三步:老农带着狗或者鱼渡河,假设带狗
//第四步:老农把猫带回去,把狗自己放在河对岸
//第五步:老农把猫放在和正岸,带着鱼一起渡河
//第六步:老农自己回去
//第七步:老农带着猫渡河,这样他们就都过去了,也不会发生冲突
public void cross()
{
while(left.size() > 1)
{
left.remove("person");
Random random = new Random(); //老农随机带走一直动物
int index = random.nextInt(left.size());
if(index == left.size() - 1 && left.size() > 1) //为防止老农带走刚带回来的动物
{
left.add("person");
continue;
}
String s = left.get(index);
left.remove(s);
if(isSafe(left)) //如果老农带走该动物后,正岸没有冲突,则带走该动物
{
right.add("person"); // 该动物和老农到达对岸
right.add(s);
System.out.println("老农带" + s + "到对岸");
if(right.size() == 4) //当老农和动物全部到达对岸,则渡河完成
{
break;
}
right.remove("person"); //老农准备返回
if(isSafe(right)) //如果老农自己返回,对岸不会发生冲突,则老农自己返回
{
left.add("person"); //老农返回正岸
System.out.println("老农单独返回");
}
else //否则,老农带着一只动物一起返回
{
String s2 = right.get(random.nextInt(right.size()));
while(s2.equals(s)) //如果老农要带走的动物是刚带来的那只,则换一只带走
{
s2 = right.get(random.nextInt(right.size()));
}
right.remove(s2);
left.add(s2); //老农和一只动物返回正岸
left.add("person");
System.out.println("老农带着" + s2 + "返回");
}
}
else //如果老农带走一只动物后,正岸发生冲突,则放下该动物
{
left.add(s);
left.add("person");
}
}
System.out.println("老农和所有的宠物都成功渡河");
}
//判断某一边是否和谐
public boolean isSafe(List<String> list)
{
boolean b = true;
//如果某一边没有人,猫单独和其他动物在一起,则不和谐
if(list.size() > 1 && list.contains("cat") && !list.contains("person"))
{
b = false;
}
return b;
}
public static void main(String[] args)
{
MaoGouYu mgy = new MaoGouYu();
mgy.cross();
}
} |
|