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