*/import java.util.*;public class Test4{
/**内部类，用来把保存过河过程中的路线和状态.
to为ture表示去对岸，否则表示从对岸返回。同时true也表示船在本岸，false表示船在对岸.
busiMansInBoat为在船里的商人数.
servsInBoat为船里的仆人数.
residualBusiMans为岸上的商人数，to为true时，表示是本岸.
residualServants为岸上的仆人数，to为true时，表示是本岸.
static class Path{
int busiMansInB
int servsInB
int residualBusiM
int residualS
Path(boolean to,int bmib,int sib,int rb,int rs){
busiMansInBoat=
servsInBoat=
residualBusiMans=
residualServants=
/*比较两个状态是不是相同.
public boolean equals(Path p){
if(to==p.to){
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&residualBusiMans==p.residualBusiMans&&residualServants==p.residualS
}else if(to){
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&residualBusiMans==3-p.residualBusiMans-p.busiMansInBoat&&residualServants==3-p.residualServants-p.servsInB
return busiMansInBoat==p.busiMansInBoat&&servsInBoat==p.servsInBoat
&&3-residualBusiMans-busiMansInBoat==p.residualBusiMans&&3-residualServants-servsInBoat==p.residualS
public String toString(){
return "本岸(商人"+residualBusiMans+"个,仆人"+residualServants+"个)-----&"
+"[船上:"+busiMansInBoat+"个商人,"+servsInBoat+"个仆人]-----&"
+"对岸(商人"+(3-residualBusiMans-busiMansInBoat)+"个,仆人"+(3-residualServants-servsInBoat)+"个)";
return "本岸(商人"+(3-residualBusiMans-busiMansInBoat)+"个,仆人"+(3-residualServants-servsInBoat)+"个)&-----"
+"[船上:"+busiMansInBoat+"个商人,"+servsInBoat+"个仆人]&-----"
+"对岸(商人"+residualBusiMans+"个,仆人"+residualServants+"个)";
//保存路线的List
public static List&Path& pathList=new ArrayList&Path&();
/**过河方法.
* @param businessmans 商人数.
* @param servants
* @param schemes
* @param to
去还是返回，同时也表示是否在对岸.
public static void passRiver(int businessmans,int servants,int[][] schemes,boolean to){
if(!to&&businessmans==3&&servants==3){
System.out.println("结果");
for(Path p : pathList){
System.out.println(p);
int schemesStart=0;
//从方案集中的那一种方案开始选择.
schemesStart=2;
//如果在本岸，则从第3种方案开始选择.
for(int i=schemesSi&schemes.i++){
int residualBusiMans=businessmans-schemes[i][0];
//按照方案岸上所剩商人数.
int residualServants=servants-schemes[i][1];
//按照方案岸上所剩仆人数.
if(residualBusiMans&0||residualServants&0){
//如果商人数或仆人数小于0，重新选择方案.
if(residualBusiMans!=0&&residualBusiMans&residualServants){
//如果仆人数大于商人数，重新选择方案.
if(3-residualBusiMans!=0&&3-residualBusiMans&3-residualServants){
//如果对岸的仆人数大于商人数,重新选择方案.
//按本方案，生成路线.
Path p=new Path(to,schemes[i][0],schemes[i][1],residualBusiMans,residualServants);
if(!isRepeat(p)){
//如果没有重复.
pathList.add(p);
passRiver(3-residualBusiMans,3-residualServants,schemes,!to); //从对岸返回.
pathList.remove(pathList.size()-1);
/**看看当前的路线是不是和以前的重复了.
public static boolean isRepeat(Path p){
boolean repeat=false;
for(Path temp : pathList){
if(temp.equals(p)){
repeat=true;
public static void main(String[] args)throws Exception{
//过河方案,每一种方案为一个一组数组,比如{1,0}表示船上要坐1个商人和0个仆人。方案可以用一个方法来生成:
int[][] sckemes={{1,0},{0,1},{1,1},{2,0},{0,2}};
passRiver(3,3,sckemes,true);
}}/*本算法只能解决3个商人和3个仆人，不俱通用性.*/
阅读(...) 评论()知识点梳理
1． 突破思维定势2． 某些特殊情境问题
整理教师:&&
举一反三（巩固练习，成绩显著提升，去）
根据问他()知识点分析，
试题“有37名战士要过河，河边只有一条小船，船上每次只能坐5人，至...”，相似的试题还有：
有20个人要到河的对岸去，河边只有一条船，船上每次只能坐5个人，小船至少要载()次才能让他们全部过河．
有37名战士要过河，只有一只小船，一次能载5人，需要几次才能渡完？
16人要自己撑船过河，河边只有一条空船，小船一次只能载4人过河，小船要载几次，16人才能全部过河？Java SE（19）
一、问题描述：
农夫要带鱼、狗、猫过河到对岸.，有一条船，只能坐一个人，农夫每次只能带一样动物过河，当农夫不在的时侯狗会咬猫，猫会吃鱼.，请问怎么顺序过河呢？
要求：编写程序，由程序来推出过河的顺序。
二、问题分析：
问题中可以提取出人、猫、狗、鱼、河、岸、船这几个对象。下面分析，这其中哪些对象是必要的，哪些是无关的。
1、河：河的存在只是为了突显左岸与右岸。农夫过河，本质上是将一堆东西从一个地方转移至另一个地方。因此，河是不必存在的；
2、岸：由1可知，设计左岸与右岸是必要的。
3、船：船是绑定于河而出现的一个模型，然而根据分析可知，问题的实质在于将一堆东西从一个地方转移至另一个地方，而转移的工具是无需描述的。因此，船不必存在。
4、人：人在整个过河问题中的作用，仅仅是为了保证人所在的岸，该岸上的动物是安全的。也就是说，人所在的位置，决定了哪一边是肯定安全的，哪一边是需要检测是否安全。人的位置只有左岸与右岸两种互斥状态。
5、猫、狗、鱼：任意一种动物都可能与另一种动物发生矛盾现象。可以设计一个动物类，并定义几个属性描述动物之间的矛盾关系。（本例中，为了简化直接将动物定为字符串类型）
6、程序执行过程中的问题：
& & 2.1、问题的最终目标：最后左岸上的动物全部转移到了右岸
& & 1）设计岸是为了描述一个地方与另一个地方，为了加以区分及结合情境，起名为左岸与右岸；
& & 2）动物是待在岸上的；
& & 3）设计两个容器，分别表示左岸与右岸。容器用于装动物；
& & 2.2、容器的选择：数组或集合
& & 1）数组：获取数组中已有的元素数量时非常不方便（缺点）；
& & 2）集合：获取集合中已有的元素数量时非常方便（优点）；
& & 3）总结：使用集合来描述左岸与右岸十分方便。当描述右边的集合长度为3（size()==3）时，最终目标达成。
& & 1）设计一个boolean值flag，描述人的位置；
& & 2）根据flag值判断出人的位置，并由此决定检测它的对岸的安全状态；
& & 1）农夫过河一次后，若两岸存在安全问题，则需要回退到过河前的状态。
& & & & &①设计一种模型，分别保存移动前的两岸各自状态，当移动后出现问题时，用于回退到移动前的状态。
& & 2）过河过程中，需要考虑当前移动后的两岸整体状态是否曾经出现过，即该次移动是否曾经出现过，若出现过则需要回退到移动前的状态。
& & & & &②设计一种模型，用于描述移动后两岸的整体状态；设计一种模型，保存所有的曾经出现过的两岸的整体状态。
三、具体代码：
* 农夫过河问题
import java.util.ArrayL
import java.util.C
import java.util.HashS
import java.util.L
public class Test10 {
public static void main(String[] args) {
CrossRiver cr=new CrossRiver();
//创建一个农夫过河对象
cr.initial();
//初始化三只动物，并添加到左岸
cr.crossRiver(); //农夫开始过河
//定义一个农夫过河类
class CrossRiver{
//定义两个集合，作为左岸与右岸
private List&String& leftSide=new ArrayList&String&();
private List&String& rightSide=new ArrayList&String&();
//定义两个集合，用于分别保存每次移动前，左\右岸的状态。当移动出现问题时，用于回复之前状态
private List&String& temp1=new ArrayList&String&();
private List&String& temp2=new ArrayList&String&();
//定义一个集合，用于存储所有移动操作后的左\右岸的整体状态，每次移动后都要保存
private HashSet&ArrayList&Object&& statusSet=new HashSet&ArrayList&Object&&();
//定义一个布尔值，用于描述人的位置。当值为true时，表示人在左岸；反之，人在右岸
private Boolean flag=
//定义一个int值，用于记录移动的次数
private int count=1;
//声明狗、猫、鱼三只动物
//初始化三只动物，添加到左岸并排序
public void initial(){
dog=&dog&;
cat=&cat&;
fish=&fish&;
leftSide.add(dog);
leftSide.add(cat);
leftSide.add(fish);
Collections.sort(leftSide);
//农夫过河
public void crossRiver(){
//当右岸集合长度为3时，即3只动物均到右岸时，循环结束
while(rightSide.size()!=3){
/*判断人的位置，根据人的位置决定过河方向，
*每次过河分为农夫独自过河与农夫带一只动物过河两种情况
if(moveAlone(leftSide,rightSide))//农夫独自过河
//当农夫独自过河是安全的，就结束本次循环
moveWithAnimal(leftSide,rightSide);
if(moveAlone(rightSide,leftSide))
moveWithAnimal(rightSide,leftSide);
System.out.println(&农夫成功过河！&);
//农夫独自过河
private boolean moveAlone(List&String& fromSide,List&String& toSide) {
System.out.println(&第&+(count++)+&次移动:&);
store(); //保存移动前状态
if(fromSide==leftSide)
System.out.println(&人单独从左岸到右岸&);
System.out.println(&人单独从右岸到左岸&);
//移动后，改变人的位置状态
System.out.println(&本次移动后状态为：&+leftSide+&,&+rightSide+&,&+flag);
return isSafe(fromSide); //判断本次移动是否安全，并返回判断值
//农夫带着一只动物过河
private void moveWithAnimal(List&String& fromSide,List&String& toSide) {
//从出发的岸上，依次选择带一只动物过河
for (int i = 0; i & fromSide.size(); i++) {
System.out.println(&第&+(count++)+&次移动:&);
String animal=fromSide.get(i); //将动物从此岸运往彼岸
fromSide.remove(animal);
toSide.add(animal);
if(fromSide==leftSide)
System.out.println(&人带着&+animal+&从左岸到右岸&);
System.out.println(&人带着&+animal+&从右岸到左岸&);
System.out.println(&本次移动后状态为：&+leftSide+&,&+rightSide+&,&+flag);
if(isSafe(fromSide)) //判断本次移动是否安全，若安全则结束for循环；否则继续带另外的动物移动
//保存每次移动前，左\右岸的状态
private void store() {
copy(temp1, leftSide);
copy(temp2, rightSide);
System.out.println(&本次移动前状态为：&+leftSide+&,&+rightSide+&,&+flag);
//集合的拷贝
private void copy(List&String& newSet,List&String& oldSet){
newSet.clear(); //拷贝前，先清空之前的内容
newSet.addAll(oldSet);
//当移动出现问题时，用于回复之前状态
private void recover() {
copy(leftSide, temp1);
copy(rightSide, temp2);
System.out.println(&回复为本次移动前状态：&+leftSide+&,&+rightSide+&,&+flag);
//判断此次移动是否安全成功
private boolean isSafe(List&String& side) {
//判断此次移动是否曾经出现过
if(addStatus()){
return checkSide(side);
System.out.println(&本次移动曾经出现过&);
recover();
//检测此次移动后，某一岸是否安全
private boolean checkSide(List&String& side) {
//若动物数量少于两只，则该岸一定安全
if(side.size()&2){
System.out.println(&本次移动是安全的&);
if(checkSafe(side)){
System.out.println(&本次移动是安全的&);
System.out.println(&本次移动是不安全的&);
recover();
//具体检测某一岸的安全状态
private boolean checkSafe(List&String& side) {
return !((side.contains(&cat&)&&side.contains(&dog&))||(side.contains(&cat&)&&side.contains(&fish&)));
//将两岸的整体状态添加进集合中,并判断这次移动操作是否曾经出现过
private boolean addStatus() {
//将集合排序，用于保证动物移动过程中产生的[dog,cat]与[cat,dog]是同一种状态
Collections.sort(leftSide);
Collections.sort(rightSide);
//定义一个集合，用于表示移动后两岸的整体状态
ArrayList&Object& status=new ArrayList&Object&();
status.add(leftSide);
status.add(rightSide);
status.add(flag);
return statusSet.add(status);
四、延伸阅读：其他实现农夫过河的方法
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：9296次
排名：千里之外
原创：31篇
(1)(17)(12)(3)当前位置：
＞＞＞有20个人要到河的对岸去，河边只有一条小船，船上每一次只能坐5个..
有20个人要到河的对岸去，河边只有一条小船，船上每一次只能坐5个人，小船至少要载几次，才能使这20人全部过河？
题型：解答题难度：偏难来源：期末题
马上分享给同学
据魔方格专家权威分析，试题“有20个人要到河的对岸去，河边只有一条小船，船上每一次只能坐5个..”主要考查你对&&有余数的除法&&等考点的理解。关于这些考点的“档案”如下：
现在没空？点击收藏，以后再看。
因为篇幅有限，只列出部分考点，详细请访问。
有余数的除法
有余数的除法竖式：思路点拨：1、有余数的除法中，余数比除数小。2、被除数÷除数=商……余数 &&&&& 被除数=商×除数+余数 &&&&& 除数=（被除数-余数）÷商 &&&&& 商=（被除数-余数）÷除数
发现相似题
与“有20个人要到河的对岸去，河边只有一条小船，船上每一次只能坐5个..”考查相似的试题有：
49767108045210387616155479417331056831