一道让人蛋疼的面试题
昨日看到了两道面试题,有两道,第一道很多人都答出来了,第二道却鲜有人回答。我本人最近在学习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只蚂蚁没影响这一步很不容易,否则就会像我上面第一种方法一样费力不讨好。

“你的组织要求你更改PIN消息”将显示在登录屏幕上。当在使用基于组织的帐户设置的电脑上达到PIN过期限制时,就会发生这种情况,在该电脑上,他们可以控制个人设备。但是,如果您使用个人帐户设置了Windows,则理想情况下不应显示错误消息。虽然情况并非总是如此。大多数遇到错误的用户使用个人帐户报告。为什么我的组织要求我在Windows11上更改我的PIN?可能是您的帐户与组织相关联,您的主要方法应该是验证这一点。联系域管理员会有所帮助!此外,配置错误的本地策略设置或不正确的注册表项也可能导致错误。即

Windows11将清新优雅的设计带到了最前沿;现代界面允许您个性化和更改最精细的细节,例如窗口边框。在本指南中,我们将讨论分步说明,以帮助您在Windows操作系统中创建反映您的风格的环境。如何更改窗口边框设置?按+打开“设置”应用。WindowsI转到个性化,然后单击颜色设置。颜色更改窗口边框设置窗口11“宽度=”643“高度=”500“>找到在标题栏和窗口边框上显示强调色选项,然后切换它旁边的开关。若要在“开始”菜单和任务栏上显示主题色,请打开“在开始”菜单和任务栏上显示主题

默认情况下,Windows11上的标题栏颜色取决于您选择的深色/浅色主题。但是,您可以将其更改为所需的任何颜色。在本指南中,我们将讨论三种方法的分步说明,以更改它并个性化您的桌面体验,使其具有视觉吸引力。是否可以更改活动和非活动窗口的标题栏颜色?是的,您可以使用“设置”应用更改活动窗口的标题栏颜色,也可以使用注册表编辑器更改非活动窗口的标题栏颜色。若要了解这些步骤,请转到下一部分。如何在Windows11中更改标题栏的颜色?1.使用“设置”应用按+打开设置窗口。WindowsI前往“个性化”,然

您是否在Windows安装程序页面上看到“出现问题”以及“OOBELANGUAGE”语句?Windows的安装有时会因此类错误而停止。OOBE表示开箱即用的体验。正如错误提示所表示的那样,这是与OOBE语言选择相关的问题。没有什么可担心的,你可以通过OOBE屏幕本身的漂亮注册表编辑来解决这个问题。快速修复–1.单击OOBE应用底部的“重试”按钮。这将继续进行该过程,而不会再打嗝。2.使用电源按钮强制关闭系统。系统重新启动后,OOBE应继续。3.断开系统与互联网的连接。在脱机模式下完成OOBE的所

任务栏缩略图可能很有趣,但它们也可能分散注意力或烦人。考虑到您将鼠标悬停在该区域的频率,您可能无意中关闭了重要窗口几次。另一个缺点是它使用更多的系统资源,因此,如果您一直在寻找一种提高资源效率的方法,我们将向您展示如何禁用它。不过,如果您的硬件规格可以处理它并且您喜欢预览版,则可以启用它。如何在Windows11中启用任务栏缩略图预览?1.使用“设置”应用点击键并单击设置。Windows单击系统,然后选择关于。点击高级系统设置。导航到“高级”选项卡,然后选择“性能”下的“设置”。在“视觉效果”选

在Windows11上的显示缩放方面,我们都有不同的偏好。有些人喜欢大图标,有些人喜欢小图标。但是,我们都同意拥有正确的缩放比例很重要。字体缩放不良或图像过度缩放可能是工作时真正的生产力杀手,因此您需要知道如何对其进行自定义以充分利用系统功能。自定义缩放的优点:对于难以阅读屏幕上的文本的人来说,这是一个有用的功能。它可以帮助您一次在屏幕上查看更多内容。您可以创建仅适用于某些监视器和应用程序的自定义扩展配置文件。可以帮助提高低端硬件的性能。它使您可以更好地控制屏幕上的内容。如何在Windows11

屏幕亮度是使用现代计算设备不可或缺的一部分,尤其是当您长时间注视屏幕时。它可以帮助您减轻眼睛疲劳,提高易读性,并轻松有效地查看内容。但是,根据您的设置,有时很难管理亮度,尤其是在具有新UI更改的Windows11上。如果您在调整亮度时遇到问题,以下是在Windows11上管理亮度的所有方法。如何在Windows11上更改亮度[10种方式解释]单显示器用户可以使用以下方法在Windows11上调整亮度。这包括使用单个显示器的台式机系统以及笔记本电脑。让我们开始吧。方法1:使用操作中心操作中心是访问

在iOS17中,Apple为其移动操作系统引入了几项新的隐私和安全功能,其中之一是能够要求对Safari中的隐私浏览选项卡进行二次身份验证。以下是它的工作原理以及如何将其关闭。在运行iOS17或iPadOS17的iPhone或iPad上,如果您在Safari浏览器中打开了任何“无痕浏览”标签页,然后退出会话或App,Apple的浏览器现在需要面容ID/触控ID认证或密码才能再次访问它们。换句话说,如果有人在解锁您的iPhone或iPad时拿到了它,他们仍然无法在不知道您的密码的情况下查看您的隐私


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Dreamweaver Mac version
Visual web development tools

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

Atom editor mac version download
The most popular open source editor

Notepad++7.3.1
Easy-to-use and free code editor
