2. 考研
  3. 对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?

admin2017-11-14  83
问题 对一个由n个关键字不同的记录构成的序列，能否用比2n一3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?
选项
答案将n个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较……比较中的小者放前半部，大者放后半部，用了n／2次比较。再在前后两部分中分别简单选择最小和最大元素，各用(n／2)一1次比较。总共用了(3n／2)一2次比较。显然，当n≥3时，(2n一3)＞(3n／2)一2。 用分治法求解再给出另一参考答案。 对于两个数x和y，经一次比较可得到最大值和最小值；对于三个数x，y，z，最多经3次比较可得最大值和最小值；对于n个数(n＞3)，将分成长为n一2和2的前后两部分A和B，分别找出最大者和最小者：Max A，Min A，Max B，Min B，最后Max={MaxA，Max B}和Min={Min A，MinB}。对A使用同样的方法求出最大值和最小值，直到元素个数不超过3。 设C(n)是所需的最多比较次数，根据上述原则，当n＞3时有如下关系式： [*] 通过逐步递推，可以得到：C(n)=(3n／2)一2。显然，当n＞3时，2n一3＞(3n／2)一2。事实上(3n／2)一2是解决这一问题的比较次数的下限。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/P3Ri777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)