一路让人蛋疼的面试题

一道让人蛋疼的面试题

　　昨日看到了两道面试题，有两道，第一道很多人都答出来了，第二道却鲜有人回答。我本人最近在学习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 style="color: #000000;">php</span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$j</span>=0;<span style="color: #800080;">$j</span>$j++<span style="color: #000000;">){    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">sprintf</span>("%05b", <span style="color: #800080;">$j</span><span style="color: #000000;">);    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">str_replace</span>('1', '1|', <span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$var</span>=<span style="color: #008080;">str_replace</span>('0', '-1|', <span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$b</span>=<span style="color: #008080;">explode</span>('|',<span style="color: #800080;">$var</span><span style="color: #000000;">);    </span><span style="color: #800080;">$res</span>=getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">);    </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">isset</span>(<span style="color: #800080;">$min</span><span style="color: #000000;">)) {        </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$res</span>$min<span style="color: #000000;">) {            </span><span style="color: #800080;">$min</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;        }    }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{        </span><span style="color: #800080;">$min</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;    }    </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">isset</span>(<span style="color: #800080;">$max</span><span style="color: #000000;">)) {        </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$res</span>><span style="color: #800080;">$max</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$max</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;        }    }</span><span style="color: #0000ff;">else</span><span style="color: #000000;">{        </span><span style="color: #800080;">$max</span>=<span style="color: #800080;">$res</span><span style="color: #000000;">;    }    </span><span style="color: #008080;">print_r</span>(<span style="color: #800080;">$b</span><span style="color: #000000;">);    </span><span style="color: #0000ff;">echo</span> "此次结果是".<span style="color: #800080;">$res</span>.'   $max='.<span style="color: #800080;">$max</span>.'  $min='.<span style="color: #800080;">$min</span><span style="color: #000000;">;    </span><span style="color: #0000ff;">echo</span> "<hr>"<span style="color: #000000;">;}</span><span style="color: #0000ff;">echo</span> "最大值是".<span style="color: #800080;">$max</span>."最小值是".<span style="color: #800080;">$min</span><span style="color: #000000;">;</span><span style="color: #008000;">//</span><span style="color: #008000;">获得某种情况下的时间</span><span style="color: #0000ff;">function</span> getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">){    </span><span style="color: #800080;">$arr</span>=<span style="color: #0000ff;">array</span>(3,7,11,17,23<span style="color: #000000;">);    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=1;<span style="color: #800080;">$i</span>$i++<span style="color: #000000;">){        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #800080;">$arr</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$k</span> => <span style="color: #800080;">$val</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]=<span style="color: #800080;">$val</span>+<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];            </span><span style="color: #0000ff;">if</span> (<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]==@<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>-1<span style="color: #000000;">]) {                </span><span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>]=-<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];                </span><span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>-1]=-@<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span>-1<span style="color: #000000;">];            }            </span><span style="color: #0000ff;">if</span> ((<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]>=27)||(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>])) {                <span style="color: #0000ff;">unset</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]);            }        }        </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">empty</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">)) {            </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$i</span><span style="color: #000000;">;        }    }}</span>

　　这是按套路出牌的，循规蹈矩，一步一步走过来，但确实也十分辛苦。

------------------------------------- ---华丽的分隔线-------------------------------------------------------------------------------------------

　

　　　在我一本正经地胡说八道后，就没有更加好的想法？

　　那就是相遇的时候，两只蚂蚁开始掉头。如果不掉头直接走呢？和他们掉头后有什么差别？结果是没有差别！每只蚂蚁开头拿一个接力棒，碰头后，两人交换接力棒，虽然蚂蚁掉头了，但接力棒可是一直往初始方向走哦~所以解题前景变得无比明朗。知道某只蚂蚁的初始状态，就知道他开始拿的接力棒最后走了多久！至于接力棒是不是亲生的，那你管哩。反正最后一个接力棒离开杆子，最后一只蚂蚁也离开杆子。

　　因而获得某种初始状态下的时间还可以这样写：

<span style="color: #0000ff;">function</span> getRes(<span style="color: #800080;">$b</span><span style="color: #000000;">){    </span><span style="color: #800080;">$arr</span>=<span style="color: #0000ff;">array</span>(3,7,11,17,23<span style="color: #000000;">);    </span><span style="color: #0000ff;">for</span>(<span style="color: #800080;">$i</span>=1;;<span style="color: #800080;">$i</span>++<span style="color: #000000;">){        </span><span style="color: #0000ff;">foreach</span> (<span style="color: #800080;">$arr</span> <span style="color: #0000ff;">as</span> <span style="color: #800080;">$k</span> => <span style="color: #800080;">$val</span><span style="color: #000000;">) {            </span><span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]=<span style="color: #800080;">$val</span>+<span style="color: #800080;">$b</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">];            </span><span style="color: #0000ff;">if</span> ((<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>]>=27)||(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span>])) {                <span style="color: #0000ff;">unset</span>(<span style="color: #800080;">$arr</span>[<span style="color: #800080;">$k</span><span style="color: #000000;">]);            }        }        </span><span style="color: #0000ff;">if</span> (<span style="color: #0000ff;">empty</span>(<span style="color: #800080;">$arr</span><span style="color: #000000;">)) {            </span><span style="color: #0000ff;">return</span> <span style="color: #800080;">$i</span><span style="color: #000000;">;        }    }}</span>

------------------------------------- ---华丽的分隔线------------------------------------------------------------------------------------------- 　　

　　

　　当然问题可以更加简化，连上面的代码都用不到了。

　　通过上面分析可以看做每只蚂蚁直接走互不影响。到最后求最大值最小值的时候实际上可以先算出每只蚂蚁到两端的距离。形成五组数字。(3,24),(7,20),(11,16),(10,17),(4,23)在五组数每组数中较小值形成的5个数中最大的一个是最后结果的最小值。  五组数每组数中较大的5个数中最大的那个是结果的最大值。很容易看出来是11和24。为什么呢？典型的木桶效应啊。最后一只蚂蚁走出去了才能算完成整个事情。五只蚂蚁全部最短路径出去，得到结果才可能是最快的，五只蚂蚁全部最长路径出去，耗时才能是最慢的。

　　ps:应该不会有更快的想法了吧。

　　　最后感谢@randeng在本问题上的指点~

 

7楼gw2010

第一题不用编程怎么做？，第二题看到上面的答案了。

Re: DeanChopper

@gw2010，不好意思这个我也不清楚。。不过感觉学数学应该会考虑到一些比较简单的东西吧。

6楼温柔的意外

最短：←3 ←7 ←11 →17 →23，最长：3→ 7→ 11→ ←17 ←23

5楼DCD

其实没这么麻烦，最小时间，就是最理想状态下的时间，也就是位于11cm的蚂蚁往左走，11秒搞定。，最大时间，其实可以理解为两只蚂蚁碰面后，不是都往反方向走，而是对着穿过去。那么就是3cm的蚂蚁往右走，27-3=24秒。

4楼Ariex

第一个是计算哪些数分解出来的因数总数是奇数么？

Re: MrNice

@Ariex，对的，好像分析到最后就是完全平方数了

Re: DeanChopper

@Ariex，这是最直观的想法，我也是这么考虑的。不知道还有什么好的算法

3楼randeng

第二题，《编程之美》上有。两只蚂蚁碰头转向，你可以看做两只蚂蚁错身而过，互相影响。有两只蚂蚁A, B，A-gt;，Blt;-，当他们相遇后，Alt;-, B-gt;，你可以把相遇后的A作为相遇前B，B作为相遇前A，这样他们还是在继续向前移动。所有只需要遍历一次数组，分别求出运动时间，找出大小就行了。

Re: DeanChopper

@randeng，万分感谢，我一定会再看看的~~

2楼笑对当空

感觉不太对啊 我是用笨办法 模拟每一只蚂蚁的行走轨迹 发现 最快的才23 最慢的才35和你的两头距离最远多少就走了多少差距有点大啊，难道我算错了？

Re: DeanChopper

@笑对当空，最短的情况，前三只蚂蚁往左走，后两只往右走。耗时11秒。最慢的情况，全部往右走，耗时24秒。

1楼风生水起

第二题直接认为5只蚂蚁互相没有影响，最小时间就是所有蚂蚁都超最近的那头走，最大时间是所有蚂蚁都超最远的那头走，写程序就是判断每只蚂蚁离两头的具体，最小时间取最近中最大的（（所以是11），最大时间是取最远中最大（等于24）。一次循环就可以

Re: DeanChopper

@风生水起，实际分析到最后确实是这样的。更像脑急转玩儿了。主要是想到5只蚂蚁没影响这一步很不容易，否则就会像我上面第一种方法一样费力不讨好。