首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
腾讯大厦有39层。你手里有两颗一模一样的玻璃珠,当你拿着玻璃
[问答题]
腾讯大厦有39层。你手里有两颗一模一样的玻璃珠,当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。大厦有个临界楼层,低于它的楼层,往下扔玻璃珠,玻璃珠不会碎;等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效方式。 请给出正确答案,给出算法代码有加分。
添加笔记
求解答(1)
邀请回答
收藏(15)
分享
纠错
2个回答
添加回答
3
帝斯卡影奥
要想知道哪一层是分界点,只有一种方法。那就是用一个球从某一层(我们已经确定是安全层)开始,向上一层一层地往下丢,最开始我们只能确定地面是安全的。因为有两个球,一个用来测定分界点,另外一个当然用来找安全层,测分界点的球只能一层一层丢,但是找安全层的球可以隔若干层丢。比如我们可以按1,2,4,8,16的顺序丢,要是某一层破了,就能确定前一次尝试的层数是安全层,然后开始用另一个球一层一层地找分界点。
因为我们考虑的最坏情况,要是找安全层的间隔过大,那么找分界点最坏情况下需要次数也会越多。所以我们应该把找安全层的间隔固定成相同的层数,而且每次尝试间隔还需要再比上次尝试的层数少一层(因为每一次尝试,探测的次数会+1,间隔不变的话,最坏情况的次数会随探测次数增加,我们要求不论怎样探测,最坏次数都不变的情况)。
假定找安全层时第一次挑的层数是X,那么之后的序列应该是X,2X-1,3X-1-2,4X-1-2-3.5X-1-2-3-4..Nx-1-2-3...-(N-1)(N是最后一次探测的次数);我们的目标就是使总的探测次数最小,然后求x的值。我们只考虑最坏情况,假设在第i次探测时球破裂,探测的是(i*x-(i-1)*i/2)层,上一次是((i-1)*x-(i-2)*(i-1)/2)层。那么找安全层的次数是i,找分界点的次数是(i*x-(i-1)*i/2)-((i-1)*x-(i-2)*(i-1)/2)=x-i次,总共加起来的次数是i+(x-i)=x次(最坏情况x次)。
我们希望第一次选的层数X越小越好,这样最坏情况就是X次,但是X要是太小的话,就会导致最后一次探测的层数不够高(比如第一次选4层,依照我们的策略,选择的序列是4,7,9,10;到10层就结束了,10层以上的部分该策略就失效了)。很明显这是个等差数列求和,第一次选X层,最终能到(X+1)*X/2的层数,使(X+1)*X/2>=39,在这个条件下求取X的最小值,推出min(X)=9。
所以选取的序列是9,17,24,30,35,39,最差需要9次能找到分界点。
编辑于 2017-03-31 20:53:36
回复(6)
0
脱缰的哈士奇~
第9层。
动态规划求解。
发表于 2017-03-30 12:34:34
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
动态规划
上传者:
牛100
难度:
2条回答
15收藏
2807浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题