黑马程序员技术交流社区

标题: 过河问题，求解答。 [打印本页]
作者: 世界公民    时间: 2014-4-20 06:47
标题: 过河问题，求解答。
本帖最后由 世界公民 于 2014-4-22 14:59 编辑

问题是：一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。编程解决猫狗鱼过河问题。

这是我基础测试时的一道题，我尽力用代码解出来了，但感觉不是非常好。我写的代码只是针对这个题的，如果换几个过河条件我的代码需要全部重写，当过河逻辑再难一点时我的这种解法就很难再有效果了。
希望有人可以指导我一下，写出一个普遍的解法，比如当过河条件变成这样：河边有警察、犯人、爸爸、妈妈、两个小男孩、两个小女孩和一条船，条件是当警察不在时犯人会伤害其他人，当爸爸不在时妈妈会伤害小男孩，当妈妈不在时爸爸会伤害小女孩，警察、爸爸、妈妈会开船，船一次只能拉两个人（算上开船的），请安全的把这些人送到对岸去。
希望有人指导一下，我希望写出一个好的解题方法，可以处理这类过河问题，比如当过河的条件更复杂时可以用程序计算出有没有过河的解，以及过河的具体步骤。

下面是我解农夫过河的代码（感觉很差，请大家指导）：
  1. public class Test10 {
  2.         int farmer,cat,dog,fish; //刚开始都为0，也就是都在河的这岸
  3.         String type = ""; //记录农夫上一步带的是什么，防止出现死循环,当农夫自己走时type不改变
  4.         String isnull = "";//当农夫自己走时，isnull会记录下来，防止出现死循环。
  5.         boolean boo = false;
  6.         public static void main(String[] args) {
  7.                 Test10 test = new Test10();
  8.                 int x = 1;//记录移动的数次
  9.                 while(true){
  10.                    test.move();
  11.            System.out.println("第"+x+"步");
  12.            System.out.println("河这岸有："+test.print(0));
  13.            System.out.println("河对岸有："+test.print(1));
  14.            x++;
  15.            //当把全部东西都移动到对岸时，即可停止移动。
  16.            if(test.farmer==1&&test.cat==1&&test.dog==1&&test.fish==1){
  17.                break;
  18.            }
  19.            }
  20.                     
  21.             
  22.         }
  23.         
  24.         //农夫过河时需要判断能带什么不能带什么
  25.         public void move(){
  26.                
  27.                 if(farmer==0){
  28.                         if(cat==0){
  29.                                 if(!type.equals("cat")){
  30.                                         farmer = 1;
  31.                                         cat = 1;
  32.                                         if(isSafe()){
  33.                                                 type = "cat";
  34.                                                 return;
  35.                                         }else{
  36.                                                 farmer = 0;
  37.                                                 cat = 0;
  38.                                         }
  39.                                 }
  40.                         }
  41.                         if(dog==0){
  42.                                 if(!type.equals("dog")){
  43.                                         farmer = 1;
  44.                                         dog = 1;
  45.                                         if(isSafe()){
  46.                                                 type = "dog";
  47.                                                 return;
  48.                                         }else{
  49.                                                 farmer = 0;
  50.                                                 dog = 0;
  51.                                         }
  52.                                 }
  53.                         }
  54.                         if(fish==0){
  55.                                 if(!type.equals("fish")){
  56.                                         farmer = 1;
  57.                                         fish = 1;
  58.                                         if(isSafe()){
  59.                                                 type = "fish";
  60.                                                 return;
  61.                                         }else{
  62.                                                 farmer = 0;
  63.                                                 fish = 0;
  64.                                         }
  65.                                 }
  66.                         }
  67.                                 farmer = 1;
  68.                         
  69.                 }else if(farmer==1){
  70.                         //当人在河对岸时需要优先考虑自已到这岸来，从而把东西带到对岸。
  71.                         if(isnull != "farmer"){
  72.                                 farmer = 0;
  73.                                 isnull = "farmer";
  74.                                 if(isSafe()){
  75.                                         return;
  76.                                 }else{
  77.                                         farmer = 1;
  78.                                 }
  79.                         }
  80.                                 
  81.                         if(cat==1){
  82.                                 if(!type.equals("cat")){
  83.                                         farmer = 0;
  84.                                         cat = 0;
  85.                                         if(isSafe()){
  86.                                                 type = "cat";
  87.                                                 isnull = "";
  88.                                                 return;
  89.                                         }else{
  90.                                                 farmer = 1;
  91.                                                 cat = 1;
  92.                                         }
  93.                                 }
  94.                         }
  95.                         if(dog==1){
  96.                                 if(!type.equals("dog")){
  97.                                         farmer = 0;
  98.                                         dog = 0;
  99.                                         if(isSafe()){
  100.                                                 type = "dog";
  101.                                                 isnull = "";
  102.                                                 return;
  103.                                         }else{
  104.                                                 farmer = 1;
  105.                                                 dog = 1;
  106.                                         }
  107.                                 }
  108.                         }
  109.                         if(fish==1){
  110.                                 if(!type.equals("fish")){
  111.                                         farmer = 0;
  112.                                         dog = 0;
  113.                                         if(isSafe()){
  114.                                                 type = "fish";
  115.                                                 isnull = "";
  116.                                                 return;
  117.                                         }else{
  118.                                                 farmer = 1;
  119.                                                 fish = 1;
  120.                                         }
  121.                                 }
  122.                         }
  123.                 }
  124.         }
  125.         
  126.         //判断现在的状态是否有冲突
  127.         public boolean isSafe(){
  128.                 if(farmer==1){
  129.                         if(cat==0&&fish==0)return false;
  130.                         if(cat==0&&dog==0)return false;
  131.                 }else if(farmer==0){
  132.                         if(cat==1&&fish==1)return false;
  133.                         if(cat==1&&dog==1)return false;
  134.                 }
  135.                 return true;
  136.         }
  137.         
  138.         //打印现在河的两岸都有什么
  139.         public String print(int i){
  140.                 if(i==0){
  141.                         String str = "";
  142.                         if(farmer==0)str += "农夫    ";
  143.                         if(dog==0)str += "狗    ";
  144.                         if(cat==0)str += "猫    ";
  145.                         if(fish==0)str += "鱼    ";
  146.                         return str;
  147.                 }else if(i==1){
  148.                         String str = "";
  149.                         if(farmer==1)str += "农夫    ";
  150.                         if(dog==1)str += "狗    ";
  151.                         if(cat==1)str += "猫    ";
  152.                         if(fish==1)str += "鱼    ";
  153.                         return str;
  154.                 }
  155.                 return null;
  156.         }

  158. }
