一道让人蛋疼的面试题

　　昨日看到了两道面试题，有两道，第一道很多人都答出来了，第二道却鲜有人回答。我本人最近在学习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>$j++<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>$min<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>$i++<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>])) {
                <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教程有兴趣的朋友有所帮助。