最少测试次数：鸡蛋安全坠落楼层确定算法

两个蛋的问题

eggs

需积分: 30 57 浏览量更新于2024-07-19 收藏 964KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"两个蛋的问题（two eggs problem），也被称为鸡蛋掉落问题，源于Google和中国的一些大型互联网公司的面试挑战。该问题的核心是设计一个实验方案，通过仅使用两个硬度相同的鸡蛋，确定一座100层大楼中鸡蛋能够安全落地的最大楼层，同时确保在最坏情况下所需的测试次数最少。这个问题涉及到了计算机科学中的算法和优化策略，特别是概率和动态规划的思想。首先，我们面临的问题是一个典型的探索性问题，需要在有限的资源（两个鸡蛋）下，通过逐步尝试找到最优解。由于每层楼尝试一次都可能导致鸡蛋破碎，因此需要一个策略来最小化失败的可能性。最基础的方法可能是从顶层开始逐层下降，但这种“贪心”策略会导致较高的风险，因为一旦第一个鸡蛋在较低楼层破碎，我们就无法得知其安全高度。为了提高效率，我们可以采用二分查找或者回溯法。二分查找法适用于具有等差序列的场景，但在这里并不适用，因为楼层高度不是均匀分布的。回溯法则可以尝试在每次试验后根据结果调整策略，例如，如果一个鸡蛋在第50层摔碎，下一个鸡蛋就从第51层开始测试，逐渐向下试探，直到找到一个鸡蛋能够安全到达的楼层。更高级的策略可能涉及到随机化，比如蒙特卡洛方法或启发式搜索。蒙特卡洛方法可以通过大量的模拟实验，估计在每层楼扔鸡蛋的概率，从而选择一个最有可能成功的楼层。启发式搜索则可以结合一定的规则或经验，如尝试将鸡蛋扔在接近中间楼层的位置，因为理论上这减少了最坏情况的出现。文章《OR/MSGames: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong》由Moshe Sniedovich撰写，发表于INFORMS Transactions on Education，探讨了这个问题的数学模型和可能的解决方案。作者在这篇论文中详细分析了问题的复杂性，并提出了不同的算法和方法，包括优化版本的试探策略，旨在降低鸡蛋破损率和测试次数。然而，使用这些方法时必须注意版权规定，未经出版商明确许可，商业使用或大规模下载都是被禁止的。该文章强调了在学术研究、教学和个人学习领域的合法使用，并提供了相关的链接供读者获取完整条款和条件。两个蛋的问题不仅仅是一个简单的智力游戏，它展示了实际问题解决中的策略思维和优化技术，对于理解计算机科学中的搜索算法、概率论以及决策分析具有重要意义。"

资源详情

资源推荐

Although the term "Worst Case" is not used explicitly

in this description, this idea is conveyed by the term

"in all cases". As we shall see, one major advantage of

adopting this version of the puzzle is that the problem

is then relatively easy.

Under the Expected Value Scenario we assume that C

is the realization of a random variable, call it C, whose

probability distribution function over H := {0,1,2,...,H}

is known. It is assumed that in this case we wish to

minimize the expected value of the total number of

trials required to determine the value of C, assuming

that Mother Nature determines the value of C via some

given probability distribution over H. The difficulty

with this approach is that we have to postulate a

probability distribution over H. The most famous in-

stance of this scenario is Laplace's Scenario under which

it is assumed that C is uniformly distributed over H. We

assume that the reader is familiar with the distinction

we make here between the random variable C and a

particular value that it can take, C.

We shall consider in detail the Worst Case Scenario

and Laplace's Scenario and show how they can be an-

alyzed and solved via dynamic programming (DP).

And for the readers convenience, in the main body of

the paper we shall consider only the simple case where

2 test eggs are available. The analysis and solution of

problems where more than two test ages are available

is provided in the Appendix.

As a prelude you may wish to experiment with the

interactive module provided below. It simulates the

Worst Case Scenario so when you play with it assume

that Mother Nature is indeed playing against you.

Commentary:

To solve the puzzle using this module, you have to

either (i) completely change the red column into a

white column or (ii) have a gold box somewhere in

the blue column and a white box just below it in the

red or blue column or (iii) have a gold box in the first

position in either the red or blue column. In case (i)

we have C = H and in case (ii) we have C = G-1, where

G is the position of the lowest gold box in the red

column, and in case (iii) we have C = 0.

Needless to say, the objective is not merely to deter-

mine the value of C, but rather to determine how the

trials should be conducted so as to determine the

value of C with the least number of trials, regardless

of how Mother Nature plays her game. Observe,

however, that if we know the value of C, then it is

easy to construct an optimal policy to solve the

problem: we drop Egg 1 from position h = C + 1.

Naturally, it will crash. Then we drop Egg 2 from h

= 1, then from h=2, and so on up to h = C. The second

egg will survive all these trials. Note that this policy

requires exactly C + 1 trials: one with Egg 1 and C

SNIEDOVICH

OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong

剩余17页未读，继续阅读

鼓浪

粉丝: 1
资源: 13

最少测试次数：鸡蛋安全坠落楼层确定算法

高中英语单词天天记scramble素材

快乐英语第四册第十六课PPT课件.pptx

give me the c++ code of the solution of two eggs problem

一个人不小心打碎了一个妇女的一篮子鸡蛋。为了赔偿便询问篮子里有多少个鸡蛋。那妇女说，不清楚，只记得每次拿三个剩两个，拿五个剩三个，拿七个剩两个，若每个鸡蛋1.3元，计算最少应该赔偿多少钱 Python

需要把四个鸡蛋打到碗中然后再切两个西红柿，使用MTM方法分析以上过程，不要忘了需要有拿刀，移动等动作。并写出该过程的MTM-1代码，用表格表示更好哦

鸡蛋掉落问题穷举法c++代码

用c语言写一个蛋糕的代码

蛋仔派对Python代码

妈妈给小明家新送来 y个鸡蛋。 已知小明家原有鸡蛋的个数x是满足“3个3个数剩1个，5个5个数剩z个，7个7个数剩3个”的最小数， 请问小明家共有多少个鸡蛋?c语言程序

已知：从小卖部售买3种物品，分别是： 牛奶 ，50元/件 鸡蛋，2元/个 面包，5元/个 创建一个名为shopping的函数，打印输出购买不同数量商品的总价。

平方根法解决鸡蛋掉落问题C++代码

使用python将表格milk ，yogurt ，eggs，turkey，tomatto ，milk，yogurt，eggs归纳整理为表格：商品名,数量 milk,2 eggs,2 yogurt,2 turkey,1 tomato,1

如何获取鸡蛋图像集中每一个鸡蛋的子图像，请写出一段代码

现给定一张鸡蛋图片, 根据这张图片从另一张含有很多鸡蛋的图片中将所有鸡蛋标注出来, 给出python代码

p ython蛋糕代码

python ->用法

python山海经（可抽蛋，境界，排行榜)代码

最新资源

妈妈给小明家新送来 y个鸡蛋。已知小明家原有鸡蛋的个数x是满足“3个3个数剩1个，5个5个数剩z个，7个7个数剩3个”的最小数，请问小明家共有多少个鸡蛋?c语言程序

已知：从小卖部售买3种物品，分别是：牛奶，50元/件鸡蛋，2元/个面包，5元/个创建一个名为shopping的函数，打印输出购买不同数量商品的总价。