最短时间过桥_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 最短时间过桥

最短时间过桥

 2014/4/22 0:18:37  MouseLearnJava  程序员俱乐部  我要评论(0)
  • 摘要:本文用代码实现最短时间过桥,并且打印如下两个例子的最小过桥时间:例子一:四人夜间过桥,他们只有一个手电筒一次只能两个人过桥,过桥时必须有手电筒,四人过桥时间为1分2分6分10分例子二:小明过桥要一秒,小明的弟弟要三秒,小明的爸爸要六秒,小明的妈妈要八秒,小明的爷爷要十二秒。每次此桥最多可过两人,而过桥的速度,依过桥最慢者而定,可是灯在点燃后,三十秒就会熄灭(过桥需要灯照明)。那么,请问小明一家,如何在三十秒内过桥?代码:importjava.util.ArrayList;importjava
  • 标签:
本文用代码实现最短时间过桥,并且打印如下两个例子的最小过桥时间:

例子一:
四人夜间过桥,他们只有一个手电筒一次只能两个人过桥,过桥时必须有手电筒,四人过桥时间为1分2分6分10分

例子二:小明过桥要一秒,小明的弟弟要三秒,小明的爸爸要六秒,小明的妈妈要八秒,小明的爷爷要十二秒。每次此桥最多可过两人,而过桥的速度,依过桥最慢者而定,可是灯在点燃后, 三十秒就会熄灭(过桥需要灯照明)。那么,请问小明一家,如何在三十秒内过桥?

代码:

class="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Eric
 */

public class CrossBridge {

	/**
	 * @param personSpeeds
	 *            每个人过桥所需时间的一个列表
	 */
	public void crossBridge(List<Integer> personSpeeds) {
		if (null == personSpeeds || 0 == personSpeeds.size()) {
			throw new IllegalArgumentException("至少有一个人需要过桥,请保证参数至少有一个元素。");
		} else if (!isSpeedParameterLeagal(personSpeeds)) {
			throw new IllegalArgumentException("请纠正过桥时间,每个人的过桥时间不能小于等于零。");
		} else if (1 == personSpeeds.size()) {
			// 只有一个人过桥,那么直接输出过桥过桥时间
			System.out.printf("%d -> Go \n", personSpeeds.get(0));
			System.out.printf("最少过桥耗时 %s 秒!\n", personSpeeds.get(0));
		} else if (2 == personSpeeds.size()) {
			// 只有两个人过桥,那么直接输出过桥过桥时间
			System.out.printf("%d %d -> Go \n", personSpeeds.get(0),
					personSpeeds.get(1));
			System.out.printf("最少过桥耗时 %d 秒!\n", personSpeeds.get(0)
					+ personSpeeds.get(0));
		} else {
			// 处理多个人过桥的场景

			// 为了获取过桥时间的最大最小值,首先对personSpeeds排序
			Collections.sort(personSpeeds);

			doBridgeCross(personSpeeds);
		}

	}

	private void doBridgeCross(List<Integer> personSpeeds) {
		List<Integer> source = new ArrayList<Integer>();
		source.addAll(personSpeeds);
		List<Integer> destination = new ArrayList<Integer>();
		int totalCrossBridgeTime = 0;
		boolean secondFastestOnDest = false;

		while (!source.isEmpty()) {
			int srcFastest = source.get(0);
			int srcSecondFastest = source.get(1);

			if (2 == source.size()) {
				totalCrossBridgeTime += populateBridgeCrossingTime(source,
						destination, srcFastest, srcSecondFastest, false);
			} else {
				// 处理多余两个人过桥的情况

				if (secondFastestOnDest) {
					// 计算出最慢的两个
					int srcSlowest = source.get(source.size() - 1);
					int srcSecondSlowest = source.get(source.size() - 2);
					if (destination.get(0) * 2 < srcFastest + srcSecondSlowest) {
						secondFastestOnDest = false;
						totalCrossBridgeTime += populateBridgeCrossingTime(
								source, destination, srcSecondSlowest,
								srcSlowest, true);
					} else {
						totalCrossBridgeTime += populateBridgeCrossingTime(
								source, destination, srcFastest, srcSlowest,
								true);
					}
				} else {
					// 最快的两个人过去
					secondFastestOnDest = true;
					totalCrossBridgeTime += populateBridgeCrossingTime(source,
							destination, srcFastest, srcSecondFastest, true);
				}

			}
		}

		// 输出花费的时间
		System.out.printf("最少过桥耗时 %d 秒!\n", totalCrossBridgeTime);
	}

