一、求一个最大值、最小值

1.解题思路

(1)将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。
(2)递归分解直到每组元素的个数≤2，可简单地找到最大（小）值。 (3)回溯时，在分解的两组解中大者取大，小者取小，合并为当前问题的解。

2.算法的伪代码描述

float a[n];
maxmin (int
i, int j ,float &fmax, float &fmin)
{ int mid;
float lmax, lmin, rmax, rmin;
if (i=j)
{fmax= a[i];
fmin=a[i];}
else if (i=j-1)
if(a[i]<a[j])
{ fmax=a[j]；fmin=a[i];}
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;
else
fmax=rmax;
if (lmin>rmin)
fmin=rmin;
else
fmin=lmin;}
}

二、求两个最大值、两个最小值

1.解题思路

(1)将数据等分为两组（如果数的个数为奇数的话，两组数的个数会差1），分别求这两组数中的两个最大值和两个最小值
(2)递归分解直到每组数的元素<=4,才可以简单的找出最大值和最小值 (3)最后在两组之中进行比较，大的取大，小的取小，再进行解得合并
(4)递归的出口是：当只有一个数时，四个值都相等
（注意）：这四个数的大小关系为 min1<min2<max2<max1

2.算法的伪代码描述

maxmin(a,m,n,min1,min2,max1,max2)
{
if m==n then
{
min1= min2= max1= max2=a[m];}
else
if m==n-1 then {
if a[m]<a[n]
then
{min1=a[m];min2=a[n];max1=a[n];max2=a[m];}
else
{min1=a[n];min2=a[m];max1=a[m];max2=a[n];}}
else
{
mid=(m+n)/2;
maxmin(a,m,mid,&lmin1,&lmin2,&lmax1,&lmax2);
maxmin(a,mid+1,n,&rmin1,&rmin2,&rmax1,&rmax2);
if lmin1<rmin1 then
{
if lmin2<rmin1 then
{min1=lmin1;min2=lmin2;}
else
{min1=lmin1;min2=rmin1; }
}
else
{
if rmin2<lmin1
then {min1=rmin1;min2=rmin2; }
else {min1=rmin1;min2=lmin1;}
}
if lmax1>rmax1 then
{
if lmax2>rmax1 then {max1=lmax1;max2=lmax2;}
else {max1=lmax1;max2=rmax1;}
}
else
{
if rmax2>lmax1 then {max1=rmax1;max2=rmax2;}
else {max1=rmax1;max2=lmax1;}
}
}

3.源程序

#include<stdio.h>
#define N 5
void maxmin(int *a,int m,int n,int *min1,int *min2,int *max1,int *max2);
int main()
{
int a[N];
int min1,min2,i,max1,max2;
printf("输入N个数（在头文件自己定义N的大小）:");
for(i=0;i<N;i++)
{
scanf("%d",&a[i]);
}
maxmin(a,0,N-1,&min1,&min2,&max1,&max2);
printf("min1=%d min2=%d max1=%d max2=%dn",min1,min2,max1,max2);
return 0;
}
void maxmin(int *a,int m,int n,int *min1,int *min2,int *max1,int *max2)
{
int lmin1,lmin2,lmax1,lmax2;
int rmin1,rmin2,rmax1,rmax2;
int mid;
if(m==n)
{
*min1=*min2=*max1=*max2=a[m];
}
else
if(m==n-1)
{
if(a[m]<a[n])
{
*min1=a[m];
*min2=a[n];
*max1=a[n];
*max2=a[m];
}
else
{
*min1=a[n];
*min2=a[m];
*max1=a[m];
*max2=a[n];
}
}
else
{
mid=(m+n)/2;
maxmin(a,m,mid,&lmin1,&lmin2,&lmax1,&lmax2);
maxmin(a,mid+1,n,&rmin1,&rmin2,&rmax1,&rmax2);
if(lmin1<rmin1)
{
if(lmin2<rmin1)
{
*min1=lmin1;
*min2=lmin2;
}
else
{
*min1=lmin1;
*min2=rmin1;
}
}
else
if(rmin2<lmin1)
{
*min1=rmin1;
*min2=rmin2;
}
else
{
*min1=rmin1;
*min2=lmin1;
}
if(lmax1>rmax1)
{
if(lmax2>rmax1)
{
*max1=lmax1;
*max2=lmax2;
}
else
{
*max1=lmax1;
*max2=rmax1;
}
}
else
if(rmax2>lmax1)
{
*max1=rmax1;
*max2=rmax2;
}
else
{
*max1=rmax1;
*max2=lmax1;
}
}
}

最后

以上就是玩命鲜花为你收集整理的用分治算法求一组数中的最大值、最小值问题一、求一个最大值、最小值二、求两个最大值、两个最小值的全部内容，希望文章能够帮你解决用分治算法求一组数中的最大值、最小值问题一、求一个最大值、最小值二、求两个最大值、两个最小值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。