4.7 蚂蚁爬杆问题

本文主要是介绍4.7 蚂蚁爬杆问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 前言

本文的一些图片, 资料截取自编程之美

2. 问题描述

这里写图片描述

3. 问题分析

根据问题, 绘制一张状态图 :
这里写图片描述

解法一 : 模拟每一只蚂蚁的运动, 并以 各个蚂蚁的单位移动量需要的时间的最小公倍数 为周期检测所有的蚂蚁的情况, 检测碰撞, 统计每一只蚂蚁离开竹竿的时间, 最后的结果中找出最大, 最小值即为所求

解法二 : 将两只蚂蚁的碰撞假想为两只蚂蚁的擦肩而过
这里写图片描述

那么, 这样一看起来, 所有的蚂蚁就”互不影响”了, 求出蚂蚁离开竹竿的最长, 最短时间, 就可以遍历一次蚂蚁, 获取他们离开的时间, 然后获取最大值, 最小值即可

这里我的思路是找出最左边的向右的蚂蚁和最右边的向左的蚂蚁, 然后找出二者的爬出竹竿的时间的较大者即为蚂蚁爬出竹竿的最长的时间, 爬出竹竿的最小时间类似

后来, 闲来无事的时候, 思考了一下后面的部分思考题
问题1. 试问每只蚂蚁爬出竹竿需要的时间分别是多少
问题2. 整个流程中, 所有的蚂蚁共碰撞了多少次

对于问题一 : 思路是来自这篇播客(或者转载这里, 具体的我也忘了) : http://lam8da.sinaapp.com/?p=11
所以, 我在Ant类中, 添加了一个dstId 用来表示在当前时间点之前, 碰撞的上一个蚂蚁的id, 出杆的时候, dstId对应的蚂蚁无障碍出杆需要的时间, 即为当前蚂蚁出杆需要的时间

这里, 我模拟运动过程的思路是 : 先移除竹竿最左边的向左走的蚂蚁(们), 向右边的向右走的蚂蚁(们) [之后最左边的蚂蚁必然向右, 最右边的蚂蚁必然向左] , 然后在从左到右校验碰撞, 更新蚂蚁的dstId, 以及其方向
流程图如下 :
这里写图片描述

对于问题二 : 从左开始找出遍历所有的向右的蚂蚁右边的向左的蚂蚁的个数的和即为整个流程的碰撞个数

如下图 : 向右的蚂蚁有3, 11; 3号右边有7, 17, 23三只蚂蚁, 11右边有17, 23两只蚂蚁, 所以整个碰撞的过程中, 碰撞的次数为 3 + 2 = 5 次
这里写图片描述

4. 代码

