用分治算法求一组数中的最大值、最小值问题一、求一个最大值、最小值二、求两个最大值、两个最小值

62 阅读 0 评论 41 点赞

我是靠谱客的博主玩命鲜花，这篇文章主要介绍用分治算法求一组数中的最大值、最小值问题一、求一个最大值、最小值二、求两个最大值、两个最小值，现在分享给大家，希望可以做个参考。

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

1.解题思路

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

2.算法的伪代码描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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.算法的伪代码描述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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;
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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;
}
}
}