似乎是某公司面试题~~偶用穷举法实现了一下~~但是这个肯定考的不是穷举法,应该有优化的多的算法~有兴趣且有时间的朋友可以做着玩玩~~
PS:没时间的话如果有好的算法也可以说出来分享一下~HOHO~
发一下偶的巨土的穷举法实现~~
package com.gufengdebianyuan;
import java.util.*;
import java.lang.*;
/*
* 该类的主要作用是模拟蚂蚁的各种属性
*/
public class Mayi {
//构造函数
public Mayi(String para,int coordinate){
this.coordinate = coordinate;
sum = 0;
state = true;
if(para.equals("0")){
direction = -1;
}
else
{
direction = 1;
}
}
//方向
public int direction;
//走动量
public int sum;
//当前坐标
public int coordinate;
//状态(是已落杆还是行进中)
public boolean state;
//判断蚂蚁是否已经落杆
public void judge()
{
if(coordinate<=0||coordinate>=27)
{
state = false;
}
}
//模拟蚂蚁走路的步骤
public void go()
{
if(state){
coordinate = coordinate + direction;
sum++;
}
judge();
}
}
/**
* 该类的主要作用是穷举所有可能发生的蚂蚁的初始化状态
*/
public class Step {
//存放所有的初始化状态
public ArrayList list;
//构造函数,初始化链表
public Step()
{
list = new ArrayList();
}
//把每种初始化状态加到链表中
public void addStep(int a,int b,int c,int d,int e){
String tal = String.valueOf(a)+String.valueOf(b)+String.valueOf(c)+
String.valueOf(d)+String.valueOf(e);
list.add(tal);
}
//返回链表的大小
public int size(){
return list.size();
}
//返回指定位置的初始化状态
public Object get(int i){
return list.get(i);
}
}
/**
* 主类,模拟蚂蚁的运动过程,并记录数据进行分析
*/
public class Test {
//存放所有可能出现的初始情况
Step steplist;
int a,b ,c ,d ,e;
public Test(){
a = 0;
b = 0;
c = 0;
d = 0;
e = 0;
steplist = new Step();
}
//把所有的初始情况增加到steplist中
public void add(){
for(int a=0;a<2;a++)
{
for(int b=0;b<2;b++)
{
for(int c=0;c<2;c++)
{
for(int d=0;d<2;d++)
{
for(int e=0;e<2;e++)
{
steplist.addStep(a,b,c,d,e);
}
}
}
}
}
}
//看两只蚂蚁是否碰头,若碰头则进行转向处理
public static void balance(Mayi mayia,Mayi mayib){
if(mayia.coordinate==mayib.coordinate)
{
mayia.direction = (-1)*mayia.direction;
mayib.direction = (-1)*mayib.direction;
}
}
public static void main(String []args)
{
Test test = new Test();
test.add();
//用向量存放每种情况的最后一只蚂蚁爬下杆子时的步数
Vector total = new Vector();
Mayi mayi1,mayi2,mayi3,mayi4,mayi5;
//循环每一种初始化状态
for(int i=0;i<test.steplist.size();i++)
{
//取当前的五个蚂蚁的初始化状态
String tempTest = (String)test.steplist.get(i);
mayi1 = new Mayi(tempTest.substring(0,1),3);
mayi2 = new Mayi(tempTest.substring(1,2),7);
mayi3 = new Mayi(tempTest.substring(2,3),11);
mayi4 = new Mayi(tempTest.substring(3,4),17);
mayi5 = new Mayi(tempTest.substring(4,5),23);
while(mayi1.state||mayi2.state||mayi3.state||mayi4.state||mayi5.state)
//判断是否所有的蚂蚁都已下杆,若不是则继续循环
{
//蚂蚁开始行走
mayi1.go();
mayi2.go();
mayi3.go();
mayi4.go();
mayi5.go();
//判断蚂蚁是否有碰头
Test.balance(mayi1,mayi2);
Test.balance(mayi2,mayi3);
Test.balance(mayi3,mayi4);
Test.balance(mayi4,mayi5);
}
int []temp = new int[]{mayi1.sum,mayi2.sum,mayi3.sum,mayi4.sum,mayi5.sum};
//为当前次每个蚂蚁行走的步数排序
Arrays.sort(temp);
total.add(String.valueOf(temp[4]));
}
//为每次的最大步数组成的链表排序
Collections.sort(total);
System.out.println("蚂蚁爬出杆子的最短时间为:"+total.elementAt(0)+"秒;");
System.out.println("蚂蚁爬出杆子的最长时间为:"+total.lastElement()+"秒。");
}
}
[此贴子已经被作者于2006-11-19 20:27:17编辑过]