应聘百度的一道试题 - 黑马程序员技术交流社区

/**
* 模拟蚂蚁运行的木棒，木棒长度为l，有l个点，每个点上的蚂蚁数量初始化为0
* @author Administrator
*
*/
class L{
static int l = 27;
static int[] point = new int[l + 1];
static{
for(int i = 0; i < l + 1; i++){
point[i] = 0;
}
}
}
/**
* 蚂蚁类，有运动方向，初始位置，以及运动的方法及Thread的run方法，
* run方法模拟蚂蚁的实际运动
* @author Administrator
*
*/
class Ant extends Thread{
private static int[] F = {1, -1};//1向右，-1向左
private int f;
private int place;
private String name = "";
private static Object obj = new Object();
int time = 0;
//蚂蚁编号
static int num = 0;
//初始化蚂蚁的名称、运动方向（0向右，1向左）和位置
Ant(String name, int i, int place){
this.name = name;
this.f = F[i];
this.place = place;
if(L.point[place] != 0){
System.out.println("Error");
}
L.point[place] = 1;
}
//蚂蚁运动
public void run(){
//获取当前蚂蚁的编号
int c = num++;
while(place > 0 || place < L.l){
try {Thread.sleep(600);} catch (InterruptedException e) {}
//如果两只蚂蚁相遇，则调转方向，相遇设计成如果L上的某个点的蚂蚁数量大于1，
//为了保证这段代码能被安全的执行，将1s的sleep时间分成两个部分，使线程有足够的时间完成判断和调转方向
if(L.point[place] > 1){
f = -f;
System.out.println(name + " turn foward in " + place);
}
try {Thread.sleep(300);} catch (InterruptedException e) {}
place += f;
//如果已经抵达0点或者第27点，那么就离开，即设置0点和27点上的蚂蚁个数为0
//以及1和26点上的蚂蚁个数为0
if(place <= 0 || place >= L.l){
if(place <= 0){
L.point[place + 1] = 0;
}
if(place >= L.l){
L.point[L.l - 1] = 0;
}
//从1和26到0和27也需要1s的时间
time++;
break;
}
//加锁避免同时操作place，尤其两只蚂蚁到同一个点相遇的时
synchronized (obj) {
//蚂蚁到place点，则数量加1
L.point[place]++;
//蚂蚁所在的前一个位置的蚂蚁数量编程0
L.point[place - f] = 0;
}
//时间加1
time++;
}
System.out.println(name + " Time:" + time);
//保存结果到SearchTime中
SearchTime.runTime[c % 5] = time;
}
}
/**
* 搜索线程，可以搜索指定蚂蚁运动方向组合的所有蚂蚁都离开的时间
* @author Administrator
*
*/
class SearchTime extends Thread{
private int tag;
static int[] runTime = new int[5];
//搜索运动方向为tag指示的情况时的所有蚂蚁都离开L的时间
SearchTime(int tag){
this.tag = tag;
}
public void run(){
System.out.println("Start tag = " + tag);
//5只蚂蚁，方向一共有32种可能，因此tag应当是小于32大于0的数，tag的二进制
//每一个位代表一只蚂蚁的运动方向
if(tag >= 32 || tag < 0){
System.out.println("error");
}else{
Ant ant1 = new Ant("Ant1", tag & 1, 3);
Ant ant2 = new Ant("Ant2", (tag & 2) >> 1, 7);
Ant ant3 = new Ant("Ant3", (tag & 4) >> 2, 11);
Ant ant4 = new Ant("Ant4", (tag & 8) >> 3, 17);
Ant ant5 = new Ant("Ant5", (tag & 16) >> 4, 23);
ant1.start();
ant2.start();
ant3.start();
ant4.start();
ant5.start();
}
}
}
public class BaiduEm {
public static void main(String[] args) throws InterruptedException {
int[] result = new int[32];
for(int i = 0; i < 32; i++){
SearchTime st = new SearchTime(i);
st.start();
try {Thread.sleep(30000);} catch (InterruptedException e) {}
result[i] = findMax(SearchTime.runTime);
System.out.println("Max:" + result[i]);
}
System.out.println("所有蚂蚁都离开的最短时间：" + findMin(result) + "s" );
System.out.println("所有蚂蚁都离开的最长时间：" + findMax(result) + "s" );
}
/*
* 寻找一个数组中的最大值
*/
public static int findMax(int[] array){
int max = array[0];
for(int i = 0; i < array.length; i++){
max = array[i] > max ? array[i] : max;
}
return max;
}
/*
* 寻找一个数组中的最小值
*/
public static int findMin(int[] array){
int min = array[0];
for(int i = 0; i < array.length; i++){
min = array[i] < min ? array[i] : min;
}
return min;
}
}

复制代码