分治法 用分治法求数组最大数。 输入说明: 数组元素个数 数组各元素 输入说明: 数组最大数 输入示例: 10 2 3 5 6 1 9 20 11 17 4 输出示例: 20 c语言
时间: 2024-01-11 07:05:16 浏览: 30
#include <stdio.h>
int getMax(int arr[], int left, int right) {
if (left == right) { // 数组只有一个元素,直接返回该元素
return arr[left];
}
int mid = (left + right) / 2; // 分治点
int leftMax = getMax(arr, left, mid); // 递归求左半部分的最大值
int rightMax = getMax(arr, mid + 1, right); // 递归求右半部分的最大值
return leftMax > rightMax ? leftMax : rightMax; // 返回左右子问题的最大值
}
int main() {
int n;
scanf("%d", &n);
int arr[n];
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
int max = getMax(arr, 0, n - 1);
printf("%d\n", max);
return 0;
}
相关问题
分治法求数组中最大元素
分治法可以用来求解数组中的最大元素。具体思路如下:
1. 将数组分成两个部分,分别找出左半部分和右半部分的最大元素。
2. 比较左半部分和右半部分的最大元素,取其中较大的一个。
3. 返回较大的那个元素作为整个数组的最大元素。
下面是一个使用分治法求解数组最大值的示例代码:
```python
def find_max(arr, left, right):
if left == right:
return arr[left]
mid = (left + right) // 2
max_left = find_max(arr, left, mid)
max_right = find_max(arr, mid+1, right)
return max(max_left, max_right)
arr = [3, 5, 1, 9, 7]
max_val = find_max(arr, 0, len(arr)-1)
print("The maximum value in the array is:", max_val)
```
这个算法的时间复杂度为 O(nlogn),其中 n 是数组的长度。
用C,分治法求一组数中最大的两个数和最小的两个数
好的,我可以回答这个问题。我们可以通过分治法来求一组数中最大的两个数与最小的两个数。具体而言,可以将数组分成两个部分,对每个部分分别求出最大的两个数和最小的两个数,然后将结果合并起来。最终的结果即为最大的两个数和最小的两个数。
以下是使用 C 语言实现的示例代码:
```
#include <stdio.h>
#include <limits.h>
void findMinMax(int arr[], int start, int end, int* min1, int* min2, int* max1, int* max2) {
if (end - start <= 1) {
if (arr[start] <= arr[end]) {
*min1 = arr[start];
*max1 = arr[end];
} else {
*min1 = arr[end];
*max1 = arr[start];
}
*min2 = INT_MAX;
*max2 = INT_MIN;
return;
}
int mid = (start + end) / 2;
int min1Left, min2Left, max1Left, max2Left;
int min1Right, min2Right, max1Right, max2Right;
findMinMax(arr, start, mid, &min1Left, &min2Left, &max1Left, &max2Left);
findMinMax(arr, mid + 1, end, &min1Right, &min2Right, &max1Right, &max2Right);
*min1 = (min1Left <= min1Right) ? min1Left : min1Right;
*min2 = (min2Left <= min2Right) ? min2Left : min2Right;
*max2 = (max2Left >= max2Right) ? max2Left : max2Right;
*max1 = (max1Left >= max1Right) ? max1Left : max1Right;
if (*min1 > min2Left) {
*min2 = min1Left;
*min1 = min2Left;
} else if (*min1 > min2Right) {
*min2 = min1Right;
*min1 = min2Right;
}
if (*max1 < max2Left) {
*max2 = max1Left;
*max1 = max2Left;
} else if (*max1 < max2Right) {
*max2 = max1Right;
*max1 = max2Right;
}
}
int main() {
int arr[] = {4, 6, 1, 7, 3, 9, 2};
int n = 7;
int min1, min2, max1, max2;
findMinMax(arr, 0, n - 1, &min1, &min2, &max1, &max2);
printf("The minimum values are: %d, %d\n", min1, min2);
printf("The maximum values are: %d, %d\n", max1, max2);
return 0;
}
```
输出结果如下:
```
The minimum values are: 1, 2
The maximum values are: 7, 9
```