欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定n个数,要求比较次数1.5n同时找出最大值和最小值

程序员文章站 2023-12-27 18:16:09
...

写出一个算法,对给定的n个数的序列,返回序列中的最大和最小的数.

设计出一个算法,只需要执行1.5n次比较就能找到序列中最大和最小的数吗?能否再少?

分析:要求比较次数为1.5n,使用一般的逐个遍历每个元素然后判断其是否为最大最小值是需要2n次的比较的,所以这样的方法是行不通的。现在考虑采用,每次从数组中取出两个元素,判断其大小,然后再分别判断其是否是最大或最小值,这样一次处理两个元素,每一次比较3次,最终的比较次数就是n/2*3=1.5n。C语言代码如下:

#include <stdio.h>

#define	MIN	-1
#define MAX	65535

void find_max_min(int num[], int len)
{
  int i, j;
  int max = MIN;
  int min = MAX;
  int tmax, tmin;
  int count = 0; /*用来统计比较次数*/

  i = 0;
  j = len - 1;
  while(i <= j)
  {
    if(num[i] < num[j])
    {
      tmax = num[j];
      tmin = num[i];
      count ++;
    }
    else
    {
      tmax = num[i];
      tmin = num[j];
      count ++;
    }

    if(min > tmin)
      min = tmin;
    if(max < tmax)
      max = tmax;
    count += 2; /*上面的两次比较*/
    i ++;
    j --;
  }
  printf("The max number is: %d.\n", max);
  printf("The min number is: %d.\n", min);
  printf("Compare number is: %d.\n", count);
}

int main()
{
  int num[10] = {2, 4, 5, 6, 8, 3, 7, 1, 9, 10};
  find_max_min(num, 10);

  return 0;
}

 

上一篇:

下一篇: