给定序列,使用分治法求出序列中的最大值,最小值,并输出比较次数(不要用排序方法)
//求解序列中的最大值和最小值 #includeusing namespace std; #define max(x,y) x>y?x:y #define min(x,y) x a, int low, int high, int &Max,int &Min,int &b){ if(low == high) // 区间只有一个元素 { Max = a[low]; Min = a[low]; b++; } else if(low == high - 1) // 区间只有两个元素 { Max = max(a[low],a[high]); Min = min(a[low],a[high]); b++; } else{ int mid = (low + high) / 2; int Lmax, Lmin; solve(a, low, mid, Lmax, Lmin,b); // 左区间求Lmax和Lmin int Rmax, Rmin; solve(a, mid + 1, high, Rmax, Rmin,b); // 右区间求Rmax和Rmin Max = max(Lmax,Rmax); Min = min(Lmin,Rmin); } }//分治法 int main(){ vector a;//定义一个vector数组 int number; int b=0; while (1) { cin>>number; a.push_back(number);//每输入一个数字将其添加到数组的最后 if(cin.get() == 'n')//输入回车 跳出循环 break; } //int n = sizeof(a)/sizeof(a[0]); int n = a.size(); int Max,Min; int max,min; solve(a, 0, n - 1, Max, Min,b); cout<<"Max = "<



