分治法找到一个数组的最大元素 [英] Divide and conquer algorithms to find the maximum element of an array

问题描述

我想了解以下算法如何工作的。

I am trying to understand how the following algorithms works.

#include <iostream>
using namespace std;
int maxsimum(int a[], int l, int r) {
    if (l == r)  
        return a[l];
    int m = (l+r)/2;
    int u = maxsimum(a,l,m);
    int v = maxsimum(a,m+1,r);
    return u>v?u:v;    
}

int main() {
    int a[] = {34,23,45,56,30,31,57,33,55,10};
    int n = sizeof(a)/sizeof(int);
    cout << maxsimum(a,0,n) << endl;         
    return 0;
}

首先，我感兴趣的是，尽管算法的正常工作，它是神秘的对我来说，如何找到最大元素。我会告诉我如何理解这个算法：

First, what I am interested in is that in spite of algorithm's working correctly, it is mysterious for me how it finds the maximum element. I will show how I understood this algorithm:

第1步：我们说一个数组的情况下， L = 0 和 R = 10 ，它检查如果（L＆GT; R）所以它计算不抱当然 M =（0 + 10）/ 2; 。然后再做新边界的过程。第一对是（0,5），第二个是（6,10），并在最后操作之后比较两个返回的值并最终返回它们之间的最大元素

Step 1: we say that in case of an array, l=0 and r=10, it checks if (l>r) which does not hold of course so it calculates m=(0+10)/2;. Then do again the procedure for new bounds. The first pair is (0,5), the second is (6,10) and after the final operation it compares two returned values and finally returns the maximum element between them.

这是否算法总是工作？在每次迭代中它不会做任何比较，只有最后一步。它如何能够确定每个递归迭代最大元素？它仅检查什么。例如：取对（0,5），是（0超过5）？无，所以再次重复，然后再次重新划分这些界限成两个以便得到新的平均值m1 =（0 + 5）/ 2，并返回一些元素，但不是最大。也为第二子阵可以说是一样的。

Does this algorithm always work? In each iteration it does not do any comparison, only the final step. How can it determine the maximum element at each recursive iteration? It checks only what. For example: take pair(0,5), is (0 more than 5)? No, so repeat again and divide these bounds into two so get new average value m1=(0+5)/2 then again again and return some element but not the maximum. Also for second subarray we can say the same.

这是什么算法的主要思想？

What is the main idea of this algorithm?

推荐答案

您的困惑是可以理解的：书面的算法包含了两个错误。它访问内存过去的结束，这是非常，非常糟糕。此外，范围是否只包含一种元素的试验是不正确。如果不加以解决，这将导致堆栈溢出。

Your confusion is understandable: the algorithm as written contains a couple of bugs. It accesses memory past the end of a, which is very, very bad. Also, the test whether a range contains only one element is incorrect. If not addressed, this leads to a stack overflow.

maxsimum函数被调用的方式表明，下界被包括在范围内，但上限是没有的。 A [0] 是有效的，但 A [N] 访问内存过去的结束。当分割的范围内，我们想要的第一部分由L，但不包括m和第二部分运行以启动在m和运行，但不包括河换句话说：第一部分的独占的上限为等于所述第二部分的包容下限。到maxsimum第一内部调用是正确的。第二个内部调用应该是：

The way the maxsimum function is called suggests that the lower bound is included in the range, but the upper bound is not. a[0] is valid, but a[n] accesses memory past the end of a. When splitting the range, we want the first part to run from l up to but not including m, and the second part to start at m and run up to but not include r. In other words: the "exclusive" upper limit of the first part is equal to the "inclusive" lower limit of the second part. The first internal call to maxsimum is correct. The second internal call should be:

int v=maxsimum(a,m,r); 

这留给我们的检测范围的长度为1的问题既然这样，算法实际上看起来一个的空的范围内。正确的测试是看的上限和下限之间的区别：

This leaves us with the problem of detecting a range of length 1. As it stands, the algorithm actually looks for an empty range. The proper test is to look at the difference between the upper and the lower bound:

if (r-l == 1) return a[l];

完整的功能如下：

The complete function is as follows:

int maxsimum(int a[],int l,int r){
   if (r-l==1)  return a[l];
   int m=(l+r)/2;
   int u=maxsimum(a,l,m);
   int v=maxsimum(a,m,r);
   return u>v?u:v;    
}

现在，我们有一个正确的程序，这是如何工作的解释很简单：

Now that we have a correct program, the explanation of how this works is straightforward:

1. 如果该范围仅包含一个元素，则该元素是最大。


2. 如果范围包含一个以上的元素，我们在分成两部分的。我们递归调用函数来计算最大每一部分。这两个值的最大是最大的整个范围的。

这篇关于分治法找到一个数组的最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！