用分治法在一个元素集合中寻找最大元素和最小元素 c++

Question

算法我会 主要是主函数不会写
如果您没有完整代码 教我一下主函数怎么写也行

Answer 1

我做的：：（其中算法中我设计的是模板类，不想那么复杂所以主函数中就直接用集合int a[10]={2,5,3,9,7,6,0,1,4,8}了）

分治法：
#include "stdafx.h"
#include <iostream>

template <class T>
class SortableList
{
private:
T *l;
int maxSize,n;
public:
SortableList(int mSize)
{
maxSize=mSize;
l=new T[maxSize];
n=0;
}
~SortableList(){delete []l;}
void MaxMin(int i,int j,T &max,T &minn)const;
int init(T a[],int nSize)
{
if(nSize<=maxSize)
{
int i;
n=nSize;
for(i=0;i<n;i++)
l[i]=a[i];
return 1;
}
else return 0;
}
};
template <class T>
void SortableList<T>::MaxMin(int i,int j,T &max,T &min)const
{
T min1,max1;
if(i==j)max=min=l[i];
else
if(i==j-1)
{
if(l[i]<l[j])
{
max=l[j];min=l[i];
}
else
{
max=l[i];min=l[j];
}
}
else
{
int m=(i+j)/2;
MaxMin(i,m,max,min);//求前半部子表中的最大、最小元
MaxMin(m+1,j,max1,min1);//求后半部子表中的最大、最小元
if(max<max1)max=max1;
if(min>min1)min=min1;
}
}

int main()
{
int i,amax,amin;
SortableList<int> alist(10);
int a[10]={2,5,3,9,7,6,0,1,4,8};
cout <<"元素集合为：";
for(i=0;i<10;i++)
cout <<a[i]<<" ";
cout <<endl ;
if(!alist.init (a,10))
cout <<"错误！";
alist.MaxMin (0,9,amax,amin);
cout <<"最大元素为"<<amax<<" 最小元素为"<<amin<<endl ;
return 0;
}本回答被提问者采纳