分治法查找数组最大最小值

  一直以来,在编程的道路上,只注重寻求问题的解决方法,很少注重效率算法之类的东西,自然算法是比较薄弱的地方,刚看到有人在论坛问分治法的东西,到google搜索了下,把百度百科的分治法看了遍(话说google真比baidu厚道,很多时候搜东西,百度百科都是第一条显示),自己把那个小例子写了遍,打算以后尽量多学习学习算法之类的知识.

#include <time.h> #include <iostream> #include <iomanip> const int NUM = 40; void InitArray(int *arr, int num); void Find(int *arr, int begin, int end, int *max, int *min) { if (end-begin <= 1) //一直到分解为最小子结构时才走这里 { if (arr[begin] > arr[end]) { *max = arr[begin]>*max ? arr[begin] : *max; *min = arr[end]<*min ? arr[end] : *min; } else { *max = arr[end]>*max ? arr[end] : *max; *min = arr[begin]<*min ? arr[begin] : *min; } return; } else { int i = begin + (end-begin)/2; Find(arr, begin, i, max, min); Find(arr, i+1, end, max, min); } } int main() { int arr[NUM]; InitArray(arr, NUM); int max = 0; int min = 0; Find(arr, 0, NUM-1, &max, &min); std::cout << "max = " << max << ", min = " << min << std::endl; return 0; } void InitArray(int *arr, int num) { for (int i=0; i<num; ++i) *(arr+i) = i; srand( time(NULL)); int s, r; for (int j=0; j<num; ++j) { r = rand() % num; s = arr[r]; arr[r] = arr[num-1-r]; arr[num-1-r] = s; } for (int k=0; k<num; ++k) { std::cout << std::setw(2) << *(arr+k) << ' '; if (!((k+1)%10)) std::cout << std::endl; } }

大致说明下程序流程,调用Find函数后,将判断是否为最小子结构,如果不是则将它2分继续判断,如果是最小子结构,则把最小子结构的元素与全局最大最小值做比较.

这里假设数据元素个数为8时,该程序走的流程应该是

0-7分解为0-3->

0-3分解为0-1满足最小子结构做完比较后return->

继续0-3分解的2-3满足最小子结构做完比较后return->

继续0-7分解的4-7->

4-7分解为4-5满足最小子结构做完比较后return->

继续4-7分解的6-7满足满足最小子结构做完比较后return,此时后面没有操作可做将一直return出第一次调用Find的位置,分治到处结束.

最后

以上就是知性楼房为你收集整理的分治法查找数组最大最小值的全部内容，希望文章能够帮你解决分治法查找数组最大最小值所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。