实验报告
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。用分治策略比较的过程如下：
1
图中每个方框中，左边是最小值，右边是最大值。从图中看出，用这种方法一共比较了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+1~n，接下来有三种情况： 1）j=k，则找到第k个元素。 2）j 2 3）j>k，则第k个元素在区间1~j。 在情况2和3中继续寻找 试验过程记录 在实验一中程序调试成功，但是输入结果却不是预期的，出现了不可知的结果，就是输出的结果中不是我输入的，后面详细的检查了程序，在函数调用中maxmin2( A, mid+1, j,&max2,&min2)，中加上取地址符就正确了。 在实验二程序调试成功，但是不是我的预期效果，后经多次调试程序，在 if(i>k) { if(a[i]