黑马程序员技术交流社区

标题: 猫狗鱼过河问题(写的有点简单，不知大家还是否有更好的解法，求指教) [打印本页]

---

作者: 乐成    时间: 2015-6-8 20:13
标题: 猫狗鱼过河问题(写的有点简单，不知大家还是否有更好的解法，求指教)
package com.itheima;

import java.util.ArrayList;


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

/**
* 题目分析:
* 假设开始时农夫带着猫，狗和鱼都在河岸左边，农夫要带这些动物去河岸右边。
* 因为狗会咬猫，猫会吃鱼，所以当农夫不在时，不能让猫和狗或者是猫和鱼
* 同时待在一个地方，只能让狗和鱼待在同一个地方，而农夫在时三者可以共存
* 方法一:
*                 第一次：农夫把猫从河岸左边带到河岸右边，左边：狗和鱼，右边:猫和农夫。
*                 第二次: 农夫单独返回到河岸左边，左边：农夫，狗和鱼,右边:猫。
*                 第三次: 农夫把狗从河岸左边带到河岸右边，左边:鱼，右边:农夫，猫和狗。
*                 第四次：农夫把猫从河岸右边带回河岸左边，左边:农夫，猫和鱼，右边：狗。
*                 第五次: 农夫把鱼从河岸左边带到河岸右边，左边：猫，右边：农夫，狗和鱼
*                 第六次： 农夫单独返回到河岸左边，左边:农夫和猫，右边：狗和鱼
*                 第七次：农夫把猫从河岸左边带到河岸右边，左边：无，右边：农夫,猫,狗和鱼。
*
*/
public class Test10 {

        //定义两个list集合，一个用来存放河岸左边的动物，一个用来存放河岸右边的动物
        private static ArrayList<String> left = new ArrayList<String>();               
        private static ArrayList<String> right = new ArrayList<String>();               
       
        //定义三个动物的字符串变量
        private static String cat = "猫";
        private static String dog = "狗";
        private static String fish = "鱼";
        private static String farmer = "农夫";
       
        /**
         * 主函数
         * @param args
         */
        public static void main(String[] args) {
               
                new Test10();                //对自定义构造函数进行初始化
                move();                         //调用农夫运动物过河的函数
               
        }
        //构造函数初始化，一初始化就往河岸左边的集合中添加农夫，猫，狗和鱼(farmer,cat,dog,fish)
        public Test10()
        {
                left.add(farmer);
                left.add(cat);
                left.add(dog);
                left.add(fish);
        }
       
        /**
         * 定义农夫运动物过河的函数
         */
        public static void move()
        {
                int time = 0;                                //定义一个整形变量，用来记录农过河的次数
                String animal = null;                //定义一个字符串变量，用来记录要运过河的动物
                while(!left.isEmpty())
                {
                        time++;                                        //计算次数
                        animal = null;                        //初始化为空
                        if(time%2==1)                        //次数为奇数时，表示农夫把动物从河岸左边往河岸右边运
                        {
                                for(int x=0;x<left.size();x++)
                                {
                                        left.remove(farmer);
                                        animal = left.remove(x);        //农夫把河岸左边一个动物运到河岸右边去
                                       
                                        //如果河岸左边，安全，则往河岸右边添加该动物，同时往河岸右边添加农夫
                                        if(isSafe(left))                       
                                        {
                                                right.add(animal);       
                                                right.add(farmer);
                                                break;
                                        }else{                                //如果不安全,则结束本次循环，继续下一次循环
                                                left.add(animal);        //左边动物不安全，恢复删除
                                                //left.add(farmer);
                                                continue;
                                        }
                                }
                                System.out.println("第"+time+"次：农夫把"+animal+"从河岸左边->河岸右边\t"+"河岸左边:"+left+", 河岸右边:"+right);
                               
                        }else{                                                        //次数为偶数时，表示农夫从河岸左边回河岸右边，有可能是单独回，也有可能是带走一个动物回
                                //当河岸右边动物之间不安全时，则进行循环，否则结束循环
                                while(!isSafe(right))
                                {
                                        for(int x=0;x<right.size();x++)
                                        {
                                                //因为河岸右边是不安全的，所以农夫在返回河岸左边的时候，要带回一个动物
                                                right.remove(farmer);                       
                                                animal = right.remove(x);
                                                //如果该动物被带回后河岸右边是安全的，则往河岸左边添加该动物，同时农夫也回到河岸左边
                                                if(isSafe(right))
                                                {
                                                        left.add(animal);
                                                        left.add(farmer);
                                                        break;
                                                }else{                                //如果不安全,则结束本次循环，继续下一次循环
                                                        right.add(animal);        //右边动物不安全，恢复删除
                                                        //right.add(farmer);
                                                        continue;
                                                }
                                        }
                            }

                                 if(animal==null)
                                 {
                                         right.remove(farmer);
                                         left.add(farmer);
                                         System.out.println("第"+time+"次：农夫划船独自回河岸左边             \t"+"河岸左边:"+left+", 河岸右边:"+right);
                                 }
                                 else
                                          System.out.println("第"+time+"次：农夫把"+animal+"从河岸右边->河岸左边\t"+"河岸左边:"+left+", 河岸右边:"+right);
                        }       
                }
                System.out.println("猫狗鱼成功过河，问题解决了！");  
        }
       
        //当农夫不在时，猫和狗或者猫和鱼在同一河岸时，是不安全的，返回false，否则是安全的，返回true
        public static boolean isSafe(ArrayList<String> list)
        {
                if(list.contains(dog)&&list.contains(cat))
                        return false;
                else if(list.contains(cat)&&list.contains(fish))
                        return false;
                else
                        return true;
        }

}

---

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

黑马程序员IT技术论坛 X3.2