百度面试题---5只蚂蚁走木棍问题的递归解法(java实现)

题目描述：
    有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，不能同时通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。编写程序，求所有蚂蚁都离开木杆的最小时间和最大时间。

    在网上无意间看到这个小问题，觉得挺有趣的，自己分析后给出了递归方法来处理它

算法思想、步骤都在code的注释里有所解释

package com.leochan;

import java.util.LinkedList;

public class RecursionAntWalker {

	public static int spendTime = 0;

	public static int totalLength = 27;

	public static void main(String[] args) {

		recursionTest();

	}

	// 递归计算32种不同情况下所需要的时间。
	private static void recursionTest() {
		int count = 0;
		for (int d1 = -1; d1 <= 1; d1 += 2) {
			for (int d2 = -1; d2 <= 1; d2 += 2) {
				for (int d3 = -1; d3 <= 1; d3 += 2) {
					for (int d4 = -1; d4 <= 1; d4 += 2) {
						for (int d5 = -1; d5 <= 1; d5 += 2) {
							count++;
							spendTime = 0;
							Ant a = new Ant(3);
							Ant b = new Ant(7);
							Ant c = new Ant(11);
							Ant d = new Ant(17);
							Ant e = new Ant(23);
							a.direction = d1;
							b.direction = d2;
							c.direction = d3;
							d.direction = d4;
							e.direction = d5;

							LinkedList<Ant> testCase = new LinkedList<Ant>();

							testCase.add(a);
							testCase.add(b);
							testCase.add(c);
							testCase.add(d);
							testCase.add(e);

							System.out.print("count=" + count + " d1=" + d1
									+ " d2=" + d2 + " d3=" + d3 + " d4=" + d4
									+ " d5=" + d5);
							System.out
									.println("  getTime=" + getTime(testCase));
						}
					}
				}
			}
		}
	}

	// 递归计算每种组合需要的时间
	public static int getTime(LinkedList<Ant> antList) {

		int len = antList.size();

		// 如果antList里没有蚂蚁，直接返回spendTime
		if (len == 0)
			return spendTime;

		// 如果antList里只有1只蚂蚁，让这种蚂蚁一直走下去，直到它达到边界。
		// 在spendTime和这只蚂蚁所走过的distance中取最大值做为最终花费的时间
		if (len == 1) {
			Ant onlyAnt = antList.getFirst();
			onlyAnt.keepWalking();
			return (spendTime > onlyAnt.distance) ? spendTime
					: onlyAnt.distance;
		}

		// 如果antList里的第一只蚂蚁的运动方向为负方向，即-1，
		// 就重新计算spendTime,并且将这只蚂蚁移出list,递归去getTime
		if (!antList.getFirst().positiveDirect()) {
			Ant currentAnt = antList.removeFirst();
			spendTime = (currentAnt.position > spendTime) ? currentAnt.position
					+ currentAnt.distance : spendTime;
		}

		// 如果antList里最后一只蚂蚁的方向为正方向，即1
		// 就重新计算spendTime,并且将这只蚂蚁移出list,递归去getTime
		else if (antList.getLast().positiveDirect()) {
			Ant currentAnt = antList.removeLast();
			int needToGo = totalLength - currentAnt.position;
			spendTime = (needToGo > spendTime) ? needToGo + currentAnt.distance
					: spendTime;
		}

		// 其他情况下，让所有的蚂蚁按方向走一步，并判断有没有2只蚂蚁的位置重合，
		// 如果有重合，就让对应的2只蚂蚁转向。
		else {
			for (int i = 0; i < len; i++) {
				antList.get(i).walking();
				if (!antList.get(i).positiveDirect()) {
					if (antList.get(i).checkPosition(antList.get(i - 1))) {
						antList.get(i).changedirect();
						antList.get(i - 1).changedirect();
					}
				}
			}
		}

		return getTime(antList);
	}
}

// 蚂蚁类
class Ant {

	public int distance = 0; // 走过的距离，数值上等于时间
	public int position; // 当前的位置，在0-27之间

	public int direction = -1; // 运动的方向，-1表示向左，1表示向右

	public Ant(int position) {
		this.position = position;
	}

	// 用来判断运动方向是否为正方向
	public boolean positiveDirect() {
		return direction > 0;
	}

	// 如果位置在0-27之间，让蚂蚁一直行走
	public void keepWalking() {
		while (this.position > 0
				&& this.position < RecursionAntWalker.totalLength)
			this.walking();
	}

	// 检查2只蚂蚁的位置是否相同
	public boolean checkPosition(Ant ant) {
		return this.position == ant.position;
	}

	// 让当前的蚂蚁转向
	public void changedirect() {
		direction = -direction;
	}

	// 让蚂蚁按照自己的方向走1步，即经历单位时间1.
	public void walking() {
		distance += 1;
		position += direction;
	}
}

评论

2 楼 leochan007 2009-07-04  

fehly 写道

精品值得学习学习

额。。。。纯属瞎写着玩 。。。。shy

1 楼 fehly 2009-07-04  

精品值得学习学习