如何解决这个寻找最大值和最小值的递归（分而治之）过程？

Question

为了在递归和分而治之的方法中找到 maximum & minimum，我从 伪代码 .但是这段代码有问题，我找不到maximum & minimum。 maximum & minimum 的结果在这里不正确。

#include <bits/stdc++.h>
using namespace std;

int num[50000], max1 = 0, min1 = 0, max2 = 0, min2 = 0;

void maxmin(int i, int j, int &max1, int &min2)
{
    if(i == j)
        max1 = min1 = num[i];
    else if(i == j - 1)
        {
            if(num[i] < num[j])
                {
                    max1 = num[j];
                    min1 = num[i];
                }
            else
                {
                    max1 = num[i];
                    min1 = num[j];
                }
        }
    else
    {
        int mid = (i + j) / 2;
        maxmin(i, mid, max1, min1);
        maxmin(mid+1, j, max2, min2);
        if(max1 < max2)
            max1 = max2;
        if(min1 > min2)
            min1 = min2;

    }
}

main()
{
    int n, i, minValue, maxValue;
    cout<<"No. of Data: ";
    cin>>n;
    cout<<"\nRange(min, max): ";
    cin>>minValue>>maxValue;
    for(i=0; i<n; i++)
    {
        num[i] = minValue+(rand()%(int)(maxValue-minValue+1));
    }
    maxmin(0, n-1, max1, min1);
    cout<<"\nMax: "<<max1<<"\tMin: "<<min1<<endl;
}

这个伪代码/代码有什么问题??

Answer 1

在 maxmin(0, n-1, max1, min1); 中，您是否希望 max1 和 max2 通过引用传递？如果是，则需要修改函数签名为：

void maxmin(int i, int j, int & max1, int & min2)

Answer 2

好的，下面你会发现两个函数，当被调用时。将找到数组中最大和最小的元素。如果你想使用它们，你将不得不更改你的主要代码以使它们工作..

您的主程序可能看起来像这样。

  #include <iostream>
  #include <stdlib.h>
  using namespace std;
 int findSmallest(int tempArray[], int a_Size);
 int findLargest(int tempArray[], int a_Size);
 int main()
 {  
   int myArray[101];
   int array_Size = 101;

   for (int i = 0; i < 101; i++)
   {
       myArray[i] = rand() % 100 + 1; 
   }

cout << "The largest value in the array is: " << findLargest(myArray, array_Size) << endl;

cout << "The Smallest value in the array is: " << findSmallest(myArray, array_Size) << endl;

   return 0;
}


int findSmallest(int tempArray[], int a_Size)
{ 
       int Smallest = tempArray[0]; 

       for (int i = 0; i < a_Size; i++) 
           {
              if (tempArray[i] < Smallest) 
              {
                 Smallest = tempArray[i]; 
              }
           }

  return Smallest; 
}

创建此函数的原型并对其进行测试，它将找到您数组中的最小数字。

int findLargest(int tempArray[], int a_Size)
{   
       int maxValue = 0;

       for (int i = 0; i < a_Size; i++) 
       {
             if (tempArray[i] > maxValue) 
             {
                maxValue = tempArray[i]; 
             }
       } 

  return maxValue;
}

如果您对它进行原型设计和测试，它会在您的数组中找到最大的元素！

Answer 3

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;

void BasicRecurisonExample();
void getLargest(int tempArray[], int a_Size);
void getSmallest(int tempArray[], int a_Size);
int main()
{
   BasicRecurisonExample();
  return 0;
}




  void BasicRecurisonExample()
  {
     string input;
     int myArray[101];
     int array_Size = 101;

    for (int i = 0; i < 101; i++)
    {
      myArray[i] = rand() % 100 + 1;
    }


    getLargest(myArray, array_Size);

    cout << "\n\n";

    getSmallest(myArray, array_Size);

    cout << "\n\nDo you want to do another, if so type yes: ";
    getline(cin, input);

    if (input == "yes")
    {
       BasicRecurisonExample();
    }
}

  void getSmallest(int tempArray[], int a_Size)
  {
     int Smallest = tempArray[0];

     for (int i = 0; i < a_Size; i++)
     {
        if (tempArray[i] < Smallest)
        {
           Smallest = tempArray[i];
        }
    }
      cout << "The smallest Element is: " << Smallest;
 }



void getLargest(int tempArray[], int a_Size)
{
    int maxValue = 0;

     for (int i = 0; i < a_Size; i++)
     {
        if (tempArray[i] > maxValue)
        {
           maxValue = tempArray[i];
        }
     }
       cout << "The largest element is: " << maxValue;
 }

