Question

用C++编程 ： 求数组的最大最小值

求数组（10个整数）的最大最小值

要求1.MAX（）MIN（）函数来实现
2. 只用一个函数返回最大最小值（用“引用”)
在线等 50分钟
编程环境是VC 6.0 你们的编程存在错误

Answer 1

可以使用分治法(Divide and couquer)来求数组的最大最小值。
将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。

程序代码如下：

#include <iostream>
#include <cassert>
#include <algorithm>
#include <functional> // For greater<int>( )

// 分治法实现
std::pair<int, int> searchMaxMin(int a[], int low, int high)
{
assert(a != NULL && high>=low);
if (high - low <= 1)
return a[high] > a[low] ? std::make_pair(a[high], a[low]) : std::make_pair(a[low], a[high]);

int mid = low + (high - low)/2;
std::pair<int, int> L = searchMaxMin(a, low, mid);
std::pair<int, int> R = searchMaxMin(a, mid+1, high);

int maxValue = (L.first > R.first ? L.first : R.first);
int minValue = (L.second < R.second ? L.second : R.second);

return std::make_pair(maxValue, minValue);
}

// 查找最大和第二大数字。不用此法，求数组中的第K大数值时间复杂度为
std::pair<int, int> searchMaxSecond(int a[], int low, int high)
{
assert(a != NULL && high>=low);
if (high - low <= 1)
return a[high] > a[low] ? std::make_pair(a[high], a[low]) : std::make_pair(a[low], a[high]);

int mid = low + (high - low)/2;
std::pair<int, int> L = searchMaxSecond(a, low, mid);
std::pair<int, int> R = searchMaxSecond(a, mid+1, high);

int maxValue = 0;
int secondValue = 0;

if (L.first > R.first) {
maxValue = L.first;
secondValue = (L.second > R.first ? L.second : R.first);
} else {
maxValue = R.first;
secondValue = (L.first > R.second ? L.first : R.second);
}

return std::make_pair(maxValue, secondValue);
}

int main()
{
int a[] = {6, 5, 8, 3, 9, 7};
const int N = sizeof(a)/sizeof(a[0]);
std::pair<int, int> maxMin = searchMaxMin(a, 0, N-1);

assert( maxMin.first == *std::max_element(a, a + N) );
assert( maxMin.second == *std::min_element(a, a + N) );
assert( maxMin.first == *(std::minmax_element(a, a+N).second) &&
maxMin.second == *(std::minmax_element(a, a+N).first) );

std::pair<int, int> maxSecond = searchMaxSecond(a, 0, N-1);
std::partial_sort(a, a+2, a+N, std::greater<int>());
assert( maxSecond.first = a[0] );
assert( maxSecond.second = a[1] );
}

Answer 2

#include <iostream>
using namespace std;
void main()
{
int a[10],i,max,min;
cout<<"Please input ten integers"<<endl;
for(i=0;i<10;i++)
{
cin>>a[i];
}
max=a[0];
min=a[0];
for(i=0;i<10;i++)
{
if(a[i]>max)
{max=a[i];}
if(a[i]<min)
{min=a[i];}
}
cout<<"The largest number is "<<max<<endl;
cout<<"The smallest number is "<<min<<endl;
}

Answer 3

#include<iostream>
void mn(int &iMax,int &iMin,int &array)
{
iMax=max(array);
iMin=min(array);
}

Answer 4

#include "stdafx.h"

int a [] = {1,4,7,9,0,5,3,2,8,6};

int MAX()
{
int max = a[0];

for (int i=1; i<=9; i++)
{
if (max<a[i])
{
max = a[i];
}
}

return max;
}

int MIN()
{
int min = a[0];

for (int i=1; i<=9; i++)
{
if (min>a[i])
{
min = a[i];
}
}

return min;
}

void MaxMin(int &max, int &min)
{
max = a[0];
min = a[0];
for (int i=1; i<=9; i++)
{
if (min>a[i])
{
min = a[i];
}

if (max<a[i])
{
max = a[i];
}
}
}

int main()
{
int min = MIN();
int max = MAX();

printf("Min = %d, Max = %d\n", min, max);

int min1 = 0;
int max1 = 0;

MaxMin(max1, min1);
printf("Min = %d, Max = %d\n", min1, max1);
return 0;
}

Answer 5

VC6.0下 编译通过........

#include<stdio.h>

int MAX(int a[10])
{
int MAX=a[0];
for(int i=1;i<10;i++)
MAX=a[i]>MAX?a[i]:MAX;
return MAX;
}

int MIN(int a[10])
{
int MIN=a[0];
for(int i=1;i<10;i++)
MIN=a[i]<MIN?a[i]:MIN;
return MIN;
}

void MaxMin(int a[10],int &MAX,int &MIN)
{
MAX=a[0];
MIN=a[0];
for(int i=1;i<10;i++)
{
MIN=a[i]<MIN?a[i]:MIN;
MAX=a[i]>MAX?a[i]:MAX;
}
}

void main()
{
int max,min;
int a[10]={3,56,78,2,0,34,65,4,2,89};
printf("MAX=%d\n",MAX(a));
printf("MIN=%d\n",MIN(a));
MaxMin(a,max,min);
printf("max=%d,min=%d\n",max,min);

}