分治法查找最大值最小值实验

程序员文章站 2022-05-12 15:20:52

...

1.问题描述：输入一组数据，找出其中的最大值最小值

2.分治思想：

找数组a范围l~R的最值：

①范围一分为2 mid=(l+r)/2

②最大值=max(l~mid最大值，mid+1~r最大值)；

③最小值=min(l~mid最小值，mid+1~r最小值)；

边界：

只有一个元素，最大值=最小值=a[l]

3.代码实现:

#include <iostream>
#include <fstream>
#include <windows.h>
using namespace std;
void search(int *a, int l,int r, int &maxi,int &mini){
	if(l==r){
		maxi=mini=a[l];return;
	}
	int mid=(l+r)/2;
	int max1,max2,min1,min2;
	search(a,l,mid,max1,min1);
	search(a,mid+1,r,max2,min2);
	maxi=max(max1,max2);
	mini=min(min1,min2);
} 
int main(){
	int n,i,maxi,mini;
	LARGE_INTEGER nFreq,nBegin,nEnd;
	double time; 
	
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>n;
	int a[n];
	for(i=0;i<n;i++)
		in>>a[i];
	
	QueryPerformanceFrequency(&nFreq);	
	QueryPerformanceCounter(&nBegin);
	search(a,0,n-1,maxi,mini);
	QueryPerformanceCounter(&nEnd);
	time=(double)(nEnd.QuadPart-nBegin.QuadPart)/(double)nFreq.QuadPart; 
	
	
	out<<"maxi:"<<maxi<<" mini:"<<mini<<"\n search time:"<<time<<"s\n";
	in.close();
	out.close();
	return 0;
}

②功能函数：生成规模为n的随机数

#include <time.h>
#include <stdlib.h>
#include <fstream>
#include <iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	ofstream out("input.txt");
	out<<n<<'\n';
	srand((unsigned)time(NULL));
	for(int i=0;i<n;i++){
		out<<rand()<<' ';
		if((i+1)%10==0) out<<'\n';
	}
	out.close();
	return 0;
}

4.复杂度分析：

①主函数：

时间复杂度分析：

search函数：

递推关系：

分治法查找最大值最小值实验