JAVA AJAX C++

最近有同學(xué)找工作,經(jīng)常在班級(jí)群里發(fā)一些大公司的面試,筆試題目.昨天收到這樣一個(gè)題目,據(jù)說是百度的面試題目.

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

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

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

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

package baidu;

public class Ant {
?/*
? * step 表示螞蟻每一個(gè)單位時(shí)間所走的長(zhǎng)度
? */
?private final static int step = 1;

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

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

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

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

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

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

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

?/**
? * 構(gòu)造函數(shù),設(shè)置螞蟻的初始前進(jìn)方向,和初始位置
? * @param position
? * @param direction
? */
?public Ant(int position, int direction) {
??this.position = position;
??if (direction != 1) {
???this.direction = -1;//方向設(shè)置初始位置,比如為0時(shí),也將其設(shè)置為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++;
????// 查看是否有已經(jīng)相遇的Ant,如果有則更改其前進(jìn)方向
????dealEncounter(antArray);
???}
???System.out.println(time);

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

?}

?/**
? * 這個(gè)函數(shù)的算法很亂，但暫時(shí)能解決問題
? *
? * @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();
????}
???}
??}

?}

?/**
? * 因?yàn)橛?只Ant，所以組合之后有32種組合.剛好用5位二進(jìn)制來表示,如果為0則表示Ant往0的方向走 如果為1,則表示往27的方向走
? *
? * 注:在通過Ant的構(gòu)造函數(shù)設(shè)置初始值時(shí),通過過濾把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;

?}

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

?/**
? * 取得設(shè)置好初始值的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都已經(jīng)走出了木桿,也就是設(shè)置退出條件
? *
? * @param antArray
? * @return
? */
?public static boolean isAllOut(Ant[] antArray) {
??for (Ant ant : antArray) {
???if (ant.isOut() == false) {
????return false;
???}
??}
??return true;
?}
}

?