Re: [讨论] Google面试问题

楼主: artingo (那就起而行吧)   2014-04-13 12:08:42
个人认为正解是“最多七次”
因为一次可以删掉最多50%的二分法,最多到第七次就能测出了
大家可以画二分法的树状图,第七层就答案出来了
第一次:丢50楼
第二次:有破丢25楼,没破去75楼丢
依此类推.....
(接下来bbs我不会画树状图,所以只列出每次都破的情况)
第三次:有破丢13楼
第四次:有破丢7楼
第五次:有破丢4楼
第六次:有破丢2楼
第七次:视上面结果,再去1或3楼丢,答案出来!
以上面结果为例,可能的历史进程就是
progress(50,25,13,7,4,2,1)=>得证1楼就会破
progress(50,25,13,7,4,2,3)=>得证到3楼才会破,2楼safe
还有另外62种可能的结果
因树状图共有七阶,有2的(7-1)次方,总共64种可能的历史进程,但最多只要测7次
另颗蛋是完全相同的,所以没必要再测一次,只是益智题的障眼法。
※ 引述《bleed1979 (十三)》之铭言:
: ※ [本文转录自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 标题: [讨论] Google面试问题
: 时间: Sat Apr 12 02:07:46 2014
: 问题:
: 假设你有两颗蛋,然后有一栋100层楼高的大楼。
: 而蛋的特性有的可能很坚固,坚固到从一百层楼跌下都没事,
: 有的可能很脆弱,一楼就可以摔破。
: 现在你只知道这这两颗蛋是完全相同的,
: 你想要知道蛋最高从哪一层楼摔下来不会摔破。
: 问题是:你要摔几次才能计算出来?
: (如果你低于高度摔下蛋,蛋就没事,如果高于那个楼层,蛋就完蛋)
: 在这过程你可以摔破蛋。
:
作者: exxfyy901926 (exfy)   2014-04-13 12:10:00
只有两颗蛋,50楼破25楼又破,就没得测了
作者: hobart277   2014-04-13 12:16:00
大家都知道如果有无限颗蛋的话用binary search
作者: zilong308 (大师兄)   2014-04-13 12:19:00
有破就要从前一次没破的楼层一层一层测,因为只剩一颗蛋
作者: zilong308 (大师兄)   2014-04-13 12:20:00
但一路没破的状况应该是七次无误,但这样另一颗蛋没用到
作者: zilong308 (大师兄)   2014-04-13 12:22:00
这题目应该是问最少几次吧 最多是50次
作者: msty (Ting)   2014-04-13 12:37:00
三层测一次, 破了就拿另一颗测下一层, 都破就是3n-2层。
作者: demonhell (I count to three...)   2014-04-13 12:54:00
你只有两颗蛋 还二分法 题目不看清楚一下就被刷掉了
作者: msty (Ting)   2014-04-13 13:00:00
二分一定错, 不过四层一组,应该才是最佳解。
作者: msty (Ting)   2014-04-13 13:02:00
这题应该是2(蛋的个数)状态数去计算。
作者: apley (佛渡有缘人)   2014-04-13 14:30:00
你只有2个蛋, 连‘前提’都不理的解法就是GG再联络
作者: apley (佛渡有缘人)   2014-04-13 14:31:00
如果写程式可以无视硬件资源的前提, 那暴力解可多了....
作者: keieykdx (YOz桑)   2014-04-13 14:31:00
sorry 题目看不懂可以多看几次
楼主: artingo (那就起而行吧)   2014-04-13 14:56:00
题目已写过程可以摔破蛋啊
楼主: artingo (那就起而行吧)   2014-04-13 14:57:00
哪里有写蛋破就没了?
作者: shoube (B仔)   2014-04-13 15:06:00
可以摔破蛋是指这种状况在实验过成中是合理的
作者: shoube (B仔)   2014-04-13 15:07:00
可是你只有两次机会 这样很难懂吗==
作者: shoube (B仔)   2014-04-13 15:09:00
如过要用这种方法解提目怎么会只给你两颗蛋
作者: shoube (B仔)   2014-04-13 15:10:00
“蛋就完蛋”四个字没看到…?
作者: shoube (B仔)   2014-04-13 15:14:00
如果题目给你7颗蛋用此法就最适合
作者: cha122977 (CHA)   2014-04-13 16:11:00
你只有两颗蛋,蛋可以破,但显然不会补啊…
作者: kurumi31034   2014-04-13 17:49:00
左边的门自行出去谢谢
作者: chenlarry (小鬼)   2014-04-13 18:21:00
第一句话就已经说了只有两颗蛋..
作者: debut (humming bird)   2014-04-13 22:06:00
如你所说,题目已写过程可以摔破蛋,但有说蛋破了再补给你吗?

Links booklink

Contact Us: admin [ a t ] ucptt.com