A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© lwy0319 高级黑马   /  2014-3-10 12:40  /  10219 人查看  /  22 人回复  /   1 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 lwy0319 于 2014-3-22 00:17 编辑

大家好,我是来自海淀区的新人,刚刚通过云九班报名的基础测试,希望还能赶上与大家做同学的机会
我做基础测试耽误时间最久的就是最后一题
题目如下:
一位老农带着猫、狗、鱼过河,河边有一条船,每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时,狗会咬猫,猫会吃鱼,当老农和猫狗鱼在一起时,则不会发生这种问题。
PS:这个是道经典的逻辑题,所以大家可能很早就有接触了
我个人感觉这题的编码难点跟逻辑推断难点是一致的:怎么去想到带猫从对岸回来/怎么让程序自己做出这个选择
我自己花了5个写了个很繁琐的算法,也在网上看了一些答案,但是目前找到解答难点的
基本上不约而同的讲把猫带回或者把动物带回当作是一种已经存在方案然后备选,而不是让程序自己递推出来
我自己也没做到,但是我还是感觉一段程序,自己加入的逻辑思路的痕迹越少越好
附件是我的代码,希望大家能给予我指点

农夫带猫狗鱼.rar

3.75 KB, 下载次数: 1362

评分

参与人数 1技术分 +1 收起 理由
朱神必 + 1

查看全部评分

22 个回复

倒序浏览
楼主最后虽然得到了正确的结果,但是最后输出结果不够清晰,而且程序执行的每一步都是跟着你的思想在进行,没有一点程序自己的选择,这是我写的,可以交流一下

Test10.rar

1.34 KB, 下载次数: 1693

评分

参与人数 1技术分 +1 收起 理由
朱神必 + 1

查看全部评分

回复 使用道具 举报 1 0
谢谢你,比我写得简练多了,其实我还是尽量让系统自己判断的,只不过用了循环,恨不得每一步都进行了循环并在内部进行判断,现在看来还是挺繁琐的,我为了让他们正常的按组内的索引编号循环下去,每次不得不复位直到找到正确答案才真正进行remove和add操作,你的比我的优化了很多,多谢指教了
回复 使用道具 举报

RE: 关于农民带猫狗鱼过河的问题

呃。。怎么结帖。。没找到哪儿能改成已解决
回复 使用道具 举报
都是大神呀,我就写了几行代码哈。。。
回复 使用道具 举报
想了半天,没搞清思路。还是参考下大神的答案吧
回复 使用道具 举报
刘望望童鞋确实思路清晰,领教了
回复 使用道具 举报
经典的题目...
回复 使用道具 举报
chensc 金牌黑马 2014-6-18 08:05:33
9#
学习学习!
回复 使用道具 举报
思路清晰就好
回复 使用道具 举报
这也是我的基础测试题最后一题,没有思路,正在膜拜大神的杰作
回复 使用道具 举报
wfaly 中级黑马 2014-8-19 08:22:13
12#
谢谢,楼主分享...
回复 使用道具 举报
我也在想这问题 这题目看着简单 想想要做好 还是有一点难度的
回复 使用道具 举报
刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果,但是最后输出结果不够清晰,而且程序执行的每一步都是跟着你的思想在进行, ...

厉害!!!
回复 使用道具 举报
真心不错
回复 使用道具 举报
刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果,但是最后输出结果不够清晰,而且程序执行的每一步都是跟着你的思想在进行, ...

public boolean isSafe(List<String> list)
        {
                boolean b = true;
               
                //如果某一边没有人,猫单独和其他动物在一起,则不和谐
                if(list.size() > 1 && list.contains("cat") && !list.contains("person"))
                {
                        b = false;
                }
               
                return b;
        }
这个函数为什么要boolean b = true;  直接return true,不可以吗?  有什么特别的?
回复 使用道具 举报
刘望望 发表于 2014-3-10 22:56
楼主最后虽然得到了正确的结果,但是最后输出结果不够清晰,而且程序执行的每一步都是跟着你的思想在进行, ...

你好!在吗?/我在网上看到你的一份关于农夫过河的问题!有个问题想请教你
回复 使用道具 举报
lwy0319 发表于 2014-3-11 11:02
谢谢你,比我写得简练多了,其实我还是尽量让系统自己判断的,只不过用了循环,恨不得每一步都进行了循环并 ...

