分治算法设计(求第K个最小数)VIP免费

1 福建工程学院计算机与信息科学系 实验报告 2010 – 2011 学年第 一 学期 任课老师： 实验题目 1．设计程序利用分治策略求 n 个数的最大值和最小值。 2．利用分治策略，在 n 个不同元素中找出第 k 个最小元素。 实验时间 实验开始日期： 报告提交日期： 实验目的、要求 一、算法设计技术 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。下面通过实例加以说明。 【例】在 n 个元素中找出最大元素和最小元素。我们可以把这 n 个元素放在一个数组中，用直接比较法求出。算法如下： void maxmin1(int A[],int n,int *max,int *min) { int i; *min=*max=A[0]; for(i=2;i < n;i++) { if(A[i] > *max) *max= A[i]; if(A[i] < *min) *min= A[i]; } } 上面这个算法需比较 2(n-1)次。能否找到更好的算法呢？我们用分治策略来讨论。 把 n 个元素分成两组： A1={A[1],...,A[int(n/2)]}和 A2={A[int(N/2)+1],...,A[N]} 分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全 部 元素的最大值和最小值。如果 A1 和 A2 中的元素多于两个，则 再用上述 方法各 分为两个子集 。直至子集 中元素至多两个元素为止。 例如有 下面一组元素：-13，13，9，-5，7，23，0，15。用分治策略比较的过程如下： 图 中每 个方框 中，左 边 是最小值，右 边 是最大值。从 图 中看 出，用这种 方法一共 比较了 10 次，比直接比较法的 14 次减 少 4 次，即 约 减 少 了 1/3。算法如下： 2 void maxmin2(int A[],int i,int j,int *max,int *min) /*A 存放输入的数据，i，j 存放数据的范围，初值为0，n-1，*max,int *min 存放最大和最小值*/ { int mid,max1,max2,min1,min2; if (j==i) {最大和最小值为同一个数;return;} if (j-1==i) {将两个数直接比较，求得最大会最小值；return；} mid=(i+j)/2; 求i~mid 之间的最大最小值分别为max1，min1; 求mid+1~j 之间的最大...