分治法求最大最小

63 阅读 0 评论 42 点赞

我是靠谱客的博主能干战斗机，最近开发中收集的这篇文章主要介绍分治法求最大最小，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

　　分治法的基本思想：是将一个规模为n的原问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将子问题的解合并为原问题的解。

 1 #include<stdio.h>
 2 /* 分治法计算最大值和最小值的算法程序，递归实现 */
 3 void maxmin2(int d[], int left, int right, int *max, int *min) //数组，头，尾，最大值，最小值 
 4 {
 5
int max1, min1;
 6
//递归最小时处理 
 7
if(left==right) {
//如果只有一个数 即使最大也是最小 
 8
*max = d[left];
 9
*min = d[left];
10
} else if(left == right-1) {
//两个数，判断大小 
11
if(d[left] > d[right]){
12
*max = d[left];
13
*min = d[right];
14
} else {
15
*max = d[right];
16
*min = d[left];
17 
}
18
} else {
19
int mid = (left + right) / 2;
//二分 
20
maxmin2(d, left, mid, &max1, &min1);
//处理左端 
21
maxmin2(d, mid+1, right, &max1, &min1);
//处理右端

22
if(*max < max1)
// 先分后治 
23
*max = max1;
24
if(*min > min1)
25
*min = min1;
26 
}
27 }
28
29 int main()
30 {
31
int d[10] = {0,1,2,3,4,5,6,7,8,9};
32
int max,min;
33
maxmin2(d,0,9,&max,&min);
34
printf("%d %d",max,min);
35 }