java 有关人鬼过河的一个问题
3人3鬼在一条河岸的一边，都要到河的另一边去，河边停靠有一条船，最多可以载一人一鬼，或2鬼，或2人，不论何时不管河岸的那一边只要鬼的数量超过人的数量，鬼都会吃掉人导致过河失败：用java 找出过河的方法，网上有人说用树，可想了很久不知道怎么建这棵树啊........只怪算法和数据结构学得太烂....
那位高人能给点提示呢-----不胜感激啊
[解决办法]
其实不是树，用递归，遍历所有可能性。
每层递归都依次尝试三种过发，如果发现某种方法过去后导致失败，则返回递归。
[解决办法]
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();
}
}
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;
}
}
[解决办法]
我的思路和想法是这样的啊
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;
}
}