twofen.c

二分递归查找最大和最小元素

//二分递归查找最大和最小元素
//YCL
//2004.10.27
#include<iostream.h>
//定义一个类，表示最大和最小元素的组合
class MaxMin{
private:
 int max,min;
public:
 MaxMin(int x,int y)//构造函数，给max和min附最大和最小元素的值
 {
  if(x>y)
  {
   max=x;
   min=y;
  }
        else
  {
   max=y;
   min=x;
  }
 }
 ~MaxMin(){}//析构函数
 int GetMax()//获取其中的最大值
 {
  return max;
 }
 int GetMin()//获取其中的最小值
 {
  return min;
 }
 void Print()//输出最大值和最小值
 {
  cout<<"Max="<<max<<endl;
  cout<<"Min="<<min<<endl;
 }
};
//从两个MaxMin类对象中选取最大值和最小值形成新的组合
MaxMin Comp(MaxMin t1,MaxMin t2)
{
 int x,y;
 x=t1.GetMax()>t2.GetMax()?t1.GetMax():t2.GetMax();
 y=t1.GetMin()<t2.GetMin()?t1.GetMin():t2.GetMin();
 MaxMin t(x,y);
 return t;
}
//二分递归查找:在数组a[]的[i,j]范围内查找
MaxMin Bin_MaxMin(int i,int j,int a[])
{
 int mid;
 if(i==j||i==j-1)//递归出口:当传入数组中只有一个或两个元素时
 {
  MaxMin fmaxfmin(a[i-1],a[j-1]);
  return fmaxfmin;
 }
 else//递归调用,二分查找
 {
  mid=(i+j)/2;
  MaxMin ftemp1=Bin_MaxMin(i,mid,a);
  MaxMin ftemp2=Bin_MaxMin(mid+1,j,a);
  return Comp(ftemp1,ftemp2);
 }
}

void main()
{
 int i,j,n;
 const int N=10;
 int a[N];
 do{
  cout<<"How many elements do you want to input?";
  cin>>n;
        if(n<1||n>N)
   cout<<"Overflow!Again!"<<endl;
 }while(n<1||n>N);//输入元素个数
 cout<<"Input the elements:"<<endl;
 for(i=0;i<n;i++)//输入元素内容
  cin>>a[i];
 do{
  cout<<"Input the start point and the end point:";
     cin>>i>>j;
  if((i<1||i>n)||(j<1||j>n)||(i>j&&(i>0&&i<n)&&(j>0&&j>n)))
  {
   if(i<1||i>n)
    cout<<"The start point overflows!"<<endl;
   if(j<1||j>n)
    cout<<"The end point overflows!"<<endl;
   if(i>j&&(i>0&&i<n)&&(j>0&&j>n))
    cout<<"The start point and the end point maybe need to be exchanged!"<<endl;
   cout<<"Input them again!"<<endl;
  }
 }while((i<1||i>n)||(j<1||j>n)||(i>j&&(i>0&&i<n)&&(j>0&&j>n)));//输入查找范围
 Bin_MaxMin(i,j,a).Print();//输出查找结果
}