最大元最小元算法.doc

分治算法实现分治算法实现姓名：赵成兵学号：20062353班级：软件工程2班1问题描述 从多个数中一次性查找出元素最大的值和最小值，查找元素规模即元素的个数n,用分治的思想编制程序，实现分治的最大元和最小元求法。进一步改进算法，使之能一次性求出最大和和次大元（即第二大元素）。2算法设计思想及描述分治发的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立与原问题相同。递归地解决这些问题，然后将各个子问题的解合并得到原问题的解。基于课堂的分析知道，对于本问题k的值取为2，这样可以使子问题的规模是相同的，有利于算法实现。为平衡分治时子问题的规模，这里约定需要查找元素的规模n是2的幂次方。用数组存储需要查找的元素，用结构体存储返回的最大元和最小元。元素规模事先给定，按照上面的约定，分割问题，直到子问题都只有两个元素的时候，这时通过比较这两个元素的大小，确定这两个元素的大小关系，归并到上一层时，4个元素中两个局部最大元又相互比较，两个局部最小元相互比较，得到新的局部最大元和局部最小元，层层归并，最后得到结果。进一步地，有了上面的分析，可能想到可以每次按照求最大元和最小元的思想，每次得到局部的最大元和局部次大元，然后局部最大元和最大元比较得到新的局部最大元，次大元和次大元比较得到新的局部次大元。深入分析，这种方式局部次大元是错误的。如两组元素中，a1b1,a2b2,当然a1和a2中较大的是新的局部最大元，但是b1和b2中较大的元素不是这四个元素中第二大的。这样的方法漏掉了b1可能是次大元的情况，也就是说所有的元素中的次大元可能在与最大元比较的时候被漏掉了。弥补的方法就是每次将每个元素比自身小的元素都用一个淘汰数组保存起来，最后次大元就是最大元的淘汰数组中第二大的那个元素。说明：淘汰数组是一个二维的，每行存储的第一个元素是自己本身，本行后面的就是每次比这个元素小的，因为事先最大元并不确定，所以每个元素都有一行用于存放被自己淘汰的元素，如果没有比它小的，后面元素为空。3算法分析求最大元和最小元，最大元和次大元的算法比较多，运用分治算法解决此问题，是因为这种方法的优越行，下面通过时间复杂度的比较来说明。通常算法，设置一个变量，等于需要比较的数组的第一个元素，然后依次与后面的n-1经行比较，需要比较n-1次得到最大元。同理，求得最小元的比较次数仍然是n-1次。设表示比较的次数则对于这种算法得到的值为分治算法求最大元比较解方程结果为,虽然二者都是线性增长的，可是增长率要小一些。实际编程时的实现有细微差距。另外，求最大元，次大元的时候次大元总是在最大元的淘汰数组中，所以求次大元时，多了从最大元数组中找次大元的情形，n取对数，增长率仍然是比较小的。最大最小元代码#include stdio.hstruct pointint max;/the larger oneint min;/the smaller one;int array50;int Max(int i,int j) if(i=j) return i; else return j;int Min(int i,int j)if(i=j)return j;else return i;struct point fun1(int offset,int end,int n)/传入参数为查找下限，上限，注意上限下标不在查找范围内struct point temp, temp1,temp2;if(n=2) temp.max=Max(arrayoffset,arrayend-1);temp.min=Min(arrayoffset,arrayend-1);return temp;elsetemp1=fun1(offset,(offset+end)/2,n/2);/每次规模减半temp2=fun1(offset+end)/2,end,n/2); temp.max=Max(temp1.max,temp2.max);temp.min=Min(temp1.min,temp2.min);return temp;void main() struct point a1,a2;int i,n;for(i=0;i50;i+) arrayi=0;printf(Input the total n=:n);scanf(%d,&n);printf(Input the numbers:n);for(i=0;i=j)return i;else return j;int fun2(int offset,int end,int n)/返回了最大元素的所在数组的下标，通过下标引用最大元int temp1,temp2;if(n=2) if(indexoffset=0) tempoffsetindexoffset=arrayoffset;indexoffset+; if(indexend-1=0)tempend-1indexend-1=arrayend-1;/元素本身被保存在该行的第一个位置indexend-1+; if(arrayoffset=arrayend-1) tempoffsetindexoffset=arrayend-1;/较小的元素保存到淘汰数组中indexoffset+;return offset;else tempend-1indexend-1=arrayoffset;indexend-1+; return end-1;elsetemp1=fun2(offset,(offset+end)/2,n/2);/递归调用，temp2=fun2(offset+end)/2,end,n/2);if(arraytemp1=arraytemp2)temptemp1indextemp1=arraytemp2;return temp1;elsetemptemp2indextemp2=arraytemp1;indextemp2+;return temp2;void main() struct point a1;int n,i,j,secondmax=-1,aa;/次大元开始被赋值为-1，因为所有的元素都为正数的缘故printf(Input the n=:n);scanf(%d,&n);for(i=0;i50;i+)arrayi=0;indexi=0;/suoyin xiabiao kaishi chu jun wei 0printf(Input the numbers:n);for(i=0;in;i+)scanf(%d,&arrayi); aa=fun2(0,n,n);a1.max=arrayaa;for(j=1;j=25;j+)if(secondmaxtempaaj)/aa即是最大元所在的行下标secondmax=tempaaj;a1.secondmax=secondmax;printf(Max=%dnSecondMax=%d,a1.max,a1.secondmax);4.运行环境Windows XP系统，