当前位置: 首页 > >

用分治法求一个数组的最大最小值

发布时间:

问题:用分治法来求解一个数组的最大最小值


?????


分析:用遍历的方法来求解当然很简单,但是题目给我们的要求是用分治法,因此我们需要每次利用递归来求数组的一个小部分的最大最小值,递归的结束条件是数组中有两个元素或者一个元素。


?????


下面是C语言源代码:(在Linux Ubuntu下gcc 4.0 编译通过 )


??


?


#include


????


// find the max and min value between a[m] and a[n]


void max_min(
int a[],int m, int n, int* max,int* min)?


{


??? int middle,hmax,hmin,gmax,gmin;


???


??? if( m==n )


??? {


??????? *max = * min = a[m];


??? }


??? else if(m == n-1)


??? {


??????? if( a[m] > a[n])


??????? {


??????????? *max = a[m];


??????????? *min = a[n];


??????? }


??????? else


??????? {


??????????? *max = a[n];


??????????? *min = a[m];


??????? }


??? }


??? else


??? {


??????? middle = (m+n)/2;


??????? max_min(a,m,middle,&gmax,&gmin);


??????? max_min(a,middle+1,n,&hmax,&hmin);


??????? if(gmax > hmax)


??????? {


??????????? *max = gmax;


??????? }


??????? else


??????? {


??????????? *max = hmax;


??????? }


??? ??? if(gmin < hmin)


??????? {


??????????? *min = gmin;


??????? }


??????? else


??????? {


??????????? *min = hmin;


??????? }


??? }


}


?????


int main(
int argc,char * argv[])


{


??? int max,min;


??? int num_elem = argc-1;


??? int i;


??? int * array = (int *)malloc( (argc-1) *sizeof(int) );


??? for(i=1;i

??? {


??????? array[i-1]= atoi(argv[i]);


??? }


????


??? max_min(array,0,num_elem-1,&max,&min);


???????


??? printf("The max is %d ,the min is %d /n",max,min);


??? return 0;??


}



友情链接: