这学期总算开了算法课了,不得不吐槽,大四上学期开这课,时间很尴尬。不多说了,第一节课老师留了道题,要求在一个递归函数里求序列的最大最小值。
算法思路: 1)如果数组长度为1,则最大值与最小值相等 2)如果数组长度为2,则最大值与最小值各位其中一个。 3)如果数组长度大于2,那么采用二分策略,递归求前一半的最大最小值,与后一半的最大最小值,之后两两比较后的数组的最大最小值。
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
bool MinMax(int* num , int start, int end , int& Min , int& Max)
{
//end小于start没有意义
if(end <start){
return false;
}else if(end == start){
//序列长度为1,最大值与最小值相等
Min = Max = num[start];
}else if(end - start == 1){
//序列长度为2,一个为最小值,一个为最大值
Min = min(num[start],num[end]);
Max = max(num[start],num[end]);
return true;
}else{
//序列长度大于2,递归找前一半的最大最小值
//后一半的最大最小值,两者进行比较
int mid = (start + end) / 2;
int tmp_max,tmp_min;
MinMax(num,start,mid,tmp_min,tmp_max);
MinMax(num,mid+1,end,Min,Max);
Max = max(tmp_max,Max);
Min = min(tmp_min,Min);
return true;
}
}
int main()
{
int size;
cin>>size;
int* num,Min,Max;
num = new int[size];
for(int i = 0 ; i< size; i++){
cin>>num[i];
}
if(MinMax(num,0,size-1,Min,Max)){
cout<<"Max = "<<Max<<endl;
cout<<"Min = "<<Min<<endl;
}
return 0;
}
截图: