JAVA AJAX C++

最近有同學找工作,經常在班級群里發一些大公司的面試,筆試題目.昨天收到這樣一個題目,據說是百度的面試題目.

?有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一只螞蟻。 木桿很細，不能同時通過一只螞蟻。開始 時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭， 但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一厘米的距離。 編寫程序，求所有螞蟻都離開木桿 的最小時間和最大時間。

看了這個題目之后,突然很感興趣,今天搞了半天把它做出來了,大概花了1個半小時.大公司的題目真是考人.反正都已經用算法實現了,我就不多說了,大家看代碼吧.代碼里面注釋我也盡量全寫了.一共有兩個類,一個是Ant的模型,一個是控制類.原代碼,大家可以在這取得:

http://m.tkk7.com/Files/itspy/baidu.rar

//////////////////////////////////////
/*百度面試題
?* 有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一只螞蟻。
?* 木桿很細，不能同時通過一只螞蟻。開始 時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，
?* 但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一厘米的距離。
?* 編寫程序，求所有螞蟻都離開木桿 的最小時間和最大時間。
?*
?*
?* 分析:題目中的螞蟻只可能相遇在整數點,不可以相遇在其它點,比如3.5cm處之類的,也就是可以讓每只螞蟻走 1秒,然后
?* 查看是否有相遇的即可.
?*
?* 這樣我的程序實現思路就是,初始化5只螞蟻,讓每只螞蟻走1秒,然后看是否有相遇的,如果有則做相應處理.當每只螞蟻都
?* 走出木桿時,我就記錄當前時間.這樣就可以得到當前狀態情況下,需要多久可以走出木桿,然后遍歷所有狀態則可以得到所胡
?* 可能.
?*/

package baidu;

public class Ant {
?/*
? * step 表示螞蟻每一個單位時間所走的長度
? */
?private final static int step = 1;

?/*
? * position表示螞蟻所處的初始位置
? */
?private int position;

?/*
? * direction表示螞蟻的前進方向，如果為1表示向27厘米的方向走， 如果為－1，則表示往0的方向走。
? */
?private int direction = 1;

?/*
? * 此函數運行一次，表示螞蟻前進一個單位時間，如果已經走下木桿則會拋出異常
? */
?public void walk() {
??if (isOut()) {
???throw new RuntimeException("the ant is out");
??}
??position = position + this.direction * step;
?};

?/**
? * 檢查螞蟻是否已經走出木桿，如果走出返回true
? *
? */

?public boolean isOut() {
??return position <= 0 || position >= 27;
?}

?/**
? * 檢查此螞蟻是否已經遇到另外一只螞蟻
? * @param ant
? * @return 如果遇到返回true
? */
?public boolean isEncounter(Ant ant) {
??return ant.position == this.position;
?}

?/**
? * 改變螞蟻的前進方向
? */
?public void changeDistation() {
??direction = -1 * direction;
?}

?/**
? * 構造函數,設置螞蟻的初始前進方向,和初始位置
? * @param position
? * @param direction
? */
?public Ant(int position, int direction) {
??this.position = position;
??if (direction != 1) {
???this.direction = -1;//方向設置初始位置,比如為0時,也將其設置為1.這樣可以方便后面的處理
??} else {
???this.direction = 1;
??}
?}

}

?

/////////////////////////////////////////////////////////

package baidu;

public class Controller {

?public static void main(String[] args) {

??int time = 0;
??for (int i = 0; i < 32; i++) {
???Ant[] antArray = getAntList(getPoistions(), getDirections(i));
???while (!isAllOut(antArray)) {
????for (Ant ant : antArray) {
?????if (!ant.isOut()) {
??????ant.walk();
?????}
????}
????time++;
????// 查看是否有已經相遇的Ant,如果有則更改其前進方向
????dealEncounter(antArray);
???}
???System.out.println(time);

???// 將時間歸0,這樣可以重新設置條件,再次得到全部走完所需要的時間.
???time = 0;
??}

?}

?/**
? * 這個函數的算法很亂，但暫時能解決問題
? *
? * @param list
? */
?public static void dealEncounter(Ant[] antArray) {

??int num_ant = antArray.length;
??for (int j = 0; j < num_ant; j++) {
???for (int k = j + 1; k < num_ant; k++) {
????if (antArray[j].isEncounter(antArray[k])) {
?????antArray[j].changeDistation();
?????antArray[k].changeDistation();
????}
???}
??}

?}

?/**
? * 因為有5只Ant，所以組合之后有32種組合.剛好用5位二進制來表示,如果為0則表示Ant往0的方向走 如果為1,則表示往27的方向走
? *
? * 注:在通過Ant的構造函數設置初始值時,通過過濾把0修改成了-1.
? */
?public static int[] getDirections(int seed) {
??int result[] = new int[5];
??result[0] = seed % 2;
??result[1] = seed / 2 % 2;
??result[2] = seed / 4 % 2;
??result[3] = seed / 8 % 2;
??result[4] = seed / 16 % 2;

??System.out.println("directions is " + result[0] + "|" + result[1] + "|"
????+ result[2] + "|" + result[3] + "|" + result[4]);

??return result;

?}

?/**
? * 批量設置Ant的初始位置,這樣設置不是十分必要,可以直接在代碼中設置
? *
? * @return
? */
?public static int[] getPoistions() {
??return new int[] { 3, 7, 11, 17, 23 };
?}

?/**
? * 取得設置好初始值的5只Ant
? *
? * @param positions
? * @param directions
? * @return
? */
?public static Ant[] getAntList(int[] positions, int[] directions) {
??Ant ant3 = new Ant(positions[0], directions[0]);
??Ant ant7 = new Ant(positions[1], directions[1]);
??Ant ant11 = new Ant(positions[2], directions[2]);
??Ant ant17 = new Ant(positions[3], directions[3]);
??Ant ant23 = new Ant(positions[4], directions[4]);

??return new Ant[] { ant3, ant7, ant11, ant17, ant23 };
?}

?/**
? * 判斷是否所有的Ant都已經走出了木桿,也就是設置退出條件
? *
? * @param antArray
? * @return
? */
?public static boolean isAllOut(Ant[] antArray) {
??for (Ant ant : antArray) {
???if (ant.isOut() == false) {
????return false;
???}
??}
??return true;
?}
}

?