复制代码
作者: sanguodouble1    时间: 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动判断，而不是你人为判断好了过河流程，让然再让程序实现你人为的流程，你说对吗？
那么，就开始考虑面对对象思维吧，
1.对象：猫、狗、鱼、船、两岸、人
2.对象的具体属性和方法：
猫：属性，在哪个岸上，傍边是否有人，
       方法：吃鱼
狗：属性：在哪个岸上，傍边是否有人，
      方法：咬猫
鱼：属性：在哪个岸上，傍边是否有人，
     它与世无争，没有什么动作
岸：属性：有哪些个物种
      方法：判断这些物种是否冲突
人：属性：在哪个岸上
船：属性：在哪个岸上
       方法：运输

主程序，判断对岸是否同时具有猫狗鱼和人，如果不是，一直运行船的运输方法
作者: 世界公民    时间: 2014-4-20 11:27
好的，谢谢！！
作者: 呆呆沙师妹    时间: 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
  1. package com.itheima;

  3. import java.util.ArrayList;
  4. import java.util.List;

  6. /**
  7. *
  8. * @author 呆呆沙师妹
  9. * 题目：
  10. * 10、 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
  11. * 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
  12. * 则不会发生这种问题。编程解决猫狗鱼过河问题。
  13. *
  14. * 思路：
  15. * 1、建立两个字符串集合ArrayList来存储河岸两边的动物们，
  16. *    初始时，动物全在河左岸，最终目的是要将河左岸的动物全部运到河右岸；
  17. * 2、定义函数检查当河岸边动物在无老农情况下是否产生动物损失情况；
  18. * 3、定义使用船的次数，
  19. *    当船使用次数为单数时老农在河右岸，只要老农带走的动物后剩下的动物不产生损失，
  20. *    即将带走的动物添加去河右岸集合中；
  21. *    船使用次数为偶数时老农在河左岸；如果河右岸动物们不会产生损失，
  22. *    则老农不带动物回到左岸，否则带走动物保证河右岸动物的安全，将带走动物放回左岸。
  23. * 4、如果河左岸动物为空，则循环结束。
  24. *
  25. */
  26. public class Test10 {

  28.         public static void main(String[] args) {
  29.                 List<String> left = new ArrayList<String>();
  30.                 List<String> right = new ArrayList<String>();
  31.                 left.add( "猫" );
  32.                 left.add( "狗" );
  33.                 left.add( "鱼" );
  34.                
  35.                 int useBoat = 0;
  36.                 String animal = null;
  37.                
  38.                 while( !left.isEmpty() ){
  39.                     useBoat++;
  40.                         animal = null;
  41.                         if( 1 == useBoat % 2 ){
  42.                                 for( int i = 0; i < left.size(); i++ ){
  43.                                         animal = left.remove( i );
  44.                                         if( lossAnimal(left) ){
  45.                                                 left.add( animal );
  46.                                                 continue;
  47.                                         }else{
  48.                                                 break;
  49.                                         }
  50.                                 }
  51.                                 System.out.println( "第" + useBoat + "次, 老农用船将" + animal + "运到河右岸" );
  52.                                 right.add( animal );
  53.                         }else {                       
  54.                                 while( lossAnimal(right) ){
  55.                                         for( int i = 0; i < right.size(); i++ ){
  56.                                                  animal = right.remove( i );
  57.                                                  if( lossAnimal(right) ){
  58.                                                          right.add( animal );
  59.                                                          continue;
  60.                                                  }else{
  61.                                                          break;
  62.                                                  }
  63.                                    }
  64.                                 }
  65.                            if( animal == null ){
  66.                                    System.out.println( "第" + useBoat + "次, 老农用船回到河左岸" );
  67.                            }else{
  68.                                System.out.println( "第" + useBoat + "次, 老农用船将" + animal + "运回河左岸" );
  69.                                left.add( animal );
  70.                            }
  71.                         }
  72.                 }
  73.         }
  74.        
  75.         public static boolean lossAnimal( List<String> list ){
  76.                 if( list.contains("猫") && list.contains("狗") ){
  77.                         return true;
  78.                 }else if( list.contains("猫") && list.contains("鱼") ){
  79.                         return true;
  80.                 }else{
  81.                         return false;
  82.                 }                       
  83.         }
  84. }
