注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

Google面试题(egg problem)解法分析[原创]  

2010-10-30 05:04:59|  分类: algorithms |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Google Interview Puzzle : 2 Egg Problem  

 

* You are given 2 eggs.  

* You have access to a 100-story building.  

* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical.  

* You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking.  

* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process  

 ***constrain description***

§  An egg that survives a fall can be used again.

§  A broken egg must be discarded.

§  The effect of a fall is the same for all eggs.

§  If an egg breaks when dropped, then it would break if dropped from a higher window.

§  If an egg survives a fall then it would survive a shorter fall.

§  It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 100th-floor windows do not cause an egg to break.

      此问题看起来十分有趣也不难却一时不知从何处下手,其实这种情况下可以考虑人品最差的情况,之后在此基础上进行优化,如果从此方向优化并证明能达到最优问题不就解开了吗!我们从任何一层扔下鸡蛋都是可能把蛋打坏的,因此我们的做法可以先从一楼去扔,如果不坏就再往上一层,依次下去。这样显然用打坏一个鸡蛋就可以解决问题了,可是我们有两个鸡蛋,这样我们可以尝试去冒险,从比较高的层a往下扔,如果失败我们只能用最后一个鸡蛋一层一层往上扔。但是如果万一我们中了,在a层蛋没有打坏,我们就可以从a+1层扔或是选择冒险。如果在a层打坏,我们的目标层一定在a层往下。注意上面的情况中有几点十分重要,一是当一个蛋打坏之后就只能从下面已知的不能打坏鸡蛋的层开始一层一层往上,不能再冒险了。二点就是从一层逐层往下上是效率最差的一种实验方式,没有比这更差的了。三是我们可能节约的实验次数只能来自我们的多出的一个鸡蛋去冒险而得。四点是这个最少实验次数是唯一的,不能有两个不相等最小,"两个不相等的最小值"?哦,病句,哥语文不及格,T T。

      好,现在由上面的特点出发来寻求问题的解。设我们第一次冒险的楼层是a1层,如果有每二次冒险就是a2层,以后依次类推。我们设最小的实验次数为N,如果我们在a1层冒险失败,那么我们从失败中能得到的信息只有我们要找寻的目标层是比a1小的层。现在我们只能从每一层逐次往上实验,最坏一共要实验a1-1次,这就是我们人品最差的情况,一共要a1-1+1=a1次,这是最小的,由最小的唯一性可知a1=N,如果我们这次冒险成功,那么一下次是a2层冒险,ok,现在如果在a2层失败,则此时要逐层实验的楼是a1+1到a2-1层(注意我们要在任何情况下都维持这个最小的解N,否则我们的实验次数就会变多),这种情况一共要a2-a1-2+1+2=a2-a1+1次,再由最小的唯一性,a2-a1+1=N,因此a2=2N-1,依此类推下去,a1,a2,……an与前一个的差依次是N,N-1,N-1……1,这个一共加起来很好算的, 是N(N+1)/2, 这些加起来一定要大于等于100层了,而N是整数,因此求得是N>=14,N能取到的最小值就是14了,因此我们用14次实验就一定可以把目标层找出。而冒险层的序列依次是14 27 39 50 60 69 77 84 90 95 99 100。

OK,问题搞定了,祝你思考愉快。

  评论这张
 
阅读(1152)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017