/*** file name : Test14AntCollition.java* created at : 3:09:41 PM May 30, 2015* created by 970655147*/package com.hx.test04;public class Test14AntCollition {// 蚂蚁爬杆问题// 4.7节讲的是一根长27cm的木棍上，在5个点上有5只蚂蚁，蚂蚁在开始的时候朝任意方向出发，只能掉头或者往前走。// 让任意两只蚂蚁碰头时，它们同时掉头朝反方向走。假设蚂蚁的速度都是一秒一厘米，求蚂蚁都离开木棍的最短时间和最长时间。// 1. 找出所有蚂蚁离开需要的时间// 2. 找出整个流程中碰撞的次数// 3. 找出每一个蚂蚁离开竹竿需要的时间public static void main(String []args ) {int bambooLength = 27;Ant[] ants = new Ant[5];int[] poses = new int[] {3, 7, 11, 17, 23 };boolean[] isRights = new boolean[] {true, false, true, false, false };for(int i=0; i<ants.length; i++) {ants[i] = new Ant(i, poses[i], isRights[i]);}Arrays.sort(ants);Log.log(ants);Bamboo bamboo = new Bamboo(ants, bambooLength);bamboo.findAllClearSpent();bamboo.collisionCount();bamboo.getSpentTimeFor(4);Log.log(bamboo.reallySpendTime );}// 竹竿static class Bamboo {// 蚂蚁(们)[蚂蚁的位置 是经过排序的], 竹竿的长度, 每一只蚂蚁出杆需要的时间[假设杆上只有一只蚂蚁]Ant[] ants;int length;int[] spendTime;int[] reallySpendTime;// 初始化public Bamboo() {}// 排序 确保ants有序public Bamboo(Ant[] ants, int length) {this.ants = ants;this.length = length;spendTime = new int[ants.length];calcSpendTime();}// 找出所有蚂蚁离开的时间// 思路 : 从左边找到第一个向右走的蚂蚁, 从右边找到第一个想左走的蚂蚁// 然后 取这两只蚂蚁花费的时间的较大者public void findAllClearSpent() {int left = 0, right = ants.length - 1;for(left=0; left<ants.length; left++) {if(ants[left].isRight ) {break;}}for(right=ants.length-1; right>=0; right--) {if(!ants[right].isRight ) {break;}}int leftSpent = -1, rightSpent = -1;if(left < ants.length) {leftSpent = length - ants[left].pos / ants[left].speed;}if(right >= 0) {rightSpent = ants[right].pos / ants[right].speed;}Log.log(max(leftSpent, rightSpent) );}// 统计所有蚂蚁的碰撞次数// 思路 : 从右开始遍历ants  每一个向左的ant  会与其左边的向右的所有ant碰一次 // 从而累加得到碰撞次数public void collisionCount() {int cnt = 0;for(int i=ants.length-1; i>=0; i--) {if(!ants[i].isRight ) {for(int j=i-1; j>=0; j--) {if(ants[j].isRight) {cnt ++;}}}}Log.log("collision count : " + cnt);}// 获取指定索引的蚂蚁的出去的时间public void getSpentTimeFor(int idx) {if(reallySpendTime == null) {scanForProcedure();}Log.log(reallySpendTime[idx] );}// 扫描所有的碰撞[一次一次的扫描]// 不断的碰撞 直到所有的蚂蚁都出去了// 先清理头尾可以直接出去的蚂蚁 [左边的向左的, 右边的向右的]// 校验剩余蚂蚁的碰撞   只校验当前情况下课碰撞的蚂蚁  如果发生碰撞更新两只蚂蚁的dstId[交换]  更新方向 // 进入下一个循环迭代// 比如   true false true false false  只校验(0, 1)和 (2, 3)// ants 中存放的是this.ants的副本[确保有序]// output 存放出去的蚂蚁的序列private void scanForProcedure() {Deque<Ant> ants = new LinkedList<Ant>();for(int i=0; i<this.ants.length; i++) {ants.add(new Ant(this.ants[i]) );}List<Ant> output = new ArrayList<Ant>(this.ants.length);// 清理头尾的可以直接出去的蚂蚁bigLoop :while(ants.size() > 0) {while(!ants.getFirst().isRight ) {output.add(ants.removeFirst() );if(ants.size() == 0) {break bigLoop;}}while(ants.getLast().isRight) {output.add(ants.removeLast() );if(ants.size() == 0) {break bigLoop;}}// 校验碰撞Iterator<Ant> it = ants.iterator();Ant last = null;while(it.hasNext() ) {Ant ant = it.next();if(last != null) {if((! ant.isRight) && last.isRight) {collision(last, ant);last = null;continue ;}}last = ant;}}// 设置reallySpendTimereallySpendTime = new int[this.ants.length];for(int i=0; i<this.ants.length; i++) {reallySpendTime[output.get(i).srcId] = spendTime[output.get(i).dstId];}}// 如果发生了碰撞  更新src, dst的dstId[交换], 并更新src, dst的方向private void collision(Ant src, Ant dst) {int tmp = src.dstId;src.dstId = dst.dstId;dst.dstId = tmp;src.isRight = !src.isRight;dst.isRight = !dst.isRight;}// 计算每一只蚂蚁出杆的时间[假设杆上只有一只蚂蚁]private void calcSpendTime() {for(int i=0; i<ants.length; i++) {if(ants[i].isRight ) {spendTime[i] = (length - ants[i].pos) / ants[i].speed;} else {spendTime[i] = ants[i].pos / ants[i].speed;}}}// 获取x, y之间的较大者private static int max(int x, int y) {return x > y ? x : y;}}// 蚂蚁static class Ant implements Comparable {// 蚂蚁的id, dstId表示与其相碰的蚂蚁的id// 位置, 方向是否向右, 速度int srcId;int dstId;int pos;boolean isRight;int speed;// 初始化public Ant() {speed = 1;}public Ant(Ant dst) {this(dst.srcId, dst.pos, dst.isRight);}public Ant(int srcId, int pos, boolean isRight) {this();this.srcId = srcId;this.dstId = srcId;this.pos = pos;this.isRight = isRight;}// compareTo 用于Arrays.sort() 来排序// 这里以pos为基准  谁的pos大  谁就大public int compareTo(Object o) {if(!(o instanceof Ant) ) {return -1;}Ant ant = (Ant) o;return pos - ant.pos;}// Debugpublic String toString() {return "srcId : " + srcId + ", dstId : " + dstId +  ", pos : " + pos + ", isRight : " + isRight;}}}