分治法求最大和最小值

例题：金块问题

老板有一袋金块（共n块，n是2的幂（n>=2）），最优秀的员工得到其中最重的一块，最差的员工得到其中最轻的一块。假设有一台比较重量的仪器，请你用最少的比较次数找出最重和最轻的金块。

这个问题其实就是输入n个数，找出最大和最小数的问题。

解决问题的策略

蛮力策略：对金块逐个进行比较查找。（扫描数组一轮，寻找最大和最小的数。）该策略需要进行（n－1）次的比较才能得到Max和min。

分治法（二分法）策略：问题可以简化为在n个数里面寻找最大和最小值。

（1）将数据等分为两组(两组数据的个数可能相差1)，目的是分别选取其中的最大（小）值。

（2）递归分解直到每组元素的个数<=2，则可以简单地找到其中的最大（小）值。

（3）回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为当前问题的解。

 1 #include<stdio.h>
 2 #include<time.h>
 3 #include<stdlib.h>
 4 int maxMin(int *a,int i,int j,int *max,int *min);
 5 int main()
 6 {
 7     int *a;
 8     int i,n;
 9     int max,min;
10     
11     scanf("%d",&n);
12     a=(int *)malloc(sizeof(int)*n);
13     srand((unsigned int)time(0));
14     for(i=0;i<n;i++) a[i]=rand()%91+10;
15     for(i=0;i<n;i++)
16     {
17         printf("%d ",a[i]);
18         if((i+1)%5==0) printf("
");
19     }
20     printf("

");
21     maxMin(a,0,n-1,&max,&min);
22     printf("%d %d
",max,min);/**/
23     return 0;
24 }
25 /*---------------------------------------------------
26 函数名称：maxMin
27 函数功能：在数组a的区间[i,j]范围内寻找一个最大值和一个最小值并通过指针*max和*min返回。
28 -----------------------------------------------------*/
29 int maxMin(int *a,int i,int j,int *max,int *min)
30 {
31     int mid;
32     int lmax,lmin,rmax,rmin;
33     if(j==i) { *max=a[i]; *min=a[i]; return 0;}
34     else if(j-i==1)
35     {
36         if(a[i]>a[j])  {*max=a[i];*min=a[j];return 0;}
37         else  {*max=a[j];*min=a[i];return 0;}
38     }
39     else
40     {
41         mid=i+(j-i)/2;
42         maxMin(a,i,mid,&lmax,&lmin);
43         maxMin(a,mid+1,j,&rmax,&rmin);
44         if(lmax>rmax)   *max=lmax;
45         else   *max=rmax;
46         if(lmin<rmin)     *min=lmin;
47         else   *min=rmin;
48     }
49     return 0;
50 }

二分策略代码

由该问题演变出来的另一个问题：寻找数组当中最大的两个数和最小的两个数。下面的代码实现了该算法，同样采用的是二分策略。【该算法稍有欠缺：对假如最大数或最小数有相同的多个值，可能得到的最大（小）值与次大（小）值是一样的。】

 1 #include<stdio.h>
 2 #include<time.h>
 3 #include<stdlib.h>
 4 int maxMin2(int *a,int i,int j,int *max1,int *max2,int *min1,int *min2);
 5 int max(int a,int b);
 6 int min(int a,int b);
 7 int  main()
 8 {
 9     int *a;
10     int i,n;
11     int max1,max2,min1,min2;
12     
13     scanf("%d",&n);
14     a=(int *)malloc(sizeof(int)*n);
15     srand((unsigned int)time(0));
16     for(i=0;i<n;i++) a[i]=rand()%91+10;
17     for(i=0;i<n;i++)
18     {
19         printf("%d ",a[i]);
20         if((i+1)%5==0) printf("
");
21     }
22     printf("

");
23     maxMin2(a,0,n-1,&max1,&max2,&min1,&min2);
24     printf("%d %d
%d %d
",max1,max2,min1,min2);/**/
25     return 0;
26 }
27 int maxMin2(int *a,int i,int j,int *max1,int *max2,int *min1,int *min2)
28 {
29     int mid,t;
30     int lmax1,lmax2,lmin1,lmin2,rmax1,rmax2,rmin1,rmin2;
31     if(j-i==2) 
32     {
33         *max1=max(a[j],max(a[i],a[i+1]));
34         *min1=min(a[j],min(a[i],a[i+1]));
35         t=a[i]+a[j]+a[i+1];
36         *max2=t-*max1-*min1;
37         *min2=*max2;
38         return 0;
39     }
40     else if(j-i==1)
41     {
42         if(a[i]>a[j]){*max1=a[i];*max2=a[j]; *min1=a[j];*min2=a[i];return 0;}
43         else{*max1=a[j];*max2=a[i]; *min1=a[i];*min2=a[j];return 0;}
44     }
45     else
46     {
47         mid=i+(j-i)/2;
48         maxMin2(a,i,mid,&lmax1,&lmax2,&lmin1,&lmin2);
49         maxMin2(a,mid+1,j,&rmax1,&rmax2,&rmin1,&rmin2);
50         if(lmax1>rmax1)
51         {
52             *max1=lmax1;
53             if(lmax2>rmax1) *max2=lmax2;
54             else *max2=rmax1;
55         }
56         else
57         {
58             *max1=rmax1;
59             if(lmax1>rmax2) *max2=lmax1;
60             else *max2=rmax2;
61         }
62         if(lmin1<rmin1)
63         {
64             *min1=lmin1;
65             if(lmin2<rmin1) *min2=lmin2;
66             else *min2=rmin1;
67         }
68         else
69         {
70             *min1=rmin1;
71             if(lmin1<rmin2) *min2=lmin1;
72             else *min2=rmin2;
73         }
74     }
75     return 0;
76 }
77 int max(int a,int b)
78 {    return a>b?a:b;       }
79 int min(int a,int b)
80 {    return a<b?a:b;       }

View Code

对于该算法的缺陷，暂时还不知道如何解决了呵呵