采用分治法求一个整数序列中的最大和最小元素

问题描述

设计一个算法，采用分治法求一个包含n个整数的序列中的最大和最小元素。

【输入形式】

第一行为序列中元素的个数n；第二行为n个整数，每个整数以空格隔开。

【输出形式】

n个整数中的最大和最小元素，中间用一个空格隔开。

【样例输入1】

5

4 3 1 2 5

【样例输出1】

5 1

【样例说明1】

5个数{ 4 3 1 2 5 }的最大值为5，最小值为1

【样例输入2】

10

54 13 10 32 15 56 72 35 67 22

【样例输出2】

72 10

【样例说明2】

10个数{ 54 13 10 32 15 56 72 35 67 22 }的最大值为72，最小值为10

C++代码

#include <iostream>
using namespace std;
void FindM(int a[],int low, int high, int &Max, int &Min){
	int Lmax,Lmin,Rmax,Rmin,mid;
	Lmax=Lmin=Rmax=Rmin=mid=0;
	if(high-low>1){
		mid = (high+low)/2;
		FindM(a,low,mid,Lmax,Lmin);
		FindM(a,mid+1,high,Rmax,Rmin);
		if(Lmax>Rmax){
			Max=Lmax;
		}else{
			Max=Rmax;
		}
		if(Lmin<Rmin){
			Min=Lmin;
		}else{
			Min=Rmin;
		}
	}else if(high-low==1){
		if(a[low]<a[high]){
			Max=a[high];
			Min=a[low];
		}else{
			Min=a[high];
			Max=a[low];
		}
	}else{
		Max=Min=a[low]; 
	}
}
int main(){
	int n;
	int a[5000];
	int Max=0;
    int Min=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	FindM(a,0,n-1,Max,Min);
	printf("%d %d",Max,Min);
}

最后

以上就是傲娇红牛为你收集整理的采用分治法求一个整数序列中的最大和最小元素的全部内容，希望文章能够帮你解决采用分治法求一个整数序列中的最大和最小元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。