日期:2014-05-20  浏览次数:20757 次

也搞一个逻辑问题,大家看看谁能很快回答上来
这是我进一个公司时的面试题,当初没打上来(答了,但回答错了),可能由于紧张过度?废话少说,大家看题,看谁可以很快回答出来。
一个100层的高楼,已知从某一层楼开始往下抛一枚棋子,棋子会摔碎。现在给你两枚这样的棋子,不考虑爬楼,下楼拣棋子等过程,用一个好的方案,快速的把恰好能摔碎棋子的楼层找到(答案应该好猜,推理过程就显得比较重要了)。

------解决方案--------------------
50楼开始扔,摔不碎75楼开始摔,摔不碎83楼开始摔......
------解决方案--------------------
这不就和判断一个数字在不在一组数字中一样嘛。
------解决方案--------------------
偶觉得应该二楼开始摔,摔不烂,就上四楼摔,再不烂就六楼。。。每次爬二层。

一直到摔烂为止,如果摔烂了,就退回下一层再摔一次。

如果下一层能摔烂,就是这层,不然就是刚才那层。。
------解决方案--------------------
yuanarea(我就是个送外卖的~~~) ( ) 信誉:100 2007-07-25 08:29:45 得分: 0


50楼开始扔,摔不碎75楼开始摔,摔不碎83楼开始摔......


同意
------解决方案--------------------
yuanarea(我就是个送外卖的~~~) ( ) 信誉:100 2007-07-25 08:29:45 得分: 0


50楼开始扔,摔不碎75楼开始摔,摔不碎83楼开始摔......


同意

偶觉得你们方法不行。要50楼扔烂了,那就下25,25再扔烂了。。
下13再扔。。。可二个棋子都烂了,你拿什么扔。。
------解决方案--------------------
wweennbb() ( ) 信誉:100 2007-07-25 10:55:35 得分: 0


偶觉得应该二楼开始摔,摔不烂,就上四楼摔,再不烂就六楼。。。每次爬二层。

一直到摔烂为止,如果摔烂了,就退回下一层再摔一次。

如果下一层能摔烂,就是这层,不然就是刚才那层。。

---------------------
我觉得正确
------解决方案--------------------
wweennbb() ( ) 信誉:100 2007-07-25 10:55:35 得分: 0


偶觉得应该二楼开始摔,摔不烂,就上四楼摔,再不烂就六楼。。。每次爬二层。

一直到摔烂为止,如果摔烂了,就退回下一层再摔一次。

如果下一层能摔烂,就是这层,不然就是刚才那层。。
--------------------------------------------

------解决方案--------------------
2楼开始
不碎 4楼
不碎 8楼
不碎 16楼……

32楼碎了 17楼——〉18楼——〉……——〉31楼
32楼不碎 34——〉40——〉44——〉52——〉64
64楼碎了 53——〉54——〉……——〉63

64楼不碎——〉66——〉70——〉78——〉86——〉100
依此类推

碎的楼层越高,这个算法越有利
------解决方案--------------------
思路是对的,可惜楼层弄错了

应该从3楼而不是2楼开始摔~
------解决方案--------------------
每次只能增加两层,否则不可能用剩下的一个确认精确的楼层~
------解决方案--------------------
哦,一下没想清楚,房子是没有0层的
------解决方案--------------------
用一个判断碎的所在区域,剩下一个只能一层一层试,每次只能增加1层
------解决方案--------------------
只有两枚棋子,拜托都看清题再说~
------解决方案--------------------

50楼开始扔,摔不碎75楼开始摔,摔不碎83楼开始摔. 这个最坏情况是O(N)/2
比较同意这个

------解决方案--------------------
总结一下:
二种扔法:
第一种:
从三楼开始扔,不烂,就上六楼扔,再不烂,就再上九楼。。。每次上三层。
一直到摔烂为止,如果扔烂了,就退回下二层再扔一次。就可以知道哪层扔得烂.
第二种:
从五十楼开始,不烂,就上75,再不烂。。。就再折半。。。
如果烂了,就退回上次扔的地方上一层开始一层一层扔。
如果五十楼扔烂,就从二楼开始往五十扔,每次上一层。

第二种对高层扔烂比较好,不过总体来说,还是第一种实用。
不知道大家觉得如何?
------解决方案--------------------
这个题去年程序员杂志上说过,好像是求 1+2+3+....+n> 100的最小整数n, 算出来的结果n,最为第一次的楼层,如果没碎,就将n-1最为第二次的”楼层增量“,如果碎了,就从0..n逐层试,以此类推,可以将次数 控制在n次之内
------解决方案--------------------
顶ls的,我也看到过
------解决方案--------------------
楼层间隔不能超过1层,够则你摔碎了,你只剩下一枚棋子,怎么判断剩下N层(N> 1)?