Question

用分治法求数组最大数（c语言）

在含有n个不同元素的集合中，找出他们的最大数（用分治法，c语言写程序）

Answer 1

#include <stdio.h>

#define N 21

int max(int a,int b){
if(a>b)
return a;
return b;
}

int getM(int * a,int l,int u){
if(u==l)
return a[u];
else{
return max(getM(a,l,(u+l)/2),getM(a,(u+l)/2+1,u) );
}
}

int main()
{
int a[N]={1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17};
printf("max=%d",getM(a,0,N-1));
return 0;
}

Answer 2

给，已经编译运行通过：
#include<stdio.h>
#include<stdlib.h>

#define N 20

static long int tmp=1;

void getMax(int *a,int i,int j,int *fmax)
{
int mid,hmax,hmin,gmax,gmin;

tmp++;

if(tmp>=1000)
{
printf("The program mabye dead!\n");
exit(0);
}

if(i==j)
{
*fmax=a[i]; return;
}

if(i==j-1)
{
if(a[i]>a[j])
{
*fmax=a[i];return;
}
else
{
*fmax=a[j]; return;
}
}
else
{
mid=(i+j)/2;
getMax(a,i,mid,&gmax);
getMax(a,mid+1,j,&hmax);
*fmax=gmax>hmax? gmax:hmax;
}

}

void main()
{
int max;
int a[N]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
getMax(a,0,N-1,&max);
printf("max=%d",max);
}

Answer 3

int max(int a,int b)
{
return((a>b)?a:b);
}

void Search(int a[],int *max0,int n)

{int g[30];

int i,m;

int max1,max2;

if(n==1)

{
*max0=a[0];
}

else if(n==2)

{
*max0=max(a[0],a[1]);
}

else

{ m=n/2;

for(i=0;i<m;i++)

g[i]=a[i];

Search(g,&max1,m);

for(i=0;i<n-m;i++)

g[i]=a[i+m];

Search(g,&max2,n-m);

*max0=max(max1,max2);

}