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

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

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

//YCL

//2004.10.27

#include<iostream.h>

//定义一个类,表示最大和最小元素的组合

class MaxMin{

private:

int max,min;

public:

MaxMin(int x,int y)//构造函数,给max和min附最大和最小元素的值

else

}

~MaxMin(){}//析构函数

int GetMax()//获取其中的最大值

{

return max;

}

int GetMin()//获取其中的最小值

{

return min;

}

void Print()//输出最大值和最小值

};

//从两个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==ji==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<1n>N)

cout<<"Overflow!Again!"<<endl;

}while(n<1n>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<1i>n)(j<1j>n)(i>j&&(i>0&&i<n)&&(j>0&&j>n)))

{

if(i<1i>n)

cout<<"The start point overflows!"<<endl;

if(j<1j>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<1i>n)(j<1j>n)(i>j&&(i>0&&i<n)&&(j>0&&j>n)));//输入查找范围

Bin_MaxMin(i,j,a).Print();//输出查找结果

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航