抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

面试智力题汇总

1000 瓶药水找毒药

一共 1000 瓶药水,其中 1 瓶有毒药。

已知小白鼠喝毒药一天内死,若想在一天内找到毒药,最少需要几只小白鼠?

答案:10 只

解析:二进制思想。

0 000 000 001 表示 1 号老鼠,喝了药水 1 。

0 000 000 010 表示 2 号老鼠,喝了药水 2 。

0 000 000 011 表示 1 号、 2 号老鼠,喝了药水 3 。

… …

1 111 101 000 表示 4、6、7、8、9、10 号老鼠,喝了药水 1000。

按照上述的方法依次喝

第一回合,1 号老鼠喝药水 1

第二回合,2 号老鼠喝药水 2

第一千回合,4、6、7、8、9、10 号老鼠喝药水 1000

喝完一天时,看 10 只老鼠的状态,根据老鼠状态就知道哪瓶药水有毒了。

比如最后只是 2 号老鼠死了,那就说明第 2 瓶药水有毒;如果 4、6、7、8、9、10 死了,那就说明第 1000 瓶药水有毒!

想明白这个道理,再来看怎么答案为何是 10

我们需要让二进制表示的种类数>=药水总数(1000)

求的是最小值,显然,为 10 的时候满足要求

也可以这么计算:⌈ log N ⌉,log 底数为 2

抢 30

抢 30 是双人游戏
游戏规则是:第一个人喊 “ 1 ”或 “ 2 ”,第二个人要接着往下喊一个或两个数,然后再轮到第一个人。

两人轮流进行下去。最后喊 30 的人获胜。问喊数字的最佳策略。

答案:尽量喊 3 的倍数

解析:倒着看,其实,喊 27 时,就决定胜负了。假设 A 喊了 27,B 只能喊 28 或 29 ,下个回合,A 一定可以喊 30。也就是说,喊 27 者必胜。

再倒着看,其实喊 24 时,就定胜负了。假设 A 喊了 24 ,B 只能喊 25 或 26 ,下个回合 A 一定能喊 27 。

由于喊 27 者必胜,因此喊 24 者也必胜。

同理可以推出:喊 3 的倍数者必胜

然后就会发现,这个游戏,谁先喊,谁一定输

灯泡开关

一个圆环上有 100 个灯泡,灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。

设计一种算法,对于任意初始状态,使所有灯泡全亮。

将灯泡编号 1 ~ 100

步骤一:将灯泡变为全亮或只剩一个为暗

从 1 循环到 98 ,遇到暗的则按它下一个,使之变亮。循环完毕,1 ~ 98 必然全亮。99 和 100 可能为亮亮、暗亮、亮暗、暗暗四种状态。

  • 若为亮亮,皆大欢喜,满足题目要求
  • 暗亮、亮暗,达到只剩一个为暗的状态;
  • 若为暗暗。则按下编号 100 的灯泡,使编号 99 、100 变为亮,编号 1 的灯泡变为暗,从而达到只剩一个为暗的状态。

步骤二:将灯泡变为全暗

由于灯泡环形摆放,我们指定暗的灯泡编号为 1 ,将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后,使得所有灯泡变为暗。

步骤三:将灯泡变为全亮

将所有灯泡按一下,灯泡变为全亮。

拓展

对于 N 个灯泡的任意初始状态 ( N > 3 ) ,能否经过若干次操作使得所有灯泡全亮?

N 个灯泡做分类讨论。

  1. N = 3*k+1 一定可以。方法与上述步骤相同,在步骤二中可以将 3k 个亮的灯泡分为 k 组。
  2. N = 3*k+2 一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗,其余 3 * k 个灯泡分组按即可。因为,对于任意只剩一个为暗的状态,按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态!
  3. N = 3*k 不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解;否则,无解。(该结论有待证明)

评论



Modify from Volantis theme Powered by Hexo