昨日看到了兩道面試題，有兩道，第一道很多人都答出來了，第二道卻鮮有人回答。我本人最近在學習php，所以本文以php為基礎帶來今天帶來第二道的分析。
附兩道面試題：
1：大廳裡有100盞燈，每盞燈都編了號碼，分別為1-100。每盞燈由一個開關來控制。（開關按一下，燈亮，再按一下燈滅。開關的編號與被控制的燈相同。）開始時，燈是全滅的。現在按照以下規則按動開關。
第一次，將所有的燈點亮。
第二次，將所有2的倍數的開關按一下。
第三次，將所有3的倍數的開關按一下。
以此類推。第N次，將所有N的倍數的開關按一下。
問第100次按完以後，大廳裡還有幾盞燈是亮的。
2：有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一只螞蟻。木桿很細，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會後退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。
第一道比較簡單不多說了，第二道看著就讓人頭疼。
簡單分析一下這道題。
從題本身來看，貌似同時考慮五個螞蟻的位置著實讓人摸不著頭腦。所幸題的最後一句還是很有用的，所有螞蟻都離開木桿的最大時間和最小時間。將細桿作為一個橫向的坐標軸。螞蟻位置都已經給出。當最後離開的螞蟻的位置<=0或者>=27的時候，所有螞蟻離開木桿。(這貌似是廢話。)
每秒1米，這樣的題設足夠讓人舒服。畢竟在此處螞蟻運動的時間數值上等於螞蟻運動的路程的數值。(如果考慮所有螞蟻離開木桿還繼續保持原有速度運動的話)。並且它們是同時運動。
螞蟻的運動方向只有兩個，向左或向右。考慮到坐標軸的實際情況，如果我們假設向右移動為1，那麼等價向左移動為-1。在計算機的二元世界這一步考慮是非常重要的。
好了，前面是鋪墊，不管您看懂看不懂，下面是更加重點的內容。
求最大時間和最小時間，就像我們在一堆數裡面找最大數和最小數一樣，這種事情應該不是很難。關鍵是找到最後做比較的時間。 時間和什麼有關系？從題設來看，只應該和初始每只螞蟻的運動狀態有關。至於期間某個時刻某只螞蟻的運動狀態我們有必要糾結麼？沒必要。那樣只會將問題復雜化。
螞蟻初始狀態有幾種?2^5=32種。顯然這32種每種花費時間都要算，利用一個簡單的循環就可以了。
關注螞蟻運動狀態無非兩個變量：位置和方向。因而在此處我簡單引入兩個數組 $arr和$b 。前者用來描述某個點的當前位置，後者用來當前方向。 $b[i]
如前面所描述的，取值只應該是-1或者1。
考慮到這裡，我們就可以捋順思路，給數組'$arr'和'$b'賦予一個初始值。利用時間'$i'做循環，每一秒每只螞蟻移動後，當'$arr[$k]==$arr[$k-1]'時，改變相匹配的狀態值'$b[k]'的值。 當所有的'$arr'的'value'<=0或者>=27時，停止循環，返回'$i'。其中用了大量的循環遍歷。當然為了簡便，當'$arr[$k]'不再桿子上時，可以利用unset()函數將其刪除。最後判斷'$arr'為空就可以結束循環。
講完主體內容，我們還必須處理一個小細節，如何生成描述螞蟻運動狀態的數組"$b"?
總不能手動生成吧，5只螞蟻32種情況，10只螞蟻1024種情況手動生成著實蛋疼。但你明明又知道生成32個數組，不能不利用。因而我們很容易想到將十進制數轉化為長度為5的二進制數。再將這個二進制數中的0替換為-1。將替換後的字符串轉化為數組。
貼上相應代碼：
<?php
for($j=0;$j<32;$j++){
$var=sprintf("%05b", $j);
$var=str_replace('1', '1|', $var);
$var=str_replace('0', '-1|', $var);
$b=explode('|',$var);
$res=getRes($b);
if (isset($min)) {
if ($res<$min) {
$min=$res;
}
}else{
$min=$res;
}
if (isset($max)) {
if ($res>$max) {
$max=$res;
}
}else{
$max=$res;
}
print_r($b);
echo "此次結果是".$res.' $max='.$max.' $min='.$min;
echo "<hr/>";
}
echo "最大值是".$max."最小值是".$min;
//獲得某種情況下的時間
function getRes($b){
$arr=array(3,7,11,17,23);
for($i=1;$i<100;$i++){
foreach ($arr as $k => $val) {
$arr[$k]=$val+$b[$k];
if ($arr[$k]==@$arr[$k-1]) {
$b[$k]=-$b[$k];
$b[$k-1]=-@$b[$k-1];
}
if (($arr[$k]>=27)||($arr[$k]<=0)) {
unset($arr[$k]);
}
}
if (empty($arr)) {
return $i;
}
}
}
這是按套路出牌的，循規蹈矩，一步一步走過來，但確實也十分辛苦。
------------------------------------- ---華麗的分隔線-------------------------------------------------------------------------------------------
在我一本正經地胡說八道後，就沒有更加好的想法？
那就是相遇的時候，兩只螞蟻開始掉頭。如果不掉頭直接走呢？和他們掉頭後有什麼差別？結果是沒有差別！每只螞蟻開頭拿一個接力棒，碰頭後，兩人交換接力棒，雖然螞蟻掉頭了，但接力棒可是一直往初始方向走哦~所以解題前景變得無比明朗。知道某只螞蟻的初始狀態，就知道他開始拿的接力棒最後走了多久！至於接力棒是不是親生的，那你管哩。反正最後一個接力棒離開桿子，最後一只螞蟻也離開桿子。
因而獲得某種初始狀態下的時間還可以這樣寫：
function getRes($b){
$arr=array(3,7,11,17,23);
for($i=1;;$i++){
foreach ($arr as $k => $val) {
$arr[$k]=$val+$b[$k];
if (($arr[$k]>=27)||($arr[$k]<=0)) {
unset($arr[$k]);
}
}
if (empty($arr)) {
return $i;
}
}
}
------------------------------------- ---華麗的分隔線-------------------------------------------------------------------------------------------
當然問題可以更加簡化，連上面的代碼都用不到了。
通過上面分析可以看做每只螞蟻直接走互不影響。到最後求最大值最小值的時候實際上可以先算出每只螞蟻到兩端的距離。形成五組數字。(3,24),(7,20),(11,16),(10,17),(4,23)在五組數每組數中較小值形成的5個數中最大的一個是最後結果的最小值。 五組數每組數中較大的5個數中最大的那個是結果的最大值。很容易看出來是11和24。為什麼呢？典型的木桶效應啊。最後一只螞蟻走出去了才能算完成整個事情。五只螞蟻全部最短路徑出去，得到結果才可能是最快的，五只螞蟻全部最長路徑出去，耗時才能是最慢的。
ps:應該不會有更快的想法了吧。
最後感謝@randeng在本問題上的指點~
