浏览 2732 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-06-27
有一根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; } } 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2009-07-04
精品值得学习学习
|
|
返回顶楼 | |
发表时间:2009-07-04
fehly 写道 精品值得学习学习 额。。。。纯属瞎写着玩 。。。。shy |
|
返回顶楼 | |