复制代码
作者: sanguodouble1    时间: 2014-4-20 18:16
本帖最后由 sanguodouble1 于 2014-4-20 18:18 编辑

从思路到代码，想了很久，没办法，智商有点捉急，附件里是程序代码

说一下主要思路吧，第一想法就是，程序自动判断
这个还算简单，但后来我为了扩展性重构了一下代码，那调debug调的我眼睛都花了

恩，回归正题
1.第一种思路你也知道，就是判读如果猫狗，或者鱼猫在一起，那就是不和谐状态，然后就来回倒腾，这个就不多说了
2.但你说想要扩展一下，什么叫扩展？扩展就是在不改变原有程序代码的情况下增加新的功能。
那我是这样处理的，将这些动物都实现一个接口，这个接口中定义了一个自身是否能处于和谐的状态（无论是骚扰或是被骚扰，都是一种不和谐状态）。
这样的话，以后即使增加了一个新的物种，也只需额外判断它自己是否和谐就可以了，不会对原代码产生影响。

好了，这个是核心思想，具体请看附件

另外，本人从没这么认真回答过问题，希望楼主能认真看下，然后给点建议


interview.rar

4.11 KB, 下载次数: 844
作者: 霍振鹏    时间: 2014-4-20 22:50
sanguodouble1 发表于 2014-4-20 18:16
从思路到代码，想了很久，没办法，智商有点捉急，附件里是程序代码

说一下主要思路吧，第一想法就是，程序 ...

