标题

[学习经验]使用分治法用1.5*N次比较求数组的最大值和最小值

责任编辑:admin
日期:2012-12-03

求一个数组的最大值和最小值,一般的方法,我们用两个变量max和min,遍历一遍数组,每次遇到一个元素,就更新max和min,扫描一遍就得到了最大值和最小值。该方法共比较了2*N次。

本文用分治法将2*N次的比较,减少到了1.5*N次,本文主要练习对分治法的理解。

分治算法由两部分组成:

分(divide):递归解决较小的问题(基本情况除外)

治(conquer):从子问题的解构建原问题的解。

分治算法的特点:

1、代码中至少含有2个递归调用,只含有一个递归调用的算法,不是分治算法

2、每个递归调用解决的是不相交的问题

3、分治算法必然对递归调用的返回值进行了合并

简单来说,分治算法就是至少2次递归调用、子问题不相交、必然合并子问题的解

本题目解决求数组的最大值最小值,可以将问题分解为数组左边的最大值最小值、右边的最大值最小值、它们的最大值最小值比较后整个数组的最大值最小值。

以下是测试代码,加上了详细的注释: 

  1. #include <iostream> 
  2. using namespace std; 
  3.  
  4. struct MaxMin{ 
  5.     int max; 
  6.     int min; 
  7. }; 
  8.  
  9. int arr[] = {5,6,8,3,7,9}; 
  10.  
  11. /*找出arr数组的beg和end之间的max和min,用分治法实现*/ 
  12. //来自程序员求职网www.51projob.com
  13. MaxMin getMaxMin(int *arr, int beg, int end){ 
  14.     //处理分治算法的基本情况 
  15.     if(end-beg<=1){ 
  16.         //如果只剩下2个元素了,那么就返回就行了 
  17.         MaxMin tmp; 
  18.         if(arr[beg]>arr[end]){ 
  19.             tmp.max = arr[beg]; 
  20.             tmp.min = arr[end]; 
  21.              
  22.         } else { 
  23.             tmp.max = arr[end]; 
  24.             tmp.min = arr[beg]; 
  25.         } 
  26.         return tmp; 
  27.     } 
  28.     //错误的地方在这里,比如左边,每次开始应该为beg,beg+(end-beg)/2, 
  29.     //而不是beg,(end-beg)/2区间最容易弄错 
  30.     //分治 
  31.     MaxMin leftMaxMin = getMaxMin(arr, beg, beg+(end-beg)/2); 
  32.     MaxMin rightMaxMin = getMaxMin(arr, beg+(end-beg)/2+1,end); 
  33.  
  34.     //合并子问题的解 
  35.     int maxv=0,minv=0; 
  36.     if(leftMaxMin.max>rightMaxMin.max){ 
  37.         maxv = leftMaxMin.max; 
  38.     } else { 
  39.         maxv = rightMaxMin.max; 
  40.     } 
  41.  
  42.     if(leftMaxMin.min>rightMaxMin.min){ 
  43.         minv = rightMaxMin.min; 
  44.     } else { 
  45.         minv = leftMaxMin.min; 
  46.     } 
  47.     MaxMin tmp; 
  48.     tmp.max = maxv; 
  49.     tmp.min = minv; 
  50.     return tmp; 
  51.  
  52. void main(){ 
  53.  
  54.      
  55.     MaxMin tmp = getMaxMin(arr,0,6-1); 
  56.     cout<<tmp.max<<" "<<tmp.min<<endl; 
  57.     system("pause"); 

结果截图:

分治算法的一些应用:

1、线性时间的树遍历算法

2、归并排序

3、快速排序

 

阅读:

相关新闻:
评论