	/**
	 * 计算过桥的时间,如果需要拿灯回来,则需要将回来的时间也算上。
	 */
	private int populateBridgeCrossingTime(List<Integer> source,
			List<Integer> destination, int fastOne, int slowOne,
			boolean needReturnLight) {
		int sp1 = source.remove(source.indexOf(fastOne));
		int sp2 = source.remove(source.indexOf(slowOne));
		destination.add(sp1);
		destination.add(sp2);
		System.out.printf("%d %d --> Go \n", sp1, sp2);
		// 耗时多的那个
		int elapsedTime = sp2;

		if (needReturnLight) {
			Collections.sort(destination);
			// 拿灯返回
			sp1 = destination.remove(0);
			source.add(sp1);
			Collections.sort(source);
			elapsedTime += sp1;
			// sb.append(sp1).append("\n");
			System.out.printf("%d <-- Back \n", sp1);
		}

		return elapsedTime;
	}

	/**
	 * 保证每个人过桥的时间都大于0
	 */

	private boolean isSpeedParameterLeagal(List<Integer> personSpeeds) {
		/*
		 * 每个人的过桥时间都必须大于0
		 */
		for (int i : personSpeeds) {
			if (i <= 0) {
				return false;
			}
		}
		return true;
	}
}




测试代码
import java.util.Arrays;
import java.util.List;

public class CrossBridgeText {

	public static void main(String[] args) {
		CrossBridge cb = new CrossBridge();
		System.out
				.println("Example 1 -> \n四人夜间过桥,他们只有一个手电筒一次只能两个人过桥,过桥时必须有手电筒,四人过桥时间为1分2分6分10分\n");
		List<Integer> personSpeeds1 = Arrays.asList(1, 2, 6, 10);
		cb.crossBridge(personSpeeds1);
		System.out
				.println("\nExample 2 -> \n小明过桥要一秒,小明的弟弟要三秒,小明的爸爸要六秒,小明的妈妈要八秒,小明的爷爷要十二秒。\n每次此桥最多可过两人,而过桥的速度,依过桥最慢者而定,可是灯在点燃后, 三十秒就会熄灭。\n 那么,请问小明一家,如何在三十秒内过桥?");
		List<Integer> personSpeeds2 = Arrays.asList(1, 3, 6, 8, 12);
		cb.crossBridge(personSpeeds2);
	}

}



测试结果输出:


Example 1 ->
四人夜间过桥,他们只有一个手电筒一次只能两个人过桥,过桥时必须有手电筒,四人过桥时间为1分2分6分10分

1 2 -->
1 <-- Back
6 10 -->
2 <-- Back
1 2 -->
最少过桥耗时 17 秒!

Example 2 ->
小明过桥要一秒,小明的弟弟要三秒,小明的爸爸要六秒,小明的妈妈要八秒,小明的爷爷要十二秒。
每次此桥最多可过两人,而过桥的速度,依过桥最慢者而定,可是灯在点燃后, 三十秒就会熄灭。
那么,请问小明一家,如何在三十秒内过桥?
1 3 -->
1 <-- Back
8 12 -->
3 <-- Back
1 3 -->
1 <-- Back
1 6 -->
最少过桥耗时 29 秒!

转载请注明:http://mouselearnjava.iteye.com/blog/2051541
上一篇: ajax 下一篇: JavaSE_89_文件操作初步
  • 相关文章
发表评论
用户名: 匿名