挺好的，我当时做的时候本来想让他自己生成的，后来没解决，，我运行了一下你的程序，其实还有另一种过河方法，就是  先带猫过去，农夫返回带鱼过去，然后将猫带回，之后将狗带过去，最后返回将猫带过去，最好这两种都能自动生成吧！
作者: sanguodouble1    时间: 2014-4-21 13:55
本帖最后由 sanguodouble1 于 2014-4-21 13:58 编辑
霍振鹏 发表于 2014-4-20 22:50
挺好的，我当时做的时候本来想让他自己生成的，后来没解决，，我运行了一下你的程序，其实还有另一种过河 ...

这个其实能实现的，你只要把猫狗鱼放入集合的顺换一下就可以看到你说的这种现象了，代码实现的话就更简单了，用Collections.shuffle()这个方法打乱一下顺序就可以了。

我认为，主要是不足在这个地方：
比如说有好多物种，跟楼主说的一样判断条件很复杂，这时就会出现这种现象：先把A物种弄到对岸，相安无事，然后把B物种弄到对岸，还是相安无事，
但这个，第三趟把C物种弄到对岸后，发现程序无解了，这时候就需要返回到原来的初始状态重新开始，
也就是说，你每一步都需要记录一个状态，当发现下一步无法进行时，就需要恢复这个状态，当这个状态下所有情况都无法满足条件时，你需要恢复再之前的状态。
你跟走象棋悔棋一样，有时候你需要悔好几步才能达到理想状态（突然想起了国际象棋电脑深蓝）

但请原谅以我的智商，无法将这个思想转换成代码

作者: 呆呆沙师妹    时间: 2014-4-21 15:23
sanguodouble1 发表于 2014-4-21 13:55
这个其实能实现的，你只要把猫狗鱼放入集合的顺换一下就可以看到你说的这种现象了，代码实现的话就更简单 ...

学习了，非常感谢你的分享。
作者: 随风而去    时间: 2014-4-22 09:17
呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

目测中，呆呆师妹的方法效率最高
作者: lpc4276139    时间: 2014-8-2 23:08
我想知道，这道题不做的话，其他9道题全做，多少分
作者: 無訫    时间: 2014-8-2 23:29
我是来学习的！{:3_53:}
作者: 贾浩田    时间: 2014-8-3 23:21
sanguodouble1 发表于 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动 ...

思路是纯面向对象的方法，我试了试，写不出来，求请教
作者: 关度飞    时间: 2014-8-11 00:51
嗯嗒 正在写这道题
作者: wfaly    时间: 2014-8-19 09:00
学习学习，谢谢楼主分享...
作者: liwei92244256    时间: 2014-9-17 14:47
感觉逻辑好复杂的赶脚
作者: 任我行    时间: 2014-11-28 20:26
正在写这个……
作者: 佛说    时间: 2014-12-14 17:02
好的，学习了:lol
作者: 好好学    时间: 2015-1-27 21:25
呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

有BUG 你这个一开始把三种动物放入的顺序随便颠倒一下就是死循环
作者: 新生小周    时间: 2015-2-21 23:09
做到这道题了，一看有点发蒙，过年几天有事，也没细想，看了帖子贴出的程序，与自己的想法有相同也有不同，收获很多。
作者: 新生小周    时间: 2015-2-21 23:11
package com.itheima;

import java.util.ArrayList;

/**
* 第10题： 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
*                     当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。编程解决猫狗鱼过河问题。
*
* */

public class Test10 {

        public static void main(String[] args) {
                //存放河岸A（起始位置）现有动物
                ArrayList thisLan = new ArrayList<String>();
                //存放河岸B（起始位置）现有动物
                ArrayList thatLan = new ArrayList<String>();
                //添加动物狗
                thisLan.add("猫");
                //添加动物猫
                thisLan.add("鱼");
                //添加动物鱼
                thisLan.add("狗");
                //老农类，实现所以功能
                Fammer fammer = new Fammer();
                //老农类中的dispose方法，其中调用tothatLan与tothisLan方法
                fammer.dispose(thisLan, thatLan);
        }

        //实现农夫运送动物的功能
       
       
}
class Fammer{
        //元素缓存，辅助tothatLan和tothisLan进行元素删除与恢复
        private String temp;
       
