C++

Question

我无法理解这个分而治之函数如何比较数据元素：

int main()
{
  int arr[] = { -5, -10, -16, -3, -7 };
  int largest;

  largest = largest_element(arr, 0, sizeof(arr) / sizeof(int));
  cout << "Largest element in arr is " << largest << ".\n";

  return 0;
}

int largest_element(const int *a, int begin, int past_end)
{
  int result;
  int mid;
  int left_large;
  int right_large;

  assert(begin >= 0);
  assert(begin < past_end);

  if (past_end - begin == 1)
    result = a[begin];
  else {
    mid = (begin + past_end) / 2;
    left_large = largest_element(a, begin, mid);
    right_large = largest_element(a, mid, past_end);
    if (left_large >= right_large)
      result = left_large;
    else
      result = right_large;
  }

  //STOP! draw tree here when begin == 1, and past_end == 2.
  return result;
}

我知道数组只是简单地分成更小的子数组，一旦达到基本情况，它将 return a[begin]。但是，根据我的图表，如果当我们有一个包含两个元素的数组时，它只是 return 第一个值，我不明白如何真正比较这些值。例如，如果数组中最右边的元素没有其他可比较的元素，将如何进行比较？

Here is my diagram. 我没有其他图表可以与我的进行比较。

Answer 1

如果数组已排序，这样的事情只会对您有所帮助，并且您可以在每次递归时忽略一半的结果。

只是遍历元素以找到最大的数字。你必须检查每个值

Answer 2

I don't understand how the values are truly compared if when we have an array of two elements, it simply returns the first value.

我无法重现该发现。当 arr 只有 2 个元素时，函数仍然 returns 两者中较大的一个。

您的调试器是评估您的代码并找出您误解了什么的合适方式。

但是，添加诊断并允许代码报告其进度可能会很有趣。这是一种技巧：

#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <cassert>


class T548_t
{
   int depth;

public:

   T548_t() = default;
   ~T548_t() = default;

   int exec()
      {
         {
            depth = 0;  // 0    1    2   3   4
            int arr[] = { -5, -10, -16, -3, -7 }; // -3 is largest
            uint sz = sizeof(arr) / sizeof(int);
            std::cout << hdr(sz);

            std::cout << "\n\n  Largest element in arr is  "
                      << largest_element(arr, 0, sz)
                      << ".\n" << std::endl;
         }
         {
            depth = 0;
            int arr[] = { -10, -5 }; // -5 is largest
            uint sz = sizeof(arr) / sizeof(int);
            std::cout << hdr(sz);

            std::cout << "\n\n  Largest element in arr is  "
                      << largest_element(arr, 0, sz)
                      << ".\n" << std::endl;
         }
         return 0;
      }

private: // methods

   int largest_element(const int* a, int begin, int past_end)
      {
         int result;
         int mid;
         int left_large;
         int right_large;

         assert(begin >= 0);
         assert(begin < past_end);

         std::cout << show(a, begin, past_end) << std::flush;

         if (past_end - begin == 1)
            result = a[begin];
         else {
            mid = (begin + past_end) / 2;
            left_large  = largest_element(a, begin, mid);
            right_large = largest_element(a, mid, past_end);

            if (left_large >= right_large)
               result = left_large;
            else
               result = right_large;
         }

         //STOP! draw tree here when begin == 1, and past_end == 2.
         depth -= 1;
         return result;
      }

   std::string show(const int* a, int b, int e)
      {
         std::stringstream ss;
         depth += 1;
         ss << "\n  a[" << b << " .. " << e-1 << "]    " 
            << depth << "   ";

         if(b > 0)
            ss << std::setw(4*b) << " ";

         for (int i = b; i < e; ++i)
            ss << std::setw(4) << a[i];

         return ss.str();
      }

   std::string hdr(uint sz)
      {
         std::stringstream ss;
         ss << "\n  "
            << "  b .. e"
            << std::setw(8) << "depth"
            << std::setw(4) << " ";
         for (uint i=0; i<sz; ++i)
            ss << i << "   ";
         return ss.str();
      }

}; // class T548_t

int main(int, char**)
{
   T548_t   t548;
   return t548.exec();
}

这是输出：

    b .. e   depth    0   1   2   3   4   
  a[0 .. 4]    1     -5 -10 -16  -3  -7
  a[0 .. 1]    2     -5 -10
  a[0 .. 0]    3     -5
  a[1 .. 1]    3        -10
  a[2 .. 4]    2            -16  -3  -7
  a[2 .. 2]    3            -16
  a[3 .. 4]    3                 -3  -7
  a[3 .. 3]    4                 -3
  a[4 .. 4]    4                     -7

  Largest element in arr is  -3.


    b .. e   depth    0   1   
  a[0 .. 1]    1    -10  -5
  a[0 .. 0]    2    -10
  a[1 .. 1]    2         -5

  Largest element in arr is  -5.

C++ - 难以理解分而治之的功能

C++ - Trouble Understanding a Divide and Conquer Function

arrays

recursion

divide