楼上的好像有点问题啊
回复 使用道具 举报
学习啊了,厉害!
回复 使用道具 举报
  1. package com.itheima;

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

  5. /**
  6. * 10、 一位老农带着猫、狗、鱼过河,河边有一条船,每次老农只能带一只动物过河。当老农不和猫狗鱼在一起时, 狗会咬猫,猫会吃鱼,当老农和猫狗鱼在一起时,
  7. * 则不会发生这种问题。编程解决猫狗鱼过河问题。
  8. *
  9. * 分析:
  10. *         假设动物和老农都在左岸,要到达右岸
  11. *                 第一步:老农带着猫到达右岸
  12. *                 第二步:老农一个返回左岸
  13. *                 第三步:老农带着狗或者鱼到达右岸
  14. *                 第四步:老农带着猫返回左岸
  15. *                 第五步:老农带着非猫的动物到达右岸
  16. *                 第六步:老农一个人返回左岸
  17. *                 第七步:老农带着猫到达右岸
  18. *                 过河完成!
  19. *
  20. * 把整个过河问题分为从左岸到右岸,从右岸到左岸这两个动作问题。
  21. * 老农从左岸到右岸,必须带着动物,否则没有任何意义,并且该动物不能为上次从右岸返回到左岸的动物。老农从右岸到左岸,
  22. * 如果可以不带动物,则不带,效率高,否则必须带一个动物返回左岸,并且该动物不能为上次从左岸到达右岸的动物。
  23. *
  24. * 采用过程追溯法来是实现过河问题,不满足条件追溯回原状态,知道满足条件为止。
  25. *
  26. * @author liuxiangyun
  27. *
  28. */
  29. public class Test10 {
  30.         List<String> leftBank = new ArrayList<String>();// 左岸
  31.         List<String> rightBank = new ArrayList<String>();// 右岸

  32.         public static void main(String args[]) {
  33.                 new Test10().crossRiver();
  34.         }

  35.         public Test10() {
  36.                 // 初始化数据
  37.                 leftBank.add("person");
  38.                 leftBank.add("fish");
  39.                 leftBank.add("cat");
  40.                 leftBank.add("dog");
  41.         }

  42.         // 过河
  43.         public void crossRiver() {
  44.                 boolean isAtLeftBank = true;// 老农是否在左边
  45.                 String lastToLeftAnl = "";// 上一个到左边去的动物,默认没有,用""表示
  46.                 String lastToRightAnl = "";// 上一个到右边去的动物,默认没有,用""表示
  47.                 while (leftBank.size() > 0) {
  48.                         //从左岸到右岸
  49.                         if (isAtLeftBank) {
  50.                                 lastToRightAnl = toRight(lastToLeftAnl);
  51.                                 System.out.println("老农带着{" + lastToRightAnl + "}到达右岸");
  52.                                 isAtLeftBank = false;
  53.                         //从右岸到左岸
  54.                         } else {
  55.                                 lastToLeftAnl = toLeft(lastToRightAnl);
  56.                                 if (lastToLeftAnl == "")
  57.                                         System.out.println("老农一个人回到左岸");
  58.                                 else
  59.                                         System.out.println("老农带着{" + lastToLeftAnl + "}到达左岸");
  60.                                 isAtLeftBank = true;
  61.                         }
  62.                 }
  63.                 System.out.println("老农和动物全部过河!");
  64.         }

  65.         /**
  66.          * 从左岸到右岸,老农必须携带一个动物,否则没有任何意义,并且要保证左右岸不出现安全问题
  67.          *
  68.          * @param lastToLeftAniaml
  69.          *            上一个到左岸去的动物,没有则用""表示
  70.          * @return 返回要携带的动物
  71.          */
  72.         public String toRight(String lastToLeftAniaml) {
  73.                 boolean flag = true;
  74.                 String animal = null;
  75.                 while (flag) {
  76.                         leftBank.remove("person");
  77.                         animal = leftBank.get(new Random().nextInt(leftBank.size()));// 随机获取一个动物
  78.                         leftBank.remove(animal);
  79.                         rightBank.add("person");
  80.                         rightBank.add(animal);
  81.                         if (isSafe() && (animal != lastToLeftAniaml)) {// 不是上一个去左边的动物,并且不产生和谐问题
  82.                                 flag = false;
  83.                         } else {
  84.                                 rightBank.remove("person");
  85.                                 rightBank.remove(animal);
  86.                                 leftBank.add("person");
  87.                                 leftBank.add(animal);
  88.                         }
  89.                 }
  90.                 return animal;
  91.         }

  92.         /**
  93.          * 从左岸到右岸,老农独自返回,如果没有产生安全问题,他就独自返回,否则必须携带一个动物返回左岸,并且也要保证不产生安全问题。
  94.          *
  95.          * @param lastToRightAniaml
  96.          *            上一个到达右岸的动物
  97.          * @return 返回要携带的动物,没有则返回""
  98.          */
  99.         public String toLeft(String lastToRightAniaml) {
  100.                 String animal = null;
  101.                 rightBank.remove("person");
  102.                 leftBank.add("person");
  103.                 if (isSafe()) {
  104.                         return animal = "";
  105.                 } else {
  106.                         leftBank.remove("person");
  107.                         rightBank.add("person");
  108.                         boolean flag = true;
  109.                         while (flag) {
  110.                                 rightBank.remove("person");
  111.                                 animal = rightBank.get(new Random().nextInt(rightBank.size()));// 随机获取一个动物
  112.                                 rightBank.remove(animal);
  113.                                 leftBank.add("person");
  114.                                 leftBank.add(animal);
  115.                                 if (isSafe() && (animal != lastToRightAniaml)) {// 不是上一个去右边的动物,并且不产生和谐问题
  116.                                         flag = false;
  117.                                 } else {
  118.                                         leftBank.remove("person");
  119.                                         leftBank.remove(animal);
  120.                                         rightBank.add("person");
  121.                                         rightBank.add(animal);
  122.                                 }
  123.                         }
  124.                 }
  125.                 return animal;
  126.         }

  127.         // 判断左右岸是否存在安全问题
  128.         public boolean isSafe() {
  129.                 boolean leftBankIsSafe = true;
  130.                 boolean rightBankIsSafe = true;
  131.                 // 岸上没有老农,有猫且有狗或者鱼就存在安全问题
  132.                 if (!leftBank.contains("person") && leftBank.contains("cat")
  133.                                 && leftBank.size() > 1)
  134.                         leftBankIsSafe = false;
  135.                 if (!rightBank.contains("person") && rightBank.contains("cat")
  136.                                 && rightBank.size() > 1)
  137.                         rightBankIsSafe = false;
  138.                 return leftBankIsSafe && rightBankIsSafe;
  139.         }
  140. }
复制代码
回复 使用道具 举报
12下一页
您需要登录后才可以回帖 登录 | 加入黑马