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 i
dentical.
* 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 brea
k 2 eggs in the process
------SOLUTION-----
0.假设最高层总能使鸡蛋破裂
1.扔一次可以辨别高为多少层的楼: 2
2.扔N次可以辨别高为多少层的楼:假设为s(N)
第一个鸡蛋扔在第 N 层 破了->第二个鸡蛋逐层扔 最多扔 N-1 次
没破->其上s(N-1)层需要扔 N-1 次
所以s(N)=s(N-1)+N
3.s(N)=N(N+1)/2+1
4.s(14)=106>101 s(13)<101
-----
14层 一次
碎,就从第一层 一层一层的实验,14次
不碎,14+13=27,
在27碎,就从15层实验26层, 一共是14次,(包括14层的一次)
不碎,27+12=39一次,同上 也是14次
过程是 14+13+12+。。。+4=99
在任何一个地方碎了第一个鸡蛋,一共只需要14次即可,
如果在99层还不碎,那么已经用了 (14-3)=11次,在用一次在100层一共是12
所以最多14次
-----
按照你的格式 我们看看一般情况吧
假设有k个蛋 扔N次 最高辨认s(k,N)层
0.假设最高层碎
1.k>=N时s=2^N return
k==1时s=N return
2.s(k,N)=s(k-1,N-1)+s(k,N-1)+1
应该能整理出式子,我不会
python代码如下
#welcome to Script@yssy
def s(k,N):
if k>=N:
return 2**N
elif k==1:
return N
return s(k-1,N-1)+s(k,N-1)+1
if __name__=="__main__":
print s(2,14)
输出:
106
分享到:
相关推荐
拾人牙慧的故事.doc
拾人牙慧的解释和造句.doc
当然都是拾人牙慧,建议自己整理
我们在使用AI绘画工具时,最关键的就是prompt,但是我们不能总是拾人牙慧,总是用别人写出的现成的prompt,那样的话,最终画出来的画,也是别人画出来的,并不能完全生成自己想要的效果。所以,我们需要学习编写prompt...
基于CTreeCrl 一个拖拽树, 对初学者是有所帮助的, 我也是拾人牙慧。基于CTreeCrl 一个拖拽树, 对初学者是有所帮助的, 我也是拾人牙慧。
因为需要用到这个东西,所以很无耻的拾人牙慧,收藏一下。 <!DOCTYPE html> <html> <head> <meta http-equiv=Content-Type content=text/html; charset=utf-8 /> <title>无标题文档<...
中国象棋的算法描述,使用Java语言表达。是一个本科生的课程设计。拾人牙慧而已
使用cubemap生成6张图片,适合做室内全屏截图,可以在720云平台上生成全景图。如果有需要大家可以尝试一下,拾人牙慧。
而非括号部分为本人不想拾人牙慧,又想娓娓道来,而直接给出的参考,需要点开阅读。 目录什么是PIR?热释电效应(Pyroelectric Effect)概念历史原理用途菲涅尔透镜(Fresnel lenses)概念、历史原理用途PIR的原理...
做电路的人都知道需要在芯片附近放一些小电容,至于放多大?放多少?怎么放?将该问题讲清除的文章很多,只是比较零散的分布于一些前辈...鄙人试着采用拾人牙慧的方法将几个问题放在一起讨论,希望能加深对该问题的理解
1、明确设计的方向 首先我们应该明确我们在为哪些用户做设计,了解这些... 其次还要理解公司的战略,比如:假如已经有同类产品流行于市场,差异化就是公司必须要考虑的,拾人牙慧者必死。公司对市场的决策也是要参