编程题：java实现4人在17分钟内过桥

65 阅读 0 评论 43 点赞

我是靠谱客的博主虚心星星，最近开发中收集的这篇文章主要介绍编程题：java实现4人在17分钟内过桥，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

怎么让这4个人在17分钟内要过桥
有4个人要过一座桥.她们都站在桥的某一边,要让她们在17分钟内全部通过这座桥.这时是晚上.她们只有一个手电筒.最多只能让两个人同时过桥.不管是谁过桥,不管是一个人还是两个人,必须要带着手电筒.手电筒必须要传来传去,不能扔过去.每个人过桥的速度不同,两个人的速度必须以较慢的那个人的速度过桥.
　　第一个人：过桥需要1分钟；
　　第二个人：过桥需要2分钟；
　　第三个人：过桥需要5分钟；
　　第四个人：过桥需要10分钟.
　　比如,如果第一个人与第4个人首先过桥,等她们过去时,已经过去了10分钟.如果让第4个人将手电筒送回去,那么等她到达桥的另一端时,总共用去了20分钟,行动也就失败了.怎样让这4个人在17分钟内过桥?还有别的什么方法?

代码：

package parking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 过桥事件
 * 
 * @author ASUS
 *
 */
public class CrossBridge {

	private static final String COMMA = ",";
	// 过桥规定时间不得多于17分钟
	private static final int SCHEDULT_TIME = 17;
	private static final String LEFT_SYMBOL = "{";
	private static final String RIGHT_SYMBOL = "}";
	private static final String GO_WORD = "过桥去了";
	private static final String BACK_WORD = "我又返回了";
	private static final String LEFT_ALLOW = "--->";
	private static final String RIGHT_ALLOW = "<---";
	private static final String NEW_LINE = "n";

	private static int count = 1;

	private static Map<String, Integer> map = new HashMap<>();

	static {
		map.put("A", 1);
		map.put("B", 2);
		map.put("C", 5);
		map.put("D", 10);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<String> list = new ArrayList<>();
		list.add("A");
		list.add("B");
		list.add("C");
		list.add("D");
		StringBuffer sb = new StringBuffer();
		int initTime = 0;
		new CrossBridge().resultCross(list, new ArrayList<String>(), initTime, sb);
	}

	/**
	 * 处理过桥事件
	 * 
	 * @param listNot
	 *            未过桥人员列表
	 * @param ListOver
	 *            已过桥人员列表
	 * @param initTime
	 *            花费的时间
	 * @param sb
	 *            记录步骤过程
	 */
	private void resultCross(List<String> listNot, List<String> ListOver, int initTime, StringBuffer sb) {

		// 获取未过桥的所有两两组合的可能组合
		List<String> result = getAllResult(listNot);

		for (String groupPeople : result) {
			// 因为列表数据是【a,b a,c a,d】这种格式
			String[] peoples = groupPeople.split(COMMA);
			//表示未过桥的人员列表
			List<String> current = new ArrayList<>(listNot);
			//表示已过桥的人员列表
			List<String> over = new ArrayList<>(ListOver);
			int currentTime = initTime;
			StringBuffer currentBuffer = sb;
			// 过桥后人数变动
			for (String people : peoples) {
				// 未过桥列表减去过桥人员
				current.remove(people);
				// 已过桥列表增加过桥人员
				over.add(people);
			}

			currentTime += getMaxTime(peoples);
			// 记录一条步骤--》{a,b}--->过桥去了
			currentBuffer.append(current).append(LEFT_ALLOW).append(LEFT_SYMBOL).append(groupPeople).append(RIGHT_SYMBOL).append(GO_WORD).append(LEFT_ALLOW).append(over).append(NEW_LINE);
			// 人员全部过完情况
			if (current.isEmpty()) {

				if (currentTime <= SCHEDULT_TIME) {
					System.out.println("第" + count + "种情况:");
					System.out.println("花费时间--》" + currentTime);
					System.out.println("步骤详情--》");
					System.out.println(currentBuffer.toString());
					count++;
				}
			} else {
				// 没有全部过桥情况，得从过桥列表中返回一个人
				for (String peopleToBack : over) {
					//表示已过桥的人员列表
					List<String> overGroup = new ArrayList<>(over);
					//表示未过桥的人员列表
					List<String> waitGroup = new ArrayList<>(current);
					int nowTime = currentTime;
					StringBuffer nowBuffer = new StringBuffer(currentBuffer.toString());
					// 已过桥列表删除返回的人员
					overGroup.remove(peopleToBack);
					// 未过桥列表增加返回的人员
					waitGroup.add(peopleToBack);
					// 加上返回时间
					nowTime += map.get(peopleToBack);

					// 返回的步骤
					nowBuffer.append(waitGroup).append(RIGHT_ALLOW).append(LEFT_SYMBOL).append(peopleToBack).append(RIGHT_SYMBOL).append(BACK_WORD)
					.append(RIGHT_ALLOW).append(overGroup).append(NEW_LINE);
					// 递归，重新重复以上步骤
					resultCross(waitGroup, overGroup, nowTime, nowBuffer);
				}

			}

		}

	}

	/**
	 * 返回时间最多的那个
	 * @param peoples
	 * @return
	 */
	private int getMaxTime(String[] peoples) {
		// peoples[a，b],根据key找到存在map里面对应的时间，比较2者大小，返回最大时间
		return Math.max(map.get(peoples[0]), map.get(peoples[1]));
	}

	/**
	 * 获取未过桥的所有两两组合的可能组合
	 * 
	 * @param listNot
	 *            未过桥人员列表
	 * @return
	 */
	private List<String> getAllResult(List<String> listNot) {
		// 把列表类型转换成字符串数组
		int len = listNot.size();
		String[] str = new String[len];
		listNot.toArray(str);
		int i, j;
		List<String> result = new ArrayList<>();
		for (i = 0; i < len - 1; i++) {
			for (j = 0; j < len; j++) {
				// 如果组合是【a,a】或者result已经存在组合【a,b】还是【b,a】的情况就不往列表里加数据,其他组合加进列表。
				if (!str[i].equals(str[j]) && !result.contains(str[i] + COMMA + str[j])
						&& !result.contains(str[j] + COMMA + str[i])) {
					result.add(str[i] + COMMA + str[j]);
				}
			}
		}
		// 组合格式：[A,B , A,C , A,D , B,C , B,D , C,D]
		return result;
	}

}

效果：

第1种情况:
花费时间--》17
步骤详情--》
[C, D]--->{A,B}过桥去了--->[A, B]
[C, D, A]<---{A}我又返回了<---[B]
[A]--->{C,D}过桥去了--->[B, C, D]
[A, B]<---{B}我又返回了<---[C, D]
[]--->{A,B}过桥去了--->[C, D, A, B]

第2种情况:
花费时间--》17
步骤详情--》
[C, D]--->{A,B}过桥去了--->[A, B]
[C, D, B]<---{B}我又返回了<---[A]
[B]--->{C,D}过桥去了--->[A, C, D]
[B, A]<---{A}我又返回了<---[C, D]
[]--->{B,A}过桥去了--->[C, D, B, A]