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

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

------解决方案--------------------
其实不是树，用递归，遍历所有可能性。

每层递归都依次尝试三种过发，如果发现某种方法过去后导致失败，则返回递归。
------解决方案--------------------

Java code



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 xt(lin

------解决方案--------------------


 我的思路和想法是这样的啊 
 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(); 
         }

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

相关推荐