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 之间的最大...