        //步骤记录
        private int time = 1;
        //当老农不在时，判断猫狗鱼三者的关系。如果出现狗会咬猫，猫会吃鱼的情况返回false，否则返回true
        public boolean safe(ArrayList<String> a){
                if((a.contains("狗")&&a.contains("猫")) || (a.contains("猫")&&a.contains("鱼"))){
                        return false;
                }
                return true;
        }
        //从河岸A向河岸B运送动物的方法
        public void tothatLan(ArrayList<String> tis,ArrayList<String> tat){
                //用于while循环
                boolean flag = true;
                while(true){
                        //当河岸A没有动物时说明动物均被带到河岸B
                        if(tis.size()==0){
                                //提示结束
                                System.out.println("结束！");
                                return;
                        }
                        //自动查询符合条件的动物，并带到河岸B
                        for (int i = 0; i < tis.size(); i++) {
                                //缓存，用于删除与恢复动物
                                temp = tis.get(i);
                                if(tis.remove(temp)){                                               
                                        if(this.safe(tis)){
                                                System.out.println("第"+time+"步,将"+temp+"从河岸A运送到河岸B");
                                                time++;
                                                //动物过河
                                                tat.add(temp);
                                                temp = null;
                                                System.out.println("            "+"河岸A有"+tis);
                                                System.out.println("            "+"河岸B有"+tat);
                                                return;
                                        }else{
                                                //恢复删除
                                                tis.add(temp);
                                                continue;
                                        }
                                }else{
                                        continue;
                                }
                        }
                }
        }
        //从河岸B向河岸A运送动物的方法,与tothatLan相似
        public void tothisLan(ArrayList<String> tis,ArrayList<String> tat){
                //用于while循环
                boolean flag = true;
                while(flag){
                        //当河岸B的动物符合要求或没有动物，便不需要将动物带回河岸A
                        if(tat.size()<1 || this.safe(tat)){
                                return;
                        }
                        //自动查询符合条件的动物，并带到河岸A
                        for (int i = 0; i < tat.size(); i++) {
                                //缓存，用于删除与恢复动物
                                temp = tat.get(i);
                                if(tat.remove(temp)){
                                        if(this.safe(tat)){
                                                System.out.println("第"+time+"步,将"+temp+"从河岸B运送到河岸A");
                                                time++;
                                                //动物过河
                                                tis.add(temp);
                                                temp = null;
                                                System.out.println("            "+"河岸A有"+tis);
                                                System.out.println("            "+"河岸B有"+tat);
                                                return;
                                        }else{
                                                //恢复删除
                                                tat.add(temp);
                                                continue;
                                        }
                                }else{
                                        continue;
                                }
                        }
                }
        }
        //自动完成动物过河，调用tothatLan和tothisLan的方法
        public void dispose(ArrayList<String> tis,ArrayList<String> tat){
                boolean flag = true;
                while(flag){
                        //当河岸A没有动物说明动物全部过河
                        if(tis.isEmpty()){
                                return;
                        }
                        this.tothatLan(tis, tat);
                        //当河岸A没有动物说明动物全部过河
                        if(tis.isEmpty()){
                                return;
                        }
                        this.tothisLan(tis, tat);
                }
        }
       
}
作者: 火星人_AS    时间: 2015-3-12 17:41
[code]package com.itheima;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/*
* 题目10：10、 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
*                                当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。
*                编程解决猫狗鱼过河问题。
*      
* 分析思路： 在纸上分析过后得知要像将猫、狗、鱼安全的送往河对岸，可使用下述步骤：
*                    第一步：将猫先运到河对岸 ，放下猫农夫和船回来；           ====> 已过河： 猫
*                    第二步：将狗装上船运到河对岸，并且将猫带回放下；        ====> 已过河： 狗
*                    第三步：将鱼运过对岸放下，农夫空船回来；                        ====> 已过河： 狗、鱼
*                    第四步：农夫将猫再次运到河对岸。                                        ====> 已过河： 狗、鱼、猫
*/
public class Test10 {

        // 1：因为数据长度频繁的改变所以，用集合来装数据。并且将河的两边比喻为两个不同的集合
        // left :表示左边的河岸 right：表示右边的河岸也就是对岸。
         List<String> left = new ArrayList<String>();
         List<String> right = new ArrayList<String>();

