递归求序列最大最小值

AI那点小事

发布于 2020-04-18 20:00:58

1.5K0

发布于 2020-04-18 20:00:58

文章被收录于专栏：AI那点小事AI那点小事

这学期总算开了算法课了，不得不吐槽，大四上学期开这课，时间很尴尬。不多说了，第一节课老师留了道题，要求在一个递归函数里求序列的最大最小值。

算法思路： 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;
}

截图：