黑马程序员技术交流社区

标题: 我写的用递归解决狗猫鱼和农夫 [打印本页]

---

作者: qq474249147    时间: 2014-6-14 15:53
标题: 我写的用递归解决狗猫鱼和农夫
我觉得中间环节有点繁琐，
package com.itheima;
import java.util.Scanner;
/**
* 第10题： 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
* 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，
* 则不会发生这种问题。编程解决猫狗鱼过河问题。
*/
import java.util.Vector;
/**第10题： 一位老农带着猫、狗、鱼过河，河边有一条船，每次老农只能带一只动物过河。
* 当老农不和猫狗鱼在一起时，狗会咬猫，猫会吃鱼，当老农和猫狗鱼在一起时，则不会发生这种问题。
* 编程解决猫狗鱼过河问题。
*
* @author Administrator
*
*/

public class Test10 {

public static Vector<Pos> path;
        public static void main(String[] args) {
                // TODO 自动生成的方法存根
                Scanner cin=new Scanner(System.in);
        Side side=new Side();
        path=side.move(0);
        if(path!=null){
                for(int i=path.size()-1;i>=0;i--){
                        int n=(path.size()-i-1);
                        System.out.println("第"+n+"步:");   
                        display(path.get(i).dog_here, "dog");  //输出函数
                        display(path.get(i).cat_here,  "cat ");
                        display(path.get(i).fish_here, "fish");
                        display(path.get(i).man_here,"man");
                }
        }else{
                System.out.println("no result");
        }
        int input=cin.nextInt();
        }
        public static void display(Boolean b,String s){
                if(!b){
                        System.out.println("          |     |"+s);                       
                }else{
                        System.out.println(s+"    |     |          ");
                }
        }
}
class Side{          //定义一个Side类，4个boolean分别表示狗，猫，鱼，人的位置，ture表示在原来那边，false表示在对岸
        public  boolean dog_here=true;
        public  boolean cat_here=true;
        public  boolean fish_here=true;
        public  boolean man_here=true;
        public  Vector<Pos> path;        //当按照规则成功到达对岸时，用于保存移动的路径
        public int pathlength;               //用于存储移动路径的长度，即步数
        public static final int maxpath=10;  //当步数过大依然没结果时终止程序，防止无限递归
       
        public Side(Pos pos){            //接受前一个位置状态Pos的构造函数
                this.dog_here=pos.dog_here;      
                this.cat_here=pos.cat_here;
                this.fish_here=pos.fish_here;
                this.man_here=pos.man_here;
        }
        public Side(){}            
       
        public boolean all_animal_alive(){   //判断当前状态下所有动物是否都活着，
                return!(((dog_here)&&(cat_here)&&(!man_here))||
                                ((!dog_here)&&(!cat_here)&&(man_here))||
                                ((fish_here)&&(cat_here)&&(!man_here))||
                                ((!fish_here)&&(!cat_here)&&(man_here)));
        }
        public boolean success(){             //判断是否全部都到了对岸
                return!(dog_here||cat_here||fish_here||man_here);
        }
        public Vector<Pos> move(int pathlength){ //用于寻找下一个可能的状态，当该路径失败时返回null，成功则返回状态
                pathlength++;
                if(pathlength>=maxpath)      //递归过深则停止
                        return null;                        
                if(this.all_animal_alive()){     //只有当当前状态下所有动物都活着才有必要下一步
                    if(success()){               //当成功时返回一个path路径，并将本次状态pos作为第一个元素
                                         path=new Vector<>();
                                         path.add(new Pos(dog_here, cat_here, fish_here, man_here));
                                         return path;       
                    }
                    
                    Vector<Vector<Pos>> path_group=new Vector<>();
                   /* 任何状态下下一个移动都只有4种可能性:
                    * （1）狗和人在同一边，向另一边移动；
                    * （2）猫和人在同一边，向另一边移动；
                    * （3）鱼和人在同一边，向另一边移动；
                    * （4）人单独从对岸向原岸移动。
                    * path_group用于保存4种可能性下的路径，失败则为null
                    * 从不为null的路径中选择最短路径返回到上一层调用
                    */
                        if((man_here&&fish_here)||(((!man_here)&&(!fish_here)))){
                                Pos pos2=new Pos(dog_here, cat_here, !fish_here, !man_here);                       
                                        Side side2=new Side(pos2);
                                   path_group.add(side2.move(pathlength));
       
                        }
                        if((man_here&&dog_here)||(((!man_here)&&(!dog_here)))){
                                Pos pos3=new Pos(!dog_here, cat_here, fish_here, !man_here);                       
                                Side side3=new Side(pos3);
                                 path_group.add(side3.move(pathlength));
                        }
                        if((man_here&&cat_here)||(((!man_here)&&(!cat_here)))){
                                Pos pos4=new Pos(dog_here, !cat_here, fish_here, !man_here);                       
                                Side side4=new Side(pos4);
                                 path_group.add(side4.move(pathlength));
                        }
                        if(!man_here){
                                Pos pos5=new Pos(dog_here, cat_here, fish_here, !man_here);                       
                                Side side5=new Side(pos5);
                                 path_group.add(side5.move(pathlength));
                        }
                         
                    Vector<Pos> result=null;
                    int minpath=maxpath+1;
                    for(int i=0;i<path_group.size();i++){
                            if(path_group.get(i)!=null){                 //挑选出不为null的最短路径并把自己的状态添加到路径末尾
                                    if(minpath>path_group.get(i).size()){
                                            minpath=path_group.get(i).size();
                                            result=path_group.get(i);
                                    }
                            }
                    }
                    if(result!=null){           
                            Pos this_pos=new Pos(dog_here, cat_here, fish_here, man_here);
                            result.add(this_pos);
                             return result;  
                    }                                //把路径返回到上一层调用
        }
    return null;         //当有动物死去则失败返回null
}
}
class Pos{             //pos类，用于存储状态
        public  boolean dog_here=true;
        public  boolean cat_here=true;
        public  boolean fish_here=true;
        public  boolean man_here=true;
        public Pos(Boolean dog,Boolean cat,Boolean fish,Boolean man){
                this.dog_here=dog;
                this.cat_here=cat;
                this.fish_here=fish;
                this.man_here=man;
        }
}

---

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

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