        // 2：因为一开始河的左岸就是有人和三个动物的，所以程序一加载就应该添加他们
        public Test10() {
                left.add("farmers");
                left.add("cat");
                left.add("dog");
                left.add("fish");
        }

        public static void main(String[] args) {
                // 调用过河方法
                Test10 test = new Test10();
                /*for (String string : test.left) {
                        System.out.println(string);
                }*/
                test.passRiver();
        }

        // 过河的方法
        public void passRiver() {
                do {
                        // 首先农夫上船
                        left.remove("farmers");

                        // 接着农夫随便的带上一只动物上船，利用脚标取值，脚标随机并且在[1,4）之间，对应 cat、dog、fish
                        // 产生随机数，可以使用Random类中的nextInt(int num);方法产生一个在[0,num)之间的数
                        int leftIndex = new Random().nextInt(left.size());  /*IllegalArgumentException：抛出的异常表明向方法传递了一个不合法或不正确的参数。*/
                        
                        // 取得脚标所对应的动物，并装上船
                        String animal = left.get(leftIndex); /*IndexOutOfBoundsException：脚标越界*/
                        
                        //判断农夫现在带走的动物是否是上一次带回来的动物(因为每次都会自动的添加到最后一个)
                        if (left.size()>1 && animal.equals(left.get(left.size()-1))) {
                                left.add("farmers");
                                //跳出当前循环，进入下一个循环
                                continue;
                        }
                        left.remove(animal);

                        // 此时left的岸边只有两个动物了，并且我们不确定这两个其中是否有猫，所以得判断
                        if (isSafe(left)) {
                                // 将左边的动物带到河对岸。
                                right.add(animal);
                                System.out.println("恭喜农夫和"+"\'"+animal+"\'"+"成功渡河！");
                                // 此时如果河对岸有3个动物，并且不包括农夫的话就算过河都成功返回
                                if (right.size() == 3 && !right.contains("farmers")) {
                                        System.out.println("恭喜狗、猫、鱼渡河成功！！！");
                                        break;
                                }

                                // 此时农夫准备返航回去，那么就得判断农夫离开后河对岸（right）是否安全
                                // 但是如果对岸只有一个动物的话就没有必要判断了
                                if (right.size() != 1) {
                                        if (isSafe(right)) {
                                                left.add("farmers");
                                                System.out.println("农夫独自返航了！");
                                        } else {
                                                // 获取对岸动物的脚标
                                                int rightIndex = new Random().nextInt(right.size());
                                                // 获取脚标对应的动物名
                                                String animal2 = right.get(rightIndex);
                                                // 如果不安全，则要带回一个动物，但是不能是前一次带过来的动物。
                                                while (animal2.equals(animal)) {
                                                        animal2 = right.get(rightIndex);
                                                }
                                                //将非上一次带过来的动物从对岸带回
                                                right.remove(animal2);
                                                left.add(animal2);

                                                System.out.println("农夫和" + "\'" + animal2 + "\'回来了");

                                        }
                                } else {
                                        left.add("farmers");
                                        System.out.println("农夫独自返航了！");
                                }

                        } else {
                                // left岸边的动物们不安全，把带上的动物放下换一个
                                left.add("farmers");
                                left.add(animal);
                        }

                } while (left.size() != 0);
        }

        // 判断是否安全的方法,返回的是boolean类型的值
        private static Boolean isSafe(List<String> list) {
                // 定义一个变量用来接收返回的值
                Boolean flag;

                // 判断两边岸的动物是否安全的依据是看猫和农夫是否在一起，如果农夫和猫不在一起并且猫和其他的动物在一起，则河岸不安全。
                if (list.size() > 1 && list.contains("cat") && list.contains("cat")
                                || list.contains("cat") && list.contains("fish")) {
                        flag = false;
                } else {
                        flag = true;
                }

                return flag;
        }

}
[/code]
作者: luke_yang    时间: 2015-3-13 21:02
这题我头疼
作者: jackwang    时间: 2015-4-17 21:54
sanguodouble1 发表于 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动 ...

    哥们，这个问题，你就不要人为的复杂化了，也不要求一个通用解，如果非要求一个通用解，那么只是适合于A,B，C这种模式，也即狗、猫、鱼。
    这个问题抽象出来后和你举得那个扩展例子抽象出来后不是一个类型的问题，好比x2和x3的方程的解决方法和解决需要的条件不同一样，看似类似，实则不同。
    猫狗鱼问题抽象出来后，是"A->B->C"，这个模式的问题，优先运走，度为2的对象（即B），而且这个有向图中不允许存在两个度为2的对象，也不允许存在度为3的对象，这个度包括出度和入度。否则，就是无解。
