6-2 分治法求解金块问题

description

老板有一袋金块（共n块，2≤n≤100），两名最优秀的雇员每人可以得到其中的一块，排名第一的得到最重的金块，排名第二的则得到袋子中最轻的金块。

输入一个正整数N（2≤N≤100）和N个整数，用分治法求出最重金块和最轻金块。

本题要求实现2个函数，分别使用分治法在数组中找出最大值、最小值。

函数接口定义：
int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);
递归函数max用分治法求出a[m]~a[n]中的最大值并返回。

递归函数min用分治法求出a[m]~a[n]中的最小值并返回。

裁判测试程序样例：
#include
#define MAXN 101

int max(int a[ ], int m, int n);
int min(int a[ ], int m, int n);

int main(void)
{
int i, n;
int a[MAXN];

scanf ("%d", &n); 
if(n >= 2 && n <= MAXN-1 ){
    for(i = 0; i < n; i++){ 
        scanf ("%d", &a[i]); 
    }
    printf("max = %d\n", max(a, 0, n-1));
    printf("min = %d\n", min(a, 0, n-1));
}else{
    printf("Invalid Value.\n");    
}

return 0;
1
2
3
4
5
6
7
8
9
10
11
12

}

/* 请在这里填写答案 */

输入样例：

6
3 9 4 9 2 4

输出样例：

max = 9
min = 2

solution

/* 请在这里填写答案 */
int max(int a[ ], int m, int n){
	if(m == n) return a[m];
	else{
		int mid = (m + n) / 2;
		int lMax = max(a, m, mid);
		int rMax = max(a, mid + 1, n);
		if(lMax > rMax) return lMax;
		else return rMax;
	}
}
int min(int a[ ], int m, int n){
	if(m == n) return a[m];
	else{
		int mid = (m + n) / 2;
		int lMin = min(a, m, mid);
		int rMin = min(a, mid + 1, n);
		if(lMin < rMin) return lMin;
		else return rMin;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21