你正在处理数组和循环，这意味着你需要有逻辑来防止它成为无限的，因为你可以通过删除一个 if 语句来无限地调用它自己......这是递归周期故事的结尾领先的 void 函数直接调用它自己，这是最基本的递归。

没有理由使某些事情过于复杂，例如用函数调用返回将是尾递归。他们不需要这样做......你所要做的就是输入 "yes" 它会再次调用它自己..

Answer 4

分而治之递归算法的工作原理是将工作划分为最简单的情况（通常是一个元素），通过递归地调用自身解决较小的问题，然后组合这些调用的结果。 Mergesort 是分而治之的绝佳例证。

分而治之算法如下：

检查终止条件（start == stop），并将min和max引用参数设置为这个数组值（最简单的情况是一个数组元素。在这种情况下，这个元素是一个元素的最小值和最大值）。
将数组分成左右两半，对这两半进行递归调用，保存到单独的变量中。然后"combine"通过求左右调用的最小值和最大值得到调用的结果

实现该算法的代码：

#include <iostream>
#include <limits>

void maxmin_divide_and_conquer(int arr[], int start, int stop, int &min, int & max)
{
    if (start == stop)
    {
        min = max = arr[start];
    }
    else
    {
        int midpoint = (start + stop) / 2;

        int leftMin;
        int leftMax;
        int rightMin;
        int rightMax;

        maxmin_divide_and_conquer(arr, start, midpoint, leftMin, leftMax);
        maxmin_divide_and_conquer(arr, midpoint + 1, stop, rightMin, rightMax);

        if (leftMin < rightMin)
            min = leftMin;
        else
            min = rightMin;

        if (leftMax > rightMax)
            max = leftMax;
        else
            max = rightMax;
    }
}

int main()
{
    const int size = 10;
    int arr[size] = { 99, 34, 15, 17, 19, 26, 18, 783, 14, -6 };

    int min;
    int max;
    maxmin_divide_and_conquer(arr, 0, size - 1, min, max);

    std::cout << "Divide and Conquer recursive --- " << '\n';
    std::cout << "Minimum is: " << min << '\n' << "Maximum is: " << max << "\n\n";

    return 0;
}

输出：

Minimum is: -6
Maximum is: 783

此处与您的代码的不同之处在于我没有使用任何全局变量（您的 min1 和 max2 在函数中用作全局变量），这将是一个你的问题的很大一部分。递归一般应该使用参数 and/or 局部变量来防止外部信息影响调用（换句话说，递归算法通常是自包含的，避免作为参数传递的数据之外的数据，也避免来自的副作用设置除参数或 return 值以外的数据）。

我也认为不需要 i == j - 1 的额外情况，因为这只是重复了一些用于合并结果的代码。

Answer 5

我认为你的伪代码有问题。为什么 max1 变量在这里用于两个目的？查看我的代码你的版本

#include<bits/stdc++.h>

using namespace std;

int Max(int x,int y){ //genarate the max number between to number
    return x>y?x:y; 
}
int Min(int x,int y){ //genarate the min number between to number
    return x<y?x:y;
}
void maxmin(int x, int y, int *number, int &max, int &min);
int main(){
    //*/
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    //*/
    int nCase,nInput,number[10000],max,min;
    /*
     * nCase denotes the number of test case
     * nInput<10000 number of element in each test case
     * number[10000] number array to find max-min
     * max-min stores the max and min number
     * x, y function arguments
     */ 
    scanf("%d",&nCase);
    for(int k=1; k<=nCase;k++){ //taking number of test cases
        scanf("%d",&nInput); //number of input
        for(int i=0;i<nInput;i++){ //taking input numbers for each case
            scanf("%d",&number[i]);
        }
        maxmin(0,nInput-1,number,max,min); //array as pointer
        printf("Case: %d\n",k);
        printf("The max number is %d\n",max);
        printf("The min number is %d\n",min);
    }
    return 0;
}

void maxmin(int x, int y, int *number, int &max, int &min){
    if(y-x<=1){
        max=Max(number[x],number[y]);
        min=Min(number[x],number[y]);
    }else{
        int mid=(x+y)/2,max1,max2,min1,min2;
        /*
         * mid midle index
         * max1 , max2, min1, min2 temp variables
        */
        maxmin(x,mid,number,max1,min1);
        maxmin(mid+1,y,number,max2,min2);
        max=Max(max1,max2);
        min=Min(min1,min2);
    }
}

输入：

输出：

Case: 1
The max number is 5
The min number is 1
Case: 2
The max number is 6
The min number is 4

如何解决这个寻找最大值和最小值的递归（分而治之）过程？

How to fixed this recursive (divide & conquer) process of finding maximum & minimum?

c++

algorithm

recursion

max

min