java 有关人鬼过河的一个问题

Question

3人3鬼在一条河岸的一边，都要到河的另一边去，河边停靠有一条船，最多可以载一人一鬼，或2鬼，或2人，不论何时不管河岸的那一边只要鬼的数量超过人的数量，鬼都会吃掉人导致过河失败：用java 找出过河的方法，网上有人说用树，可想了很久不知道怎么建这棵树啊........只怪算法和数据结构学得太烂....
那位高人能给点提示呢-----不胜感激啊

Answer 1

package com;import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;public class PassRiver {
/**
 * set 1 is replace of human 0 is replace of ghost
 */
String a = "1", b = "1", c = "1", d = "0", e = "0", f = "0"; static Map map = getMap(); public void topassriver() {
String[] a = getData();
/**
 * 这种嵌套循环有点象排序算法不符合要求继续
 */
for (int i = 0; i < a.length - 1; i++) { for (int j = i; j < a.length; j++) {
takeBoat(a[i], a[j]);
}
}
} /**
 * 类似递归
 */
int i = 0; public void topassriver2() {
String[] a = getData();
for (int j = i; j < a.length; j++) {
takeBoat(a[i], a[j]);
}
if (i++ < a.length - 1) {
topassriver2();
}
} public static void main(String[] args) {
PassRiver passRiver = new PassRiver();
passRiver.topassriver2(); } /**
 * tabe boat to pass river
 * 
 * @param a
 *            human or ghost
 * @param b
 *            human or ghost
 */
public static void takeBoat(String a, String b) { if (map.get(a).equals(map.get(b))) { if (map.get(a).equals("1")) {
// System.out.println(a + " and " + b + " is man" + ""); }
if (map.get(a).equals("0")) {
// System.out.println(a + " and " + b + " is ghost"); }
} else {
// a or b one is human and the other is ghost
System.out.println(a + " and " + b + " is can take boat" + "");
} } public static String[] getData() {
String[] a = new String[6];
int k = 0;
// if two human or two ghost is boat
Iterator iterator = map.keySet().iterator(); while (iterator.hasNext()) {
a[k] = (String) iterator.next();
k++;
}
return a;
} /**
 * 
 * @return
 */
public Map toPass() { return null;
} public static Map getMap() {
Map map = new HashMap();
map.put("a", "1");
map.put("b", "1");
map.put("c", "1");
map.put("d", "0");
map.put("e", "0");
map.put("f", "0");
return map;
}}

Answer 2

 public static void main(String[] args) {
        PassRiver passRiver = new PassRiver();
       //递归
        passRiver.topassriver2();
      // 循环选择
      passRiver.topassriver();    }

Answer 3

有这个flash游戏的,玩一遍就知道了

Answer 4

以前耍过这样的FLASH 游戏～～顶下

Answer 5

这个游戏NDS的莱顿教授里面玩过，呵呵
不过怎么用没想到怎么算法来的
MARK 学习一下

Answer 6

int r=3,g=3;
public void cross(){
if(r>=g||3-r>=3-g){
r--;

}else{
g--;
}
this.cross();
}

Answer 7

  &   study

Answer 8

我的思路和想法是这样的啊
package com;import java.util.*；public class PassRiver {
    /**
     * set 1 is replace of human 0 is replace of ghost
     */
    String a = "1", b = "1", c = "1", d = "0", e = "0", f = "0";    static Map map = getMap();    public void topassriver() {
        String[] a = getData();
        /**
         * 这种嵌套循环有点象排序算法不符合要求继续
         */
        for (int i = 0; i < a.length - 1; i++) {            for (int j = i; j < a.length; j++) {
                takeBoat(a[i], a[j]);
            }
        }
    }    /**
     * 类似递归
     */
    int i = 0;    public void topassriver2() {
        String[] a = getData();
        for (int j = i; j < a.length; j++) {
            takeBoat(a[i], a[j]);
        }
        if (i++ < a.length - 1) {
            topassriver2();
        }
    }    public static void main(String[] args) {
        PassRiver passRiver = new PassRiver();
        passRiver.topassriver2();    }    /**
     * tabe boat to pass river
     * 
     * @param a
     *            human or ghost
     * @param b
     *            human or ghost
     */
    public static void takeBoat(String a, String b) {        if (map.get(a).equals(map.get(b))) {            if (map.get(a).equals("1")) {
                // System.out.println(a + " and " + b + " is man" + "");            }
            if (map.get(a).equals("0")) {
                // System.out.println(a + " and " + b + " is ghost");            }
        } else {
            // a or b one is human and the other is ghost
            System.out.println(a + " and " + b + " is can take boat" + "");
        }    }    public static String[] getData() {
        String[] a = new String[6];
        int k = 0;
        // if two human or two ghost is boat
        Iterator iterator = map.keySet().iterator();        while (iterator.hasNext()) {
            a[k] = (String) iterator.next();
            k++;
        }
        return a;
    }    /**
     * 
     * @return
     */
    public Map toPass() {        return null;
    }    public static Map getMap() {
        Map map = new HashMap();
        map.put("a", "1");
        map.put("b", "1");
        map.put("c", "1");
        map.put("d", "0");
        map.put("e", "0");
        map.put("f", "0");
        return map;
    }}

Answer 9

这个flash游戏，我是玩过了的，但是数据结构方面还真没想过。

Answer 10

我的思路和想法是这样的啊 
package   com; import   java.util.*； public   class   PassRiver   { 
        /** 
          *   set   1   is   replace   of   human   0   is   replace   of   ghost 
          */ 
        String   a   =   "1 ",   b   =   "1 ",   c   =   "1 ",   d   =   "0 ",   e   =   "0 ",   f   =   "0 ";         static   Map   map   =   getMap();         public   void   topassriver()   { 
                String[]   a   =   getData(); 
                /** 
                  *   这种嵌套循环有点象排序算法不符合要求继续 
                  */ 
                for   (int   i   =   0;   i   <   a.length   -   1;   i++)   {                         for   (int   j   =   i;   j   <   a.length;   j++)   { 
                                takeBoat(a[i],   a[j]); 
                        } 
                } 
        }         /** 
          *   类似递归 
          */ 
        int   i   =   0;         public   void   topassriver2()   { 
                String[]   a   =   getData(); 
                for   (int   j   =   i;   j   <   a.length;   j++)   { 
                        takeBoat(a[i],   a[j]); 
                } 
                if   (i++   <   a.length   -   1)   { 
                        topassriver2(); 
                } 
        }         public   static   void   main(String[]   args)   { 
                PassRiver   passRiver   =   new   PassRiver(); 
                passRiver.topassriver2();         }         /** 
          *   tabe   boat   to   pass   river 
          *   
          *   @param   a 
          *                         human   or   ghost 
          *   @param   b 
          *                         human   or   ghost 
          */ 
        public   static   void   takeBoat(String   a,   String   b)   {                 if   (map.get(a).equals(map.get(b)))   {                         if   (map.get(a).equals( "1 "))   { 
                                //   System.out.println(a   +   "   and   "   +   b   +   "   is   man "   +   " ");                         } 
                        if   (map.get(a).equals( "0 "))   { 
                                //   System.out.println(a   +   "   and   "   +   b   +   "   is   ghost ");                         } 
                }   else   { 
                        //   a   or   b   one   is   human   and   the   other   is   ghost 
                        System.out.println(a   +   "   and   "   +   b   +   "   is   can   take   boat "   +   " "); 
                }         }         public   static   String[]   getData()   { 
                String[]   a   =   new   String[6]; 
                int   k   =   0; 
                //   if   two   human   or   two   ghost   is   boat 
                Iterator   iterator   =   map.keySet().iterator();                 while   (iterator.hasNext())   { 
                        a[k]   =   (String)   iterator.next(); 
                        k++; 
                } 
                return   a; 
        }         /** 
          *   
          *   @return 
          */ 
        public   Map   toPass()   {                 return   null; 
        }         public   static   Map   getMap()   { 
                Map   map   =   new   HashMap(); 
                map.put( "a ",   "1 "); 
                map.put( "b ",   "1 "); 
                map.put( "c ",   "1 "); 
                map.put( "d ",   "0 "); 
                map.put( "e ",   "0 "); 
                map.put( "f ",   "0 "); 
                return   map; 
        } } 

Answer 11

游戏不难，难到我的是，怎么写程序找到这个方法
恕我愚钝：递归 
如何递归呢？
有三种过河方法，还有5种回来的方法(在人和鬼没有完全过河之前过，还要把船划回来啊)
我实在没有想出来..............
然后我又这样想了：用循环
每次循环，都尝试3种过法，在成功的过法里面 ，再尝试此过法下可能的回来方法（至少有一种回法是成功的），直到人和鬼都全部过河。
我写了代码在一定条件下可行，但存在一个问题就是"至少有一种回法是成功的"，也可能是多种，如果在回来方法的判断顺序上不同的话就会导致失败；
代码不规范各位见笑了：看看此方法是否真的可行？
package test;import java.util.ArrayList;
import java.util.List;public class Test {

private List<Integer> left = new ArrayList<Integer>();//左岸left.get(0)表示人的数量，左岸left.get(1)表示鬼的数量
private List<Integer> right = new ArrayList<Integer>();//右岸
/**
 * 初始化左右两岸人鬼数量，左岸人鬼各三人，需要安全过到右岸
 */
public Test(){
left.add(3);
left.add(3);
right.add(0);
right.add(0);
}

public void checkSend() {
while(true){
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
if(sendTwoPerson()){
//如果左岸人鬼都成功过河，结束循环
if(left.get(0)==0&&left.get(1)==0){
break;
}
if(backOneGhost()){
right.set(1,right.get(1)-1);
left.set(1,left.get(1)+1);
System.out.print("1鬼回来");
}else if(backTwoGhost()){
right.set(1,right.get(1)-2);
left.set(1,left.get(1)+2);
System.out.print("2鬼回来");
}else if(backOne()){
right.set(0,right.get(0)-1);
left.set(0,left.get(0)+1);
right.set(1,right.get(1)-1);
left.set(1,left.get(1)+1);
System.out.print("1人1鬼回来");
}else if(backOnePerson()){
right.set(0,right.get(0)-1);
left.set(0,left.get(0)+1);
System.out.print("1人回来");
}
}else if(sendTwoGhost()){
//如果左岸人鬼都成功过河，结束循环
if(left.get(0)==0&&left.get(1)==0){
break;
}
if(backOneGhost()){
right.set(1,right.get(1)-1);
left.set(1,left.get(1)+1);
System.out.print("1鬼回来");
}else if(backOne()){
right.set(0,right.get(0)-1);
left.set(0,left.get(0)+1);
right.set(1,right.get(1)-1);
left.set(1,left.get(1)+1);
System.out.print("1人1鬼回来");
}else if(backOnePerson()){
right.set(0,right.get(0)-1);
left.set(0,left.get(0)+1);
System.out.print("1人回来");
}
}else if(sendOne()){
//如果左岸人鬼都成功过河，结束循环
if(left.get(0)==0&&left.get(1)==0){
break;
}
if(backTwoGhost()){
right.set(1,right.get(1)-2);
left.set(1,left.get(1)+2);
System.out.print("2鬼回来");
}else if(backOnePerson()){
right.set(0,right.get(0)-1);
left.set(0,left.get(0)+1);
System.out.print("1人回来");
}
}
System.out.println("  左岸剩余-->>>" +left.get(0)+"人"+" "+left.get(1)+"鬼   ||  "+"  右岸共-->>>" +right.get(0)+"人"+" "+right.get(1)+"鬼");
}
System.out.println("   左岸-->>>" +left.get(0)+"人"+" "+left.get(1)+"鬼  ||  "+"  右岸共-->>>" +right.get(0)+"人"+" "+right.get(1)+"鬼       "+"成功过河");
}
/**
 * 2人过河
 * @return 是否成功
 */
public boolean sendTwoPerson() {
if(left.get(0)-2<0){//左岸人数不足2，送法失败
return false;
}else if(left.get(0)-2!=0 && left.get(0)-2 < left.get(1)){//左岸人数大于0且送走2人后小于鬼数目时送法失败
return false;
}else if(right.get(0)+2 < right.get(1)){//右岸送过2人后人数小于鬼数送法失败
return false;
}else{//否则送法成功，并更新两岸人鬼数目
left.set(0, left.get(0)-2);
right.set(0, right.get(0)+2);
System.out.print("2人过河");
return true;
}
}
/**
 * 2鬼过河
 * @return 是否成功
 */
public boolean sendTwoGhost() {
if(left.get(1)-2<0){//左岸鬼数不足2，送法失败
return false;
}else if(left.get(0)!=0 && left.get(0) < left.get(1)-2){//左岸人数大于0且送走2鬼后小于鬼数目时送法失败
return false;
}else if(right.get(0) != 0&&right.get(0) < right.get(1)+2){//右岸人数大于0且小于送来两鬼后鬼的数量送法失败
return false;
}else{//否则送法成功，并更新两岸人鬼数目
left.set(1, left.get(1)-2);
right.set(1, right.get(1)+2);
System.out.print("2鬼过河");
return true;
}
}
/**
 * 一人一鬼过河
 * @return 是否成功
 */
public boolean sendOne() {
if(left.get(0)-1<0 || left.get(1)-1<0){//左岸鬼数不足1，送法失败
return false;
}else if(left.get(0)-1 != 0 && left.get(0)-1 < left.get(1)-1){//左岸送走1人后书目不为0且人数少于送走1鬼后的鬼数，送法失败
return false;
}else if(right.get(0)+1 < right.get(1)+1){//右岸送来1人和1鬼后，人数少于鬼数送法失败
return false;
}else{//否则送法成功，并更新两岸人鬼数目
left.set(0, left.get(0)-1);
right.set(0, right.get(0)+1);
left.set(1, left.get(1)-1);
right.set(1, right.get(1)+1);
System.out.print("一人一鬼过河");
return true;
}
}
/**
 * 回来1人
 * @return 是否成功
 */
public boolean backOnePerson() {
if(right.get(0)-1<0){
return false;
}else if(right.get(0)-1==0 && right.get(1)==0){
return false;
}else if(right.get(0)-1 != 0 && right.get(0)-1 < right.get(1)){
return false;
}else if(left.get(0)+1 < left.get(1)){
return false;
}else{
return true;
}
}
/**
 * 回来1鬼
 * @return 是否成功
 */
public boolean backOneGhost() {
if(right.get(1)-1<0){
return false;
}else if(right.get(0)==0 && right.get(1)-1==0){
return false;
}else if(right.get(0)!=0 && right.get(0) < right.get(1)-1){
return false;
}else if(left.get(0)!=0 && left.get(0) < left.get(1)+1){
return false;
}else{
return true;
}
}
/**
 * 回来2人
 * @return 是否成功
 */
public boolean backTwoPerson() {
if(right.get(0)-2<0){
return false;
}else if(right.get(0)-2==0 && right.get(1)==0){
return false;
}else if(right.get(0)-2 < right.get(1)){
return false;
}else if(left.get(0)+2 < left.get(1)){
return false;
}else{
return true;
}
}
/**
 * 回来2鬼
 * @return 是否成功
 */
public boolean backTwoGhost() {
if(right.get(1)-2<0){
return false;
}else if(right.get(0)==0 && right.get(1)-2==0){
return false;
}else if(right.get(0)!=0 && right.get(0) < right.get(1)-2){
return false;
}else if(left.get(0)!=0&&left.get(0) < left.get(1)+2){
return false;
}else{
return true;
}
}
/**
 * 回来1人1鬼
 * @return 是否成功
 */
public boolean backOne() {
if(right.get(1)-1<0 || right.get(0)-1<0){
return false;
}else if(right.get(0)-1==0 && right.get(1)-1==0){
return false;
}else if(right.get(0)-1 < right.get(1)-1){
return false;
}else if(left.get(0)+1 < left.get(1)+1){
return false;
}else{
return true;
}
} public static void main(String[] args){
Test t = new Test();
t.checkSend();
}
}

Answer 12

Sharpen your code-java高级群：78455879欢迎您的加入...

Answer 13

这个农夫过河是偶写的 你可以参考下 写的有点多 你自己优化下吧 之前还不知道农夫过河是啥意思 不过后来知道了 
应该没问题的
import java.util.Iterator; 
import java.util.LinkedList; public class AcrossTheRiver { 
// 定义三个String对象 
public static final String rabbitName = "Rabbit"; 
public static final String wolfName = "Wolf"; 
public static final String cabbageName = "Cabbage"; // 判断两个货物之间关系是否友好 写的麻烦了一点= =.. 
public static boolean isFriendly(Goods goods1, Goods goods2) { 
if (goods1 != null) { 
if (goods1.getGoodsName().trim().equals(rabbitName)) { 
if (goods2 == null) { 
return true; 
} else { 
return false; 
} 
} else if (goods1.getGoodsName().trim().equals(wolfName)) { 
if (goods2 == null || goods2.getGoodsName().trim().equals(cabbageName)) { 
return true; 
} else { 
return false; 
} 
} else if (goods1.getGoodsName().trim().equals(cabbageName)) { 
if (goods2 == null || goods2.getGoodsName().trim().equals(wolfName)) { 
return true; 
} else { 
return false; 
} 
} else { 
return false; 
} 
} else { 
return true; 
} 
} // 我就直接写在主方法里了 
public static void main(String[] args) { 
boolean isSuccess = false; 
LinkedList<Goods> beforeCrossing = new LinkedList<Goods>(); 
LinkedList<Goods> afterCrossing = new LinkedList<Goods>(); 
beforeCrossing.add(new Goods(rabbitName)); 
beforeCrossing.add(new Goods(cabbageName)); 
beforeCrossing.add(new Goods(wolfName)); 
while (!isSuccess) { 
Goods goods1 = beforeCrossing.getFirst(); 
System.out.println(goods1.getGoodsName() + " 被取走了"); 
beforeCrossing.removeFirst(); 
if (beforeCrossing.isEmpty()) { 
afterCrossing.addLast(goods1); 
isSuccess = true; 
System.out.println("全部移动完毕！"); 
} else { 
Iterator<Goods> it = beforeCrossing.iterator(); 
Goods[] beforeCro = new Goods[2]; 
for (int i = 0; it.hasNext(); i++) { 
beforeCro[i] = it.next(); 
System.out.println(beforeCro[i].getGoodsName() + " 留了下来"); 
} 
if (isFriendly(beforeCro[0], beforeCro[1])) { 
if (afterCrossing.isEmpty()) { 
afterCrossing.addLast(goods1); 
System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸"); 
} else { 
Goods goods2 = afterCrossing.getFirst(); 
if (isFriendly(goods1, goods2)) { 
afterCrossing.addLast(goods1); 
System.out.println(goods1.getGoodsName() + " 被成功的放到了对岸"); 
} else { 
beforeCrossing.addLast(goods2); 
afterCrossing.removeFirst(); 
System.out.println(goods1.getGoodsName() + " 与 " 
+ goods2.getGoodsName() + "并不和睦 于是把 " + goods2.getGoodsName() 
+ "带了回来 并将 " + goods1.getGoodsName() + " 留了下来"); 
} 
} 
} else { 
beforeCrossing.addLast(goods1); 
System.out.println("很可惜 留下来的两个东西并不和睦 于是 " + goods1.getGoodsName() 
+ " 又被放了回去"); 
} 
} 
} 
} 
} // 货物类 
class Goods { 
// 货物名称 
private String goodsName; // 默认构造方法 
public Goods(String goodsName) { 
this.goodsName = goodsName; 
} // 获得货物名称 
public String getGoodsName() { 
return goodsName; 
} } 

Answer 14

上面的那个算法不错，不过可以有一点小改进：
  for   (int   j   =   i+1;   j   <   a.length;   j++)   

Answer 15

广度优先搜索定义状态 [(i,j),(k,l)] 表示在河对岸及船上的 人和鬼 的个数每次根据要求进行状态转移就好了 就算有10人10鬼 状态数量也不过10000个而已 况且很多状态是无法达到的