给定一个含n个整数顺序存储的线性表,按分治法思路,采用二分策略,设计一个求出其最大值和最小值算法,编写相应测试程序。要求使用分治法设计出其中求最大值、最小值组合的递归算法。
时间: 2024-05-13 22:21:05 浏览: 100
算法设计:
1. 将线性表按照二分策略分成两个子序列。
2. 分别递归求出子序列的最大值和最小值。
3. 将子序列的最大值和最小值分别与当前最大值和最小值比较,更新最大值和最小值。
4. 返回最大值和最小值。
代码实现:
```
#include <iostream>
using namespace std;
void max_min(int a[], int low, int high, int& max, int& min) {
if (low == high) { // 只有一个元素
max = a[low];
min = a[low];
} else if (low == high - 1) { // 两个元素
max = a[low] > a[high] ? a[low] : a[high];
min = a[low] < a[high] ? a[low] : a[high];
} else { // 多于两个元素
int mid = (low + high) / 2;
int max1, min1, max2, min2;
max_min(a, low, mid, max1, min1); // 递归求左半部分的最大值和最小值
max_min(a, mid + 1, high, max2, min2); // 递归求右半部分的最大值和最小值
max = max1 > max2 ? max1 : max2;
min = min1 < min2 ? min1 : min2;
}
}
int main() {
int a[] = {3, 1, 4, 2, 6, 5};
int max, min;
max_min(a, 0, 5, max, min);
cout << "max: " << max << endl;
cout << "min: " << min << endl;
return 0;
}
```
测试结果:
```
max: 6
min: 1
```
阅读全文
相关推荐














