一道讓人蛋疼的面試題

　　昨日看到了兩道面試題，有兩道，第一道很多人都答出來了，第二道卻鮮有人回答。我自己最近在學習php，所以這篇文章以php為基礎帶來今天帶來第二道的分析。

附兩道面試題：

　　1：大廳裡有100盞燈，每盞燈都編了號碼，分別為1-100。每盞燈由一個開關來控制。 （開關按一下，燈亮，再按一下燈滅。開關的編號與被控制的燈相同。）開始時，燈是全滅的。現在請依照以下規則按動開關。
第一次，將所有的燈點亮。
第二次，將所有2的倍數的開關按一下。
第三次，將所有3的倍數的開關按一下。
以此類推。第N次，將所有N的倍數的開關按一下。
問第100次按完以後，大廳裡還有幾盞燈是亮的。
　　2：有一根27公分的細木桿，在第3公分、7公分、11公分、17公分、23公分這五個位置各有一隻螞蟻。木桿很細，不能同時通過一隻螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會後退。當任兩隻螞蟻碰頭時，兩隻螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一公分的距離。寫出程序，求所有螞蟻都離開木桿的最小時間和最大時間。

    　 第一道比較簡單不多說了，第二道看著就讓人頭痛。

　　簡單分析一下這題。

　　從題本身來看，似乎同時考慮五個螞蟻的位置著實讓人摸不著頭腦。所幸題的最後一句還是很有用的，所有螞蟻都離開木桿的最大時間和最小時間。將細桿作為一個橫向的座標軸。螞蟻位置都已經給。當最後離開的螞蟻的位置=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'=27時，停止循環，返回'$i'。其中用了大量的循環遍歷。當然為了簡便，當'$arr[$k]'不再在桿子上時，可以利用unset()函數將其刪除。最後判斷'$arr'為空就可以結束循環。

　　講完主體內容，我們還必須處理一個小細節，如何產生描述螞蟻運動狀態的數組"$b"?

　　總不能手動生成吧，5隻螞蟻32種情況，10隻螞蟻1024種情況手動生成著實蛋疼。但你明明又知道生成32個數組，不能不利用。因而我們很容易想到將十進制數轉換為長度為5的二進制數。再將這個二進制數中的0替換為-1。將替換後的字串轉換為陣列。

　　最後貼上對應代碼：

<?<span>php
</span><span>for</span>(<span>$j</span>=0;<span>$j</span><32;<span>$j</span>++<span>){

    </span><span>$var</span>=<span>sprintf</span>("%05b", <span>$j</span><span>);

    </span><span>$var</span>=<span>str_replace</span>('1', '1|', <span>$var</span><span>);
    </span><span>$var</span>=<span>str_replace</span>('0', '-1|', <span>$var</span><span>);

    </span><span>$b</span>=<span>explode</span>('|',<span>$var</span><span>);

    </span><span>$res</span>=getRes(<span>$b</span><span>);


    </span><span>if</span> (<span>isset</span>(<span>$min</span><span>)) {
        </span><span>if</span> (<span>$res</span><<span>$min</span><span>) {
            </span><span>$min</span>=<span>$res</span><span>;

        }
    }</span><span>else</span><span>{
        </span><span>$min</span>=<span>$res</span><span>;
    }
    </span><span>if</span> (<span>isset</span>(<span>$max</span><span>)) {
        </span><span>if</span> (<span>$res</span>><span>$max</span><span>) {
            </span><span>$max</span>=<span>$res</span><span>;
        }
    }</span><span>else</span><span>{
        </span><span>$max</span>=<span>$res</span><span>;
    }
    </span><span>print_r</span>(<span>$b</span><span>);
    </span><span>echo</span> "此次结果是".<span>$res</span>.'   $max='.<span>$max</span>.'  $min='.<span>$min</span><span>;
    </span><span>echo</span> "<hr/>"<span>;

}


</span><span>echo</span> "最大值是".<span>$max</span>."最小值是".<span>$min</span><span>;


</span><span>//</span><span>获得某种情况下的时间</span><span>function</span> getRes(<span>$b</span><span>){
    </span><span>$arr</span>=<span>array</span>(3,7,11,17,23<span>);
    </span><span>for</span>(<span>$i</span>=1;<span>$i</span><100;<span>$i</span>++<span>){

        </span><span>foreach</span> (<span>$arr</span><span>as</span><span>$k</span> => <span>$val</span><span>) {
            </span><span>$arr</span>[<span>$k</span>]=<span>$val</span>+<span>$b</span>[<span>$k</span><span>];
            </span><span>if</span> (<span>$arr</span>[<span>$k</span>]==@<span>$arr</span>[<span>$k</span>-1<span>]) {
                </span><span>$b</span>[<span>$k</span>]=-<span>$b</span>[<span>$k</span><span>];
                </span><span>$b</span>[<span>$k</span>-1]=-@<span>$b</span>[<span>$k</span>-1<span>];
            }

            </span><span>if</span> ((<span>$arr</span>[<span>$k</span>]>=27)||(<span>$arr</span>[<span>$k</span>]<=0<span>)) {
                </span><span>unset</span>(<span>$arr</span>[<span>$k</span><span>]);
            }
        }


        </span><span>if</span> (<span>empty</span>(<span>$arr</span><span>)) {
            </span><span>return</span><span>$i</span><span>;
        }


    }

}</span>

　　　php並不擅長數學運算，筆者更不擅長數學運算。感覺自己上面寫的程式碼也就勉強能夠完成任務。也希望得到大家的指導。

以上就介紹了一道讓人蛋疼的面試題，包括了方面的內容，希望對PHP教程有興趣的朋友有幫助。