首页 > dp > 2 eggs problem

2 eggs problem

一个很老蛋很经典的问题了

Google Interview Puzzle : 2 Eggs Problem

The Standard Problem in simple writing goes like this:

* You are given 2 eggs.

* You have access to a 100-storey 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 100 th floor.Both eggs are identical.

* You need to figure out the highest floor of a 100-storey 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

大意是,两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋。

解决的策略是使用第一个鸡蛋从某一层测试,如果在该层碎了,则用第二个鸡蛋从最低层逐一测试;如果第一个鸡蛋没有碎,则问题得到了约减。

采用dp的思想,但是该问题的类型还不是很清楚,min max 有点像game theory中的那个啥玩意儿?以后希望得到相关的知识。用minNum[n]表示获得“鸡蛋从高n层的楼摔下不碎”需要的最小丢蛋次数。则有

转移方程:

minNum[n ] = min(1 + max(i – 1, minNum[n-i])) for 1<=i <= n

边界条件:

minNum[0] = 0; minNum[1] = 1

假设i是第一次扔鸡蛋的楼层,如果破了,则为了确定下面楼层中的安全位置,需要从第一层挨着试,需要i-1次;不碎的话上面还有n-i层,还剩两个鸡蛋,需要minNum[n-i]次。

据说POJ3783是一个推广形式,有时间做下看。

本文参考部分网页。

http://mathforum.org/wagon/past_solns/s921.html

http://www.techinterview.org/

http://www.impactinterview.com/2009/10/140-google-interview-questions/

About these ads
分类: dp
  1. 还没有评论。
  1. No trackbacks yet.

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

加关注

每发布一篇新博文的同时向您的邮箱发送备份。

%d bloggers like this: