2. 考研
  3. 一个长度为L(L≥1)的升序序列S，处在第个位置的数称为s的中位数。例如，若序列S1=(11，13，15，17，19)，则Sl的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则Sl和S2的中位数是

一个长度为L(L≥1)的升序序列S，处在第个位置的数称为s的中位数。例如，若序列S1=(11，13，15，17，19)，则Sl的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则Sl和S2的中位数是

admin2015-12-30  67
问题 一个长度为L(L≥1)的升序序列S，处在第个位置的数称为s的中位数。例如，若序列S1=(11，13，15，17，19)，则Sl的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则Sl和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
要求：
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
选项
答案算法的实现如下： int M Search(int A[]，intB[]，int n){ int s1=0，d1=n-1，m1，s2=1，d2=n-1，m2， ／／分别表示序列A和B的首位数、末位数和中位数 while(s1!=d1｜｜s2！=d2)( m1=(S1+d1)／2， m2=(s2+d2)／2； if(A[m1]；==B[m2]) return A[m1]，／／满足条件1) if(A[m1]＜B[m2]){／／满足条件2) if((s1+d1)％2==0){／／若元素个数为奇数 s1=m1；／／舍弃A中间点以前的部分，且保留中间点 d2=m2；／／舍弃B中间点以后的部分，且保留巾间点 } else f／／元素个数为偶数 s1=m1+1；／／舍弃A中间点及中间点以前部分 d2=m2；／／舍弃B中间点以后部分且保留中间点 } } elsef／／满足条件3) if((sl+d1)％2==0){／／若元素个数为奇数 d1=m1，／／舍弃A中间点以后的部分，且保留中间点 s2=m2；／／舍弃B中间点以前的部分，且保留中间点 } else{／／元素个数为偶数 d1=m1；／／舍弃A中问点以后部分，且保留中间点 s2=m2+1；／／舍弃B中间点及中间点以前部分 } } } return A[s1]＜B[s2]?A[s1]：B[s2]， }
解析
转载请注明原文地址:https://www.kaotiyun.com/show/sBRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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