一道让人蛋疼的面试题

昨日看到了两道面试题,有两道,第一道很多人都答出来了,第二道却鲜有人回答。我本人最近在学习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;   }  } } 

php并不擅长数学运算,笔者更不擅长数学运算。感觉自己上面写的代码也就勉强能够完成任务。还希望得到大家的指导。

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 一道让人蛋疼的面试题

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址