分治算法求最大值与最小值

用分治法（二分法）可以用较少的比较次数解决上述问题。

问题可简化为如下三个步骤：（1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大和最小值。

（2）递归分解直到每组元素的个数≤2，可简单地找到最大和最小值。

（3）回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为当前问题的解。

递归求取数组a中最大和最小元素的算法如下：maxmin（i, j , fmax, fmin）float A[n];maxmin（i, j, fmax, fmin）//最大和最小元素赋给fmax和fmin{ if (i==j){ fmax = A[i];fmin =A[i];}// 每组元素的个数=1时else if (i==j-1)if (A[i]<A[j]){ fmax ← A[j]；fmin ← A[i]}// 每组元素的个数=2时else{ fmax ← A[i]; fmin ← A[j]; }else{ mid ← (i+j)/2;maxmin(i，mid，lmax，lmin)maxmin(mid+1，j，rmax，rmin）if (lmax > rmax)fmax = lmax;elsefmax = rmax;if (lmin > rmin)fmin = rmin;elsefmin = lmin;}}例2.3.3.2在下述9个元素上模拟递归求最大和最小元素的过程。

数组A[1..9]的各个元素如下:如果用T （n ）表示maxmin 中元素比较次数，则所导出的递归关系式是： 0 n=1=)n (T 1 n=22)2n (T )2n (T +⎥⎥⎤⎢⎢⎡+⎥⎦⎥⎢⎣⎢ n>2 在最坏情况下，递归求最大最小元素比第一种算法要好一些，平均情况下两者差不多。

当n 是2的幂时，即对于某个正整数k ，k 2n =，可以证明，任何以元素比较为基础的找最大和最小元素的算法，其元素比较下界均为22n 3－⎥⎥⎤⎢⎢⎡次。

分治法求最大值最小值a.为一个分治算法编写伪代码，该算法同时求出一个n元数组的最大元素和最小元素的值。

b.假设n=2k,为该算法的键值比较次数建立递推关系式并求解。

c.请拿该算法与解同样问题的蛮力算法做一个比较。

解答：a.同时求出原数组最大值和最小值，先将原数组一分为二，再找出划分的两个部分的最值，然后再合并最值，找划分的两个部分的最值就递归地在这两个部分中用同样的方法找最大值和最小值，然后只需要给出最小规模的确切解法作为递归出口就可以了。

算法MaxMin(A[f…l],Max,Min)//该算法利用分治法求得数组A中的最大值和最小值//输入：数值数组A[f..l]//输出：最大值Max和最小值Minif l−f=0 //只有一个元素时Max←A[f]；Min←A[f];elseif l－f=1 //有两个元素时if A[f]>A[l] //基本操作是作比较Max←A[f] ,Min←A[l]else Max←A[l] ,Min←A[f]else //有大于两个元素时MaxMin(A[f…(f+l2)],Max1,Min1);//递归解决前一部分MaxMin(A[(f+l2)…l],Max2,Min2); //递归解决后一部分Max←max {Max1,Max2};//从两部分的两个最大值中选择大值Min←min {Min1,Min2};//从两部分的两个最小值中选择小值 return Max,Min;b.假设n=2k,比较次数的递推关系式:C(n)=2C(n2)+2 ,n>2C(1)=0, C(2)=1C(n)=C(2k)=2C(2k-1)+2=2[2C(2k-2)+2]+2=22C(2k-2)+22+2=23C(2k-3)+23+22+2...=2k-1C(2)+2k-1+2k-2+...+2 //C(2)=2 =2k-1+2k-1+2k-2+...+2 //等比数列求和=2k-1+2k-2 //2k=n， 2k-1=n2=3n−22b.蛮力法的算法如下：算法ForceMaxMin(A[l..r])//用蛮力法得到数组A的最大值和最小值//输入：数值数组A[l…r]//输出：最大值Max和最小值MinMax=Min=A[l];for i=l+1 to r doif A[i]>Max Max←A[i];else if A[i]<MinMin←A[i]return Max,Minc.作比较ForceMaxMin的时间复杂度T(n)=2n−2算法MaxMin的时间复杂度为3n−2，ForceMaxMin的时间复杂度为2n-2，都属于Θ(n)，2但MaxMin的速度要比ForceMaxMin的稍快一点。

如何找出一组数据中的最大值和最小值数据处理在现代社会中扮演着重要的角色，如何高效地找出一组数据中的最大值和最小值是数据处理中常见的问题。

本文将介绍一些常用的方法，帮助读者轻松找到一组数据中的最大值和最小值。

一、直接遍历法直接遍历法是最直观、简单的一种方法。

具体步骤如下：1. 初始化最大值为数据中的第一个元素，最小值也为数据中的第一个元素。

2. 从数据的第二个元素开始，依次与最大值和最小值进行比较。

3. 如果当前元素大于最大值，则更新最大值；如果当前元素小于最小值，则更新最小值。

4. 继续依次比较下一个元素，直至遍历完成。

5. 最终得到的最大值和最小值即为所求。

直接遍历法虽然简单，但是在数据量较大时效率较低。

下面介绍更高效的方法。

二、分治法分治法是一种常用的高效算法，它将问题分解成若干个子问题，再将子问题的解整合得到最终解。

在找出一组数据中的最大值和最小值时，可以使用分治法来提高效率。

具体步骤如下：1. 将数据分成若干个大小相等的子数组，每个子数组包含相同数量的元素。

2. 对每个子数组分别找出最大值和最小值。

3. 将每个子数组的最大值和最小值与已知的最大值和最小值进行比较，更新最大值和最小值。

4. 继续将每个子数组进一步分割，重复步骤2和步骤3，直至每个子数组只包含一个元素。

5. 最终得到的最大值和最小值即为所求。

分治法通过分解问题，利用子问题的解来推导最终解，能够有效地减少比较次数，提高算法效率。

三、堆排序法堆排序法是一种常用的排序方法，通过构建最大堆和最小堆，可以方便地找到一组数据中的最大值和最小值。

具体步骤如下：1. 构建最大堆，将数据中的元素依次插入堆中。

2. 从堆顶取出最大值，即为所求的最大值。

3. 构建最小堆，将数据中的元素依次插入堆中。

4. 从堆顶取出最小值，即为所求的最小值。

堆排序法通过构建堆的方式，既可以找到最大值，也可以找到最小值，算法效率较高。

综上所述，通过直接遍历法、分治法和堆排序法，我们可以高效地找到一组数据中的最大值和最小值。

分治法寻找数组最⼤的两个数和最⼩的两个数分治法寻找数组最⼤的两个数和最⼩的两个数这个程序实现的结果：假如有两个并列最⼤或并列最⼩数，他们两个是有可能⼀起作为最⼤和次⼤（最⼩和次⼩）。

所以，应该尽量保证没有相同⼤⼩的数据。

但程序对相同的数据不是返回同⼀个下标的数，⽽是不同下标的数据本程序旨在练习分治法，其他的请参看最⼤和最⼩值的求法。

1 #include<stdio.h>2 #include<time.h>3 #include<stdlib.h>4int maxMin2(int *a,int i,int j,int *max1,int *max2,int *min1,int *min2);5int max(int a,int b);6int min(int a,int b);7int main()8 {9int *a;10int i,n;11int max1,max2,min1,min2;1213 scanf("%d",&n);14 a=(int *)malloc(sizeof(int)*n);15 srand((unsigned int)time(0));16for(i=0;i<n;i++) a[i]=rand()%91+10;17for(i=0;i<n;i++)18 {19 printf("%d ",a[i]);20if((i+1)%5==0) printf("\n");21 }22 printf("\n\n");23 maxMin2(a,0,n-1,&max1,&max2,&min1,&min2);24 printf("%d %d\n%d %d\n",max1,max2,min1,min2);/**/25return0;26 }27int maxMin2(int *a,int i,int j,int *max1,int *max2,int *min1,int *min2)28 {29int mid,t;30int lmax1,lmax2,lmin1,lmin2,rmax1,rmax2,rmin1,rmin2;31if(j-i==2)32 {33 *max1=max(a[j],max(a[i],a[i+1]));34 *min1=min(a[j],min(a[i],a[i+1]));35 t=a[i]+a[j]+a[i+1];36 *max2=t-*max1-*min1;37 *min2=*max2;38return0;39 }40else if(j-i==1)41 {42if(a[i]>a[j]){*max1=a[i];*max2=a[j]; *min1=a[j];*min2=a[i];return0;}43else{*max1=a[j];*max2=a[i]; *min1=a[i];*min2=a[j];return0;}44 }45else46 {47 mid=i+(j-i)/2;48 maxMin2(a,i,mid,&lmax1,&lmax2,&lmin1,&lmin2);49 maxMin2(a,mid+1,j,&rmax1,&rmax2,&rmin1,&rmin2);50if(lmax1>rmax1)51 {52 *max1=lmax1;53if(lmax2>rmax1) *max2=lmax2;54else *max2=rmax1;55 }56else57 {58 *max1=rmax1;59if(lmax1>rmax2) *max2=lmax1;60else *max2=rmax2;61 }62if(lmin1<rmin1)63 {64 *min1=lmin1;65if(lmin2<rmin1) *min2=lmin2;66else *min2=rmin1;67 }68else69 {70 *min1=rmin1;71if(lmin1<rmin2) *min2=lmin1;72else *min2=rmin2;73 }74 }75return0;76 }77int max(int a,int b)78 { return a>b?a:b; } 79int min(int a,int b)80 { return a<b?a:b; } View Code。

福建工程学院计算机与信息科学系实验报告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。

分治算法实验（⽤分治法查找数组元素的最⼤值和最⼩值）算法分析与设计实验报告第⼀次实验完整代码（分治法）#include#include#includeusing namespace std;//当数组中的元素个数⼩于3时，处理最⼤值int compmax(int A[],int start,int end){int max;if(start{if(A[start]<=A[end])max=A[end];elsemax=A[start];}else//有⼀个元素max=A[start];return max;}//当数组中元素的个数⼩于2时，处理最⼩值int compmin(int A[],int start,int end){int min;if(start{if(A[start]<=A[end])min=A[start];elsemin=A[end];}else//有⼀个元素min=A[start];return min;}//分治法处理整个数组，求最⼤值与最⼩值void merge(int a[],int left,int right,int &Max,int &Min) //Max,Min⽤来保存最⼤值与最⼩值//之所以使⽤&引⽤，是由于如果只是简单的使⽤变量，并不会改变Max与Min的值，使⽤指针也可以{int max1=0,min1=0,max2=0,min2=0;if(right-left>2) //当数组中元素个数⼤于等于3时，进⾏分治{int mid=(right+left)/2;merge(a,left,mid,max1,min1); //左半边递归调⽤⾃⾝，求出最⼤值最⼩值，分别保存在max1,min1中merge(a,mid+1,right,max2,min2); //右半边递归调⽤⾃⾝，求出最⼤值最⼩值，分别保存在max2,min2中if(max1>=max2) //⼦序列两两合并，求出最⼤值与最⼩值，保存在Max与Min中Max=max1;elseMax=max2;if(min1<=min2)Min=min1;elseMin=min2;}else//数组中元素个数⼩于3时的情况，直接赋值{Max=compmax(a,left,right);Min=compmin(a,left,right);}}void ran(int *input,int n) //随机⽣成数组元素函数{int i;srand(time(0));for(i=0;iinput[i]=rand();input[i]='\0';}int a[1000000]; //定义全局变量⽤来存放要查找的数组int main(){int n;int i;int max;int min;cout<<"请输⼊要查找的序列个数："<for(i=0;i<5;i++){cin>>n;ran(a,n);clock_t start,end,over; //计算程序运⾏时间的算法start=clock();end=clock();over=end-start;start=clock();merge(a,0,n-1,max,min); //调⽤分治法算法cout<end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显⽰运⾏时间}system("pause"); //停⽌运⾏窗⼝return 0;}完整代码（⾮递归⽅法）#include#include#includeusing namespace std;void ran(int *input,int n) //随机⽣成数组元素函数{int i;srand(time(0));for(i=0;iinput[i]=rand();input[i]='\0';}int a[1000000];int main(){int max=a[0],min=a[0];int i,j,n;cout<<"请输⼊数据规模："<for(j=0;j<5;j++){cin>>n;ran(a,n);clock_t start,end,over; //计算程序运⾏时间的算法start=clock();end=clock();over=end-start;start=clock();for(i=1;i{if(a[i]>max)max=a[i];if(a[i]min=a[i];}cout<end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显⽰运⾏时间} system("pause");return 0;}。

实验报告一、实验名称：分治法求最大值和最小值二、实验学时：4三、实验器材和环境：PC机一台四、实验内容和目的：1、实验目的：加深对分治算法原理及实现过程的理解。

2、实验任务：实现用分治算法解决问题。

3、实验内容：给定一个顺序表，编写一个求出其最大值和最小值的分治算法。

分析：由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。

我们知道如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是我们找到求解该问题的子问题即: 数组大小 <= 2。

到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解以下是代码。

五、实验原理：分治算法基本原理，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

大概分为“分治合“策略：分：将要求解的较大规模的问题分割成K个更小规模的子问题；治：对这K个子问题分别求解。

如果子问题的规模仍然不够小则再划分为K个子问题，如此递归的进行下去；划分到基础问题，则设计可行算法直接求解；合：将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。

设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。

再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。

用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：11)()/()1()(>=⎩⎨⎧+=n n n f m n kT O n T通过迭代法求得方程的解：∑-=+=1log0log )/()(n m j jj k m m n f k n n T 六、实验步骤：1、设定参数: s 为当前分治段的开始下标,e 为当前分治段的结束下标,meter 表的地址,max 为存储当前搜索到的最大值,min 为存储当前搜索到的最小值2、获取局部解，并更新全局解，不是子问题的话就继续分治3、用一组随机数据填充数组并以表的形式输出4、用分治法获取最大值和最小值七、实验数据及结果分析：分治算法代码：#include <stdio.h>#include <stdlib.h>#include <limits.h>#include <time.h>#define M 40// 分治法获取最优解void PartionGet(int s,int e,int *meter,int *max,int *min){int i;if(e-s <= 1){// 获取局部解，并更新全局解if(meter[s] > meter[e]){if(meter[s] > *max)*max = meter[s];if(meter[e] < *min)*min = meter[e];}else{if(meter[e] > *max)*max = meter[s];if(meter[s] < *min)*min = meter[s];}return ;}i = s + (e-s)/2; // 不是子问题继续分治PartionGet(s,i,meter,max,min);PartionGet(i+1,e,meter,max,min);}int main(){int i,meter[M];int max = INT_MIN; // 用最小值初始化int min = INT_MAX; // 用最大值初始化printf("The array's element as followed:\n\n"); srand(time(0)); // 初始化随机数发生器for(i = 0; i < M; i ++){ // 随机数据填充数组meter[i] = rand()%10000;if(!((i+1)%10)) // 输出表的随机数据printf("%-6d\n",meter[i]);elseprintf("%-6d",meter[i]);}PartionGet(0,M - 1,meter,&max,&min); // 分治法获取最值printf("\nMax : %d\nMin : %d\n",max,min);system("pause");return 0;}实验结果：。

算法设计与分析报告学生姓名学号专业班级指导教师完成时间目录一、课程内容 (3)二、算法分析 (3)1、分治法 (3)（1)分治法核心思想 (3)（2）MaxMin算法分析 (3)2、动态规划 (4)（1）动态规划核心思想 (4)（2）矩阵连乘算法分析 (5)3、贪心法 (5)(1）贪心法核心思想 (5)（2）背包问题算法分析 (6)（3）装载问题算法分析 (7)4、回溯法 (7)（1）回溯法核心思想 (7)（2)N皇后问题非递归算法分析 (7)(3）N皇后问题递归算法分析 (8)三、例子说明 (9)1、MaxMin问题 (9)2、矩阵连乘 (10)3、背包问题 (10)4、最优装载 (10)5、N皇后问题(非递归） (11)6、N皇后问题(递归) (11)四、心得体会 (12)五、算法对应的例子代码 (12)1、求最大值最小值 (12)2、矩阵连乘问题 (13)3、背包问题 (15)4、装载问题 (17)5、N皇后问题(非递归） (19)6、N皇后问题(递归） (20)一、课程内容1、分治法,求最大值最小值，maxmin算法；2、动态规划，矩阵连乘，求最少连乘次数；3、贪心法，1）背包问题，2）装载问题；4、回溯法，N皇后问题的循环结构算法和递归结构算法。

二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。

如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1<k≤n, 而且子问题与原问题性质相同,原问题的解可由这些子问题的解合并得出。

那末，这类问题可以用分治法求解。

分治法的核心技术1)子问题的划分技术.2）递归技术。

反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生出不用进一步细分就可求解的子问题。

3)合并技术.（2）MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素。

《算法设计与分析》上机实验报告专业班级学号学生姓名完成日期1. 上机题目及实验环境1.1上机题目：1.1.1 用分治法查找数组元素的最大值和最小值1.1.2 众数问题1.2实验环境：CPU：Intel Core i3 2.30GHz内存：2.0G操作系统：Windows 7软件平台：Visual C++2. 算法设计与分析2.1 查找数组最值2.1.1 分治递归方法：●将max和min设置为静态全局变量；●将数据集array平均分为两个数据集；●分别求解两个数据集中的最大和最小值；●最终的最大和最小值通过与max和min的值比较；●采用同样的处理方法递归处理以分好的数据集。

2.1.2 细节处理：●数组的大小为n2，n=0,1,2,3......●数组中的数字随机产生，数字的范围为1~100；●静态全局变量：max的初值为0，min的初值为101。

2.2 众数问题2.2.1 快速排序算法：●设置两个变量i、j，排序开始的时候：i=left，j=right+1；●以第一个数组元素作为关键数据，赋值给temp，即temp=array[left]；●从j开始向前搜索，即由后开始向前搜索(--j)，找到第一个小于temp的值array[j]；●从i开始向后搜索，即由前开始向后搜索(++i)，找到第一个大于temp的array[i]；●交换array[i]和array[j]的值；●重复搜索步骤，直到i=j；●将temp的值和array[j]的值交换，并以此为界，分别在对左右两边进行快速排序。

3. 核心代码3.1 查找最值3.1.1 流程图（如图1）（核心函数为void MaxAndMin(int array[N], int left, int right)）：图1.查找最值的流程图3.1.2 核心代码如下：（注：max和min是静态全局变量）void MaxAndMin(int array[N], int left, int right) // 求最大值最小值函数，分治递归法{int mid; // 数组的分界点if ( (left + 1) == right) // 分治的数组只有两个值时，更新max和min的值{if ( array[left] < array[right] && max < array[right] ) // 判断、更新最大值max = array[right];if ( array[left] > array[right] && max < array[left] )max = array[left];if ( array[left] < array[right] && min > array[left]) // 判断、更新最小值min = array[left];if ( array[left] > array[right] && min > array[right])min = array[right];}else{mid = (left + right) / 2; // 对数组进行分治MaxAndMin(array, left, mid); // 对左边的数组进行分治递归MaxAndMin(array, mid + 1, right); // 对右边的数组进行分治递归}}3.2 众数问题3.2.1 流程图（如图图2.众数问题的流程图3.2.2 核心代码如下：void quickSort(int *array,int left,int right) // 用快速排序法排序数组{if(left < right){int i = left, j = right+1;int temp = array[left]; // 以第一个数为基准while(true){while(array[++i] < temp && i < right); // 从前面找大于基准的数while(array[--j] > temp); // 从后面找小于基准的数if(i >= j) // 当left>right时停止break;swap(array[i], array[j]); // 交换两值}array[left] = array[j];array[j] = temp;int part = j; // 以靠左的较小值为界，对左右两部分数继续快排quickSort(array, left, part-1);quickSort(array, part+1, right);}}4. 运行与调试4.1 查找数组最值产生随机数组并排序：（如图3、图4、图5）图3.随机数组之一及结果图4.随机数组之二及结果图5.随机数组之三及结果4.2 众数问题4.2.1 只有一个众数（如图6、图7）图6.只有一个众数的数组图7.只有一个众数的结果4.2.2 没有众数（如图8、图9）图8.没有众数的数组图9.没有众数的结果4.2.3 有两个众数（如图10、图11）图10.有两个众数的数组图11.有两个众数的结果5. 结果分析和小结5.1 结果分析：通过设置不同的测试数据及运行的结果，可以看出程序的算法思想是正确的，程序的运行也是有效的，全面的。