首页 > 建筑工程
题目内容 (请给出正确答案)
[主观题]

教材2.6节针对有序向量介绍的各种查找算法,落实减而治之策略的形式均大同小异,反复地“猜测”某

一元素S[mi],并通过将目标元素与之比较的结果,确定查找范围收缩的方向,然而在某些特殊的场合,沿前、后两个方向深入的代价并不对称,甚至其中之一只允许常数次。

比如,在仅能使用直尺的情况下,可通过反复实验,用鸡蛋刚能摔碎的下落高度(比如精确到毫米)来度量蛋壳的硬度。尽管可以假定在破裂之前蛋壳的硬度保持不变,但毕竟破裂是不可逆的。故若仅有一枚鸡蛋,则我们不得不从0开始,以1毫米为单位逐步增加下落的高度,若蛋壳的硬度不超过n毫米,则需要进行o(n)次实验。就效率而言,这等价于退化到无序向量的顺序查找。

a)若你拥有两枚鸡蛋(假定它们硬度完全相同),所需实验可减少到多少次?试给出对应的算法;

b)进一步地,如果你拥有三枚鸡蛋呢?

c)一般地,如果共有d枚鸡蛋可用呢?

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“教材2.6节针对有序向量介绍的各种查找算法,落实减而治之策略…”相关的问题
第1题
考查教材39页代码2.10中的无序向量查找算法find(e,lo,hi)。a)在最好情况下,该算法需要运行多少时间?为什么?b)若仅考查成功的查找,则平均需要运行多少时间?为什么?

点击查看答案
第2题
若输入的有序序列S1和S2以列表(而非向量)的方式实现,则:a)如教材344页代码12.8和346页代码12.9所示的两个median()算法,分别应做哪些调整?b)调整之后的计算效率如何?

点击查看答案
第3题
a)仿照教材81页代码3.20,试针对向量结构实现选择排序算法Vector::selectionSort();b)你实现的选择排序算法是稳定的吗?为什么?

点击查看答案
第4题
如教材346页代码12.9所示的median()算法针对两个向量长度相差悬殊的情况做了优化处理。a)试分析该方法的原理,并证明其正确性;b)试证明,复杂度的精确上界应为o(log(min(n1,n2)))。

点击查看答案
第5题
设使用Pratt序列:对长度为n的任一向量S做希尔排序。试证明:a)若S已是(2,3)-有序,则只需o(n)时间

设使用Pratt序列:

对长度为n的任一向量S做希尔排序。

试证明:

a)若S已是(2,3)-有序,则只需o(n)时间即可使之完全有序;

b)对任何,若S已是(2hk,3hk)-有序,则只需o(n)时间即可使之hk-有序;

c)针对序列中的前o(logtn)项,希尔排序算法需要分别迭代一轮;

d)总体的时间复杂度为o(log2n)。

点击查看答案
第6题
无预订重在查找订房记录,核对预订信息,而有预订则应检查有无空房,如有空房,则重在有针对性地向客人介绍、推销客房,如无空房则应婉拒客人,或为客人介绍其他酒店。()
点击查看答案
第7题
促销人员通过与消费者交流,有效地向消费者宣传商品运用各种销售技巧进行沟通,有针对性地介绍商品,帮助顾客作出正确选择()
点击查看答案
第8题
在模式枚举(pattern enumeration)类应用中,需要从主串T中找出所有的模式串P(T|=n,|P|=m),而且

在模式枚举(pattern enumeration)类应用中,需要从主串T中找出所有的模式串P(T|=n,|P|=m),而且有时允许模式串的两次出现位置之间相距不足m个字符。

类似于教材310页图11.3中的实例,比如在“000000”中查找“000”。若限制多次出现的模式串之间至少相距|P|=3个字符,则应找到2处匹配;反之,若不作限制,则将找到4处匹配。

a)试举例说明,若采用后一约定,则教材11.4.3节BM算法的好后缀策略,可能需要Ω(nm)时间;

b)试针对这一缺陷改进好后缀策略,使之即便在采用后一约定时,最坏情况下也只需线性时间。

点击查看答案
第9题
试证明,g-有序的向量再经h-排序之后,依然保持g-有序。

点击查看答案
第10题
对于两台及以上接收机同步观测值进行独立基线向量的平差计算,叫做基线解算。()
点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改