所以，这个问题主要是用来锻炼大家的对象抽取能力和设计能力，以及问题的分析能里。
      
     这个不是一个可以扩展的问题，要扩展也只能扩展成（A->B->C   D->E->F），你的扩展就属于另一个问题，不属于和原问题同类型的问题了。用到的东西可能会更多，问题难度要大很多。3个的可能只是一个特例。这个就好比2重积分可以看成是3重积分的一个特例一样，但是3重积分的解法是更复杂的问题。
     最后，真想扩展，那你也要先固定好到底是几个对象，几个约束条件，几个可以渡河运送人的等等，不固定，就谈不上问题的通解，尤其使用程序来做这件事，也许数学还可以有通解。
作者: jackwang    时间: 2015-4-17 21:59
另外，这个问题可以谈对象抽取和方法封装的设计，谈类的设计，至于算法的高效，到底用广搜和深搜，还是自动机，动态规划，又是状态之类的，其实没有太大意思。这是个较为特殊的特例问题，而且解决方案也较为单一的问题，不是什么需要大优化之类的问题规模很大的问题。
作者: 知识改变人生    时间: 2015-5-8 21:45
高手啊
作者: Melo    时间: 2015-5-21 22:11
这题知道怎么过 可是一到代码上就懵圏了
作者: 7shashaai    时间: 2015-6-4 11:23
我是来学习的。。
作者: l598790586    时间: 2015-6-7 20:22
呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

你的实现不了，只要把集合中鱼的位置排到第一位，你循环几千次都出不来
作者: 不安静的丑男子    时间: 2015-6-12 17:55
我也正在写这道题！！
作者: RockLee    时间: 2015-6-15 13:48
很不错，是大神
作者: 导航    时间: 2015-7-1 16:59
关度飞 发表于 2014-8-11 00:51
嗯嗒 正在写这道题

刚看到你写的时间，话说你现在工作多久了？感觉怎么样呢
作者: 导航    时间: 2015-7-9 19:28
逻辑最简单了，算法怎么才能最好呢
作者: 导航    时间: 2015-7-15 09:27
看了好几天了
作者: 360638403    时间: 2015-7-27 09:36
都是面向对象的思想,,难道社招的难度大那么多?
作者: 暴走的牛奶    时间: 2015-8-11 00:53
呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

真心点赞,写不出来
作者: 导航    时间: 2015-8-14 19:43
楼主成功运行了吗，我怎么在自己的电脑上变异不上呢
作者: wangquanjava    时间: 2015-9-11 19:02
呆呆沙师妹 发表于 2014-4-20 13:51
我也碰上过这个题。想了好久才做出来。
在这里也分享一下自己的思路，期待有更好的算法。
...

写的很好，不过有一个地方有Bug，
if( lossAnimal(left) ){
    left.add( animal );
    continue;
}

把动物remove()以后，再添加时，如果不加用添加的位置，就会默认放在后面，这样在遍历时就出现了Bug
作者: 崔判官    时间: 2015-11-5 18:16
第一步：把猫带过去；
第二步：农夫回来把鱼（狗）带过去；
第三步：农夫回来的时候把猫带回来再把狗（鱼）带过去；
第四步：农夫在回来把猫带过去。
作者: dg216888    时间: 2015-11-15 09:25
学习学习
作者: 马官聘    时间: 2015-12-28 16:50
sanguodouble1 发表于 2014-4-20 11:24
这个问题很有意思，先说下我的思路吧，代码有空再写
我觉得，关键是以程序的方法去实现，也就是让程序自动 ...

这样一份感觉思路清晰多了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2