black

离散数学

登录

问答题

共用题干题设A是n(n〉1)个不等的正整数构成的集合,其中n=2k,k为正整数。考虑下述在A中找最大和最小的算法MaxMin:如果A中只有2个数,那么比较1次就可以确定最大数与最小数。否则,将A划分成相等的两个子集A1和A2,用算法MaxMin递归地在A1与A2中找最大与最小。令a1,a2分别表示A1与A2中的最大数,b1与b2分别表示A1与A2中的最小数,那么max(a1a2)与min(b1,b2)就是所需要的结果。

对于规模为n的输入,计算算法MaxMin最坏情况下所做的比较次数。

【参考答案】

相关考题

问答题 一手扑克牌有5张,满足条件包含一个顺子,即5张牌的牌点是连续的概率是多少?

问答题 (1)证明:当z=k+1时,这样的三元序组的个数恰为k2个(1≤k≤n)

问答题 判断下题是哪一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。 S5={0,1},*为模2加法,Ο为模2乘法。

All Rights Reserved 版权所有©易学考试网(yxkao.com)

备案号:湘ICP备2022003000号-3