1 实验报告 2010 – 2011 学年第 2 学期 任课老师： 课程名称 分治算法设计技术的应用 班级 座号 实验题目 1．设计程序利用分治策略求 n个数的最大值和最小值。 2．利用分治策略，在 n个不同元素中找出第 k个最小元素。 实验时间 实验目的、要求 实验目的：了解分治算法思想，并用分治算法实现函数调用 实验要求：1．该实验的课内学时是 4个课时。 2．题目 1必须完成。 3．题目 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。用分治策略比较的过程如下： 2 图中每个方框中，左边是最小值，右边是最大值。从图中看出，用这种方法一共比较了 10次，比直接比较法的 14次减少 4次，即约减少了 1/3。算法如下： 主要数据结构： 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之间的最大最小值分别为 max2，min2; 比较 max1和 max2，大的就是最大值; 比较 min1和 min2，小的就是最小值; } 实验二主要算法 把 n个元素放在顺序表中，然后取第 k个元素作为标准 m，把 n个元素重新排列，分成两个区间：小于标准 m的元素区间 1~j，大于标准 m的元素区间 j+...
