题目内容
(请给出正确答案)
[主观题]
教材2.6节针对有序向量介绍的各种查找算法,落实减而治之策略的形式均大同小异,反复地“猜测”某
一元素S[mi],并通过将目标元素与之比较的结果,确定查找范围收缩的方向,然而在某些特殊的场合,沿前、后两个方向深入的代价并不对称,甚至其中之一只允许常数次。
比如,在仅能使用直尺的情况下,可通过反复实验,用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变,但毕竟破裂是不可逆的。故若仅有一枚鸡蛋,则我们不得不从0开始,以1毫米为单位逐步增加下落的高度,若蛋壳的硬度不超过n毫米,则需要进行o(n)次实验。就效率而言,这等价于退化到无序向量的顺序查找。
a)若你拥有两枚鸡蛋(假定它们硬度完全相同),所需实验可减少到多少次?试给出对应的算法;
b)进一步地,如果你拥有三枚鸡蛋呢?
c)一般地,如果共有d枚鸡蛋可用呢?
查看答案
如果结果不匹配,请 联系老师 获取答案