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

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

"两个蛋的问题（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

基于springboot+vue的体育馆管理系统的设计与实现（Java毕业设计，附源码，部署教程）.zip

二叉树的创建，打印，交换左右子树，层次遍历，先中后遍历，计算树的高度和叶子节点个数

鸿蒙操作系统接入智能卡读写器SDK范例

【天线】基于matlab时域差分FDTD方法喇叭天线仿真（绘制电场方向图）【含Matlab源码 9703期】.zip

QT 下拉菜单设置参数 起始端口和结束端口

基于springboot+vue的大学生就业招聘系统的设计与实现（Java毕业设计，附源码，部署教程）.zip

java学生学籍管理系统设计与实现(源代码+论文+开题报告+外文翻译+答辩PPT)

最新资源

QT 下拉菜单设置参数起始端口和结束端口