分治法递归求取数组中的最大和最小值

Question

如题所述

Answer 1

//求一个数组A[i...j]的最大值和最小值，分支算法，递归实现//2015.2.9//dev c++#include<stdio.h>#include<malloc.h> int min(int a,int b){    return a<b? a:b;}int max(int a,int b){    return a>b? a:b;}int* MaxMin(int a[],int i,int j){     int *m=(int *)malloc(2*sizeof(int));     if(j-i+1==1){         m[0]=m[1]=a[i];         return m;     }     if(j-i+1==2){         if(a[i]<a[j]){             m[0]=a[i];             m[1]=a[j];               }         else{             m[0]=a[j];             m[1]=a[i];         }         return m;     }     int k=(j-i+1)/2;     int *m1 = MaxMin(a,i,k);     int *m2 = MaxMin(a,k+1,j);     m[0]=min(m1[0],m2[0]);     m[1]=max(m1[1],m2[1]);     return m;}int main(){    int a[128];    int n;    int i;    while(scanf("%d",&n)!=EOF){        for(i=0;i<n;i++){            scanf("%d",&a[i]);        }        int *m = MaxMin(a,0,n-1);        printf("%d %d\n",m[0],m[1]);    }    return 0;}