首页 文章

在单个递归函数中查找数组的最大值和最小值

提问于
浏览 次
3

下面的程序使用Divide and Conquer范例，并使用Merge Sort的思想递归地查找数组的最大和最小元素 . 这是一个要求递归执行的任务，我编写了解决方案，但我的问题是它是否最小化了查找最小值和最大值所需的比较次数？

#include <stdio.h>
#include <limits.h>


void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
  //returns the maximum element of the array
  int mid;
  int left, right;

  if(lower == upper){
    if(ptr[lower] > *maximum)
      {
         *maximum = ptr[lower];
      }
    if(ptr[lower] < *min)
      {
         *min = ptr[lower];
      }
    return;
  }

  mid = (lower+upper) /2;

  max(ptr, lower, mid, maximum, min);
  max(ptr, mid+1, upper, maximum, min);
}

int main()
{
  int n;
  int i;

  int *ptr;

  int maximum=-1;
  int minimum=INT_MAX;


  printf("\nEnter the size of the array : ");
  scanf("%d", &n);

  ptr = (int *) malloc(sizeof(int)*n);

  printf("Enter the contents of the array : ");

  for(i=0 ; i<n; i++)
    scanf("%d", &ptr[i]);

  max(ptr,0,n-1,&maximum,&minimum);

  printf("\n Maximum element is : %d", maximum);
  printf("\n Minimum element is : %d", minimum);

  free(ptr);

  return 0;
}
c arrays algorithm recursion

3 回答

  • 0

    使用else来最小化比较 . 如果你找到一个新的最大值，那么它不能是最小值（如果你想要的话，反之亦然）：

    if (ptr[lower] > *maximum) {
  *maximum = ptr[lower];
} else {
  if (ptr[lower] < *min) {
    *min = ptr[lower];
}

    为此，您需要将min和max初始化为数组中的任何值：

    minimum = maximum = ptr[0];

    请注意，在您的情况下，递归模式是绝对无用的，对数组的简单增量解析就足够了，并且可以节省大量操作（计算中间值，测试基本情况，传递参数，函数调用） . 另一种方法是在扫描输入时计算结果......

    回复于
  • 2

    它是否最小化了找到最小值和最大值所需的比较次数？

    Short answer: no

    您的代码实际上需要

    n * 4 - 1

    比较 n 是数组中的项目数 .

    上面的计数1比较检查 lower==upper ，如果它评估真2另外比较检查 max 和 min

    如果您只需要使用for循环从开头到结尾解析数组，那么您需要

    n * 2

    比较 .

    但是等等：因为在每次迭代时你还需要一个for循环，所以还有一个额外的比较来检查循环是否结束 .

    实际上有

    n * 3

    比较 .

    您发布的代码效率不高，此外，您必须在每次调用 max() 时计算 mid 加上递归函数调用的开销 .

    由于你有一个无序的数组或数字，你必须找到最小和最大的最快解决方案（正如其他人指出）迭代数组 .

    如果你想要一个证明你可以测试它...

    这是输出：

    Elements count : 10000
Maximum element is : 99964
Minimum element is : 9
Number of comparisons : 39999

    下面是嵌入测试的代码

    （我刚刚添加了一个在每次比较之前递增的全局 g_comparisons - 也是以编程方式使用随机值完成数组填充的过程）

    #include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int g_comparisons = 0;

void max(int *ptr, int lower, int upper, int *maximum, int *min)
{
    //returns the maximum element of the array
    int mid;
    g_comparisons ++;
    if(lower == upper){
        g_comparisons += 2;
        if(ptr[lower] > *maximum)
        {
            *maximum = ptr[lower];
        }
        if(ptr[lower] < *min)
        {
            *min = ptr[lower];
        }
        return;
    }

    mid = (lower+upper) /2;

    max(ptr, lower, mid, maximum, min);
    max(ptr, mid+1, upper, maximum, min);
}

int main()
{
    int n;
    int i;

    int *ptr;

    int maximum=-1;
    int minimum=INT_MAX;


    //printf("\nEnter the size of the array : ");
    //scanf("%d", &n);

    n = 10000;

    ptr = (int *) malloc(sizeof(int)*n);

    // printf("Enter the contents of the array : ");

    for(i=0 ; i<n; i++)
    {
    //    scanf("%d", &ptr[i]);
        ptr[i] = rand()%100000;
    }

    max(ptr,0,n-1,&maximum,&minimum);

    printf("\n Elements count : %d" , n);

    printf("\n Maximum element is : %d", maximum);
    printf("\n Minimum element is : %d", minimum);

    printf("\n Number of comparisons : %d\n", g_comparisons);

    free(ptr);

    return 0;
}
    回复于
  • 2

    有两件事我想指出1.如果数组已排序，那么查找最小值和最大值需要O（1）时间 . 2.如果数组不是按排序顺序排列，那么如果您的目标只是找到最小和最大数字，那么排序对您没有帮助 . 原因如下：任何基于比较的排序算法都需要Ω（nlogn）时间，而最大值和最小值可以在单个for循环迭代中一起找到 . 每次比较下一个元素到目前为止发现的最大值和最小值 . 所以只使用一个for循环 . 这很简单

    如果你的任务强制你以递归方式执行，那么它仍然可以在O（n）比较中完成 . 只需代替编写for循环，就可以在循环中编写的代码中稍作修改使用recurssion函数 .

    回复于

相关问题