数据结构邓俊辉——递归+分治（max2最大值与次大值）

问题：

在一个数组中找出最大的两个数，要求比较的次数尽可能少。

方法：

分治+递归 分治思想：

字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。 步骤： step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题； step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题 step3 合并：将各个子问题的解合并为原问题的解。

代码实现：

BUG调试：出现“Stack overflow” 堆栈溢出的情况，开始一直以为是给的保留堆栈大小不足，在VS中把堆栈加到很大也没有用，后来发现原来是递归基没有写上去，代码停不下来，加上递归基，解决。

#include <iostream> using namespace std; //分治+递归 void max2(int *a, int low, int high, int &x1, int &x2) { if (low + 2 == high)//必须加上递归基 { if (a[x1 = low] < a[x2 = (low + 1)]) { x1 = low + 1; x2 = low; } return; } if (low + 1 == high)//必须加上递归基 { x1 = low; x2 = low; return; } int b = (low + high) / 2;//求中间数 int x1_R, x2_R; max2(a, low, b, x1_R, x2_R);//递归调用max2 int x1_L, x2_L; max2(a, b, high, x1_L, x2_L); if (a[x1_L] > a[x1_R])// { x1 = x1_L; x2= (a[x1_R] > a[x2_L]) ?x1_R : x2_L; } else { x1 = x1_R; x2 = (a[x2_R] < a[x1_L]) ? x1_L : x2_R; } } int main() { int c[]= {1,2,3,4,10,3,12,27,24,29,7}; int max; int flowing_max; int length; length = size(c); max2(c, 0, length, max, flowing_max); cout << "max=" << c[max] << endl; cout << "flowing_max=" << c[flowing_max] << endl; }