The theoretical answers from everyone else are all neat, but let’s be pragmatic. ActionScript provides the tools you need so that you don’t even have to write a loop in this case!
First, note that Math.min() and Math.max() can take any number of arguments. Also, it’s important to understand the apply() method available to Function objects. It allows you to pass arguments to the function using an Array. Let’s take advantage of both:
var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);
Here’s the best part: the “loop” is actually run using native code (inside Flash Player), so it’s faster than searching for the minimum or maximum value using a pure ActionScript loop.
answered Jan 8, 2009 at 23:51
Josh TynjalaJosh Tynjala
5,2253 gold badges23 silver badges25 bronze badges
4
There isn’t any reliable way to get the minimum/maximum without testing every value. You don’t want to try a sort or anything like that, walking through the array is O(n), which is better than any sort algorithm can do in the general case.
answered Jan 8, 2009 at 16:00
Adam BellaireAdam Bellaire
107k19 gold badges148 silver badges163 bronze badges
If
- The array is not sorted
- Finding the min and max is done simultaneously
Then there is an algorithm that finds the min and max in 3n/2 number of comparisons. What one needs to do is process the elements of the array in pairs. The larger of the pair should be compared with the current max and the smaller of the pair should be compared with the current min. Also, one needs take special care if the array contains odd number of elements.
In c++ code (borrowing some code from Mehrdad).
struct MinMax{
int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
MinMax min_max;
int index;
int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
if ( n%2 != 0 ){// if n is odd
min_max.Min = array[start];
min_max.Max = array[start];
index = start + 1;
}
else{// n is even
if ( array[start] < array[start+1] ){
min_max.Min = array[start];
min_max.Max = array[start+1];
}
else{
min_max.Min = array[start+1];
min_max.Max = array[start];
}
index = start + 2;
}
int big, small;
for ( int i = index; i < n-1; i = i+2 ){
if ( array[i] < array[i+1] ){ //one comparison
small = array[i];
big = array[i+1];
}
else{
small = array[i+1];
big = array[i];
}
if ( min_max.Min > small ){ //one comparison
min_max.Min = small;
}
if ( min_max.Max < big ){ //one comparison
min_max.Max = big;
}
}
return min_max;
}
It’s very easy to see that the number of comparisons it takes is 3n/2. The loop runs n/2 times and in each iteration 3 comparisons are performed. This is probably the optimum one can achieve. At this moment, I cannot point to a definite source of that. (But, I think I have seen a proof of that somewhere.)
The recursive solution given by Mehrdad above, probably also achieves this minimal number of comparisons (the last line needs to be changed). But with the same number of comparisons an iterative solution will always beat a recursive solution due to overhead in the function call as he mentioned. However, if one only cares about finding min and max of a few numbers (as Eric Belair does), no one will notice any difference in todays computer with any of the approaches above. For a large array, the difference could be significant.
Though this solution and the solution given by Matthew Brubaker has O(n) complexity, in practice one should carefully asses the hidden constants involved. The number of comparisons in his solution is 2n. The speedup gained with the solution with 3n/2 comparisons as opposed to 2n comparisons would be noticeable.
answered Jul 26, 2009 at 7:41
2
Unless the array is sorted, that’s the best you’re going to get. If it is sorted, just take the first and last elements.
Of course, if it’s not sorted, then sorting first and grabbing the first and last is guaranteed to be less efficient than just looping through once. Even the best sorting algorithms have to look at each element more than once (an average of O(log N) times for each element. That’s O(N*Log N) total. A simple scan once through is only O(N).
If you are wanting quick access to the largest element in a data structure, take a look at heaps for an efficient way to keep objects in some sort of order.
answered Jan 8, 2009 at 16:10
EclipseEclipse
44.6k20 gold badges112 silver badges170 bronze badges
9
You have to loop through the array, no other way to check all elements. Just one correction for the code – if all elements are negative, maxValue will be 0 at the end. You should initialize it with the minimum possible value for integer.
And if you are going to search the array many times it’s a good idea to sort it first, than searching is faster (binary search) and minimum and maximum elements are just the first and the last.
answered Jan 8, 2009 at 16:03
1
Depends on what you call “best.” From a theoretical point of view, you cannot solve the problem in less than O(n) in a deterministic Turing machine.
The naive algorithm is too loop and update min, max. However, a recursive solution will require less comparisons than naive algorithm, if you want to get min, max simultaneously (it isn’t necessarily faster due to function call overhead).
struct MinMax{
public int Min,Max;
}
MinMax FindMinMax(int[] array, int start, int end) {
if (start == end)
return new MinMax { Min = array[start], Max = array[start] };
if (start == end - 1)
return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;
MinMax res1 = FindMinMax(array, start, (start + end)/2);
MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}
The simplest solution would be to sort and get the first and last item, though it’s obviously not the fastest 😉
The best solution, performance-wise, to find the minimum or maximum is the naive algorithm you written (with a single loop).
answered Jan 8, 2009 at 16:06
Mehrdad AfshariMehrdad Afshari
413k90 gold badges850 silver badges788 bronze badges
9
Math.max() is actually as3 code compiled to AVM2 opcodes, and as such is not more “native” than any other as3 code. As a consequence, it is not necessarily the fastest implementation.
Actually, given that it works on Array type, it is slower than carefully written code usign Vector:
I did a quick benchmark comparison of several naive Vector and Array implementations of Math.max, using gskinner’s PerformanceTest (Vector and Array being filled with identical random Numbers).
The fastest Vector implementation appeared to be more than 3x faster than Math.max with recent AIR SDK/release player (flash player WIN 14,0,0,122 RELEASE, compiled with AIR SDK 14):
average 3.5 ms for 1,000,000 values, compared to Math.max() average of 11ms :
function max(values:Vector.<Number>):Number
{
var max:Number = Number.MIN_VALUE;
var length:uint = values.length;
for (var i:uint = 0; i < length ; ++i)
if (values[i] > max)
max = values[i];
return max;
}
Conclusion is that if you are concerned by performance, you should use Vector over Array anywhere you can in the first place, and not always rely on default implementations, especially when they force the use of Array
PS:same implementation with a for each() loop is 12x slower …!
answered Aug 27, 2014 at 13:47
jaubouxjauboux
8886 silver badges12 bronze badges
This depends on real world application requirements.
If your question is merely hypothetical, then the basics have already been explained. It is a typical search vs. sort problem. It has already been mentioned that algorithmically you are not going to achieve better than O(n) for that case.
However, if you are looking at practical use, things get more interesting. You would then need to consider how large the array is, and the processes involved in adding and removing from the data set. In these cases, it can be best to take the computational ‘hit’ at insertion / removal time by sorting on the fly. Insertions into a pre-sorted array are not that expensive.
The quickest query response to the Min Max request will always be from a sorted array, because as others have mentioned, you simply take the first or last element – giving you an O(1) cost.
For a bit more of a technical explanation on the computational costs involved, and Big O notation, check out the Wikipedia article here.
Nick.
answered Jan 8, 2009 at 16:18
NickNick
2,2852 gold badges14 silver badges26 bronze badges
If you are building the array once and want to find the maximum just once, iterating is the best you can do.
When you want to modify the array and occasionally want to know the maximum element, you should use a Priority Queue. One of the best data structures for that is a Fibonacci Heap, if this is too complicated use a Binary Heap which is slower but still good.
To find minimum and maximum, just build two heaps and change the sign of the numbers in one of them.
answered Jan 8, 2009 at 16:12
martinusmartinus
17.7k15 gold badges72 silver badges92 bronze badges
Please take into account that sorting the array will only be faster that looping up to certain size of the array. If your array is small (and it will be like that any time) then your solution is perfectly fine. But if it might get too large you should use a conditional to use the sort approach when the array is small, and the normal iteration when it is too large
answered Jan 28, 2009 at 21:21
If you want to find both the min and max at the same time, the loop can be modified as follows:
int min = int.maxValue;
int max = int.minValue;
foreach num in someArray {
if(num < min)
min = num;
if(num > max)
max = num;
}
This should get achieve O(n) timing.
answered Jan 8, 2009 at 16:29
Matthew BrubakerMatthew Brubaker
3,0971 gold badge21 silver badges18 bronze badges
Shortest way :
Math.min.apply(null,array); //this will return min value from array
Math.max.apply(null,array); //this will return max value from array
otherway of getting min & max value from array
function maxVal(givenArray):Number
{
var max = givenArray[0];
for (var ma:int = 0; ma<givenArray.length; ma++)
{
if (givenArray[ma] > max)
{
max = givenArray[ma];
}
}
return max;
}
function minVal(givenArray):Number
{
var min = givenArray[0];
for (var mi:int = 0; mi<givenArray.length; mi++)
{
if (givenArray[mi] < min)
{
min = givenArray[mi];
}
}
return min;
}
As you can see, the code in both of these functions is very similar. The function sets a variable – max (or min) and then runs through the array with a loop, checking each next element. If the next element is higher than the current, set it to max (or min). In the end, return the number.
answered Feb 6, 2014 at 3:39
sajansajan
1,3451 gold badge14 silver badges18 bronze badges
Below is Solution with o(n):-
public static void findMaxAndMinValue(int A[]){
int min =0, max = 0;
if(A[0] > A[1] ){
min = A[1];
max = A[0];
}else{
max = A[1];
min = A[0];
}
for(int i = 2;i<A.length ;i++){
if(A[i] > max){
max = A[i];
}
if(min > A[i]){
min = A[i];
}
}
System.out.println("Maxinum Value is "+min+" & Minimum Value is "+max);
}
answered Jun 17, 2015 at 18:06
Ajay KumarAjay Kumar
4,6681 gold badge38 silver badges42 bronze badges
Amazed no-one mentioned parallelism here.
If you got really a huge array, you can use parallel-for, on sub ranges.
In the end compare all sub-ranges.
But parallelism comes width some penalty too, so this would not optimize on small arrays. However if you got huge datasets it starts to make sense, and you get a time division reduction nearing the amount of threads performing the test.
answered Mar 21, 2018 at 9:26
PeterPeter
2,0071 gold badge20 silver badges45 bronze badges
Find max values from a array
Let’s see how to obtain min, max values by using a single funtion
public void findMaxValue(){
int[] my_array = {1,2,,6,5,8,3,9,0,23};
int max = my_array[0];
for(int i=1; i<my_array.length; i++)
{
if(my_array[i] > max)
max = my_array[i];
}
return max;
}
same thing can do for find min value
answered Oct 24, 2018 at 16:00
After reading everyone’s comments (thank you for your interest), I found that the “best” way (least amount of code, best performing) to do this was to simply sort the Array, and then grab the first value in the Array:
var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];
myArray.sort(Array.NUMERIC);
var minValue:int = myArray[0];
This also works for an Array of Objects – you simply use the Array.sortOn() function and specify a property:
// Sample data
var myArray:Array /* of XML */ =
[
<item level="2" name="a" />
<item level="3" name="b" />
<item level="3" name="c" />
<item level="2" name="d" />
<item level="5" name="e" />
]
// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);
var lowestLevel:int = myArray[0].@level;
I hope this helps someone else someday!
answered Jan 23, 2009 at 22:34
Eric BelairEric Belair
10.6k13 gold badges75 silver badges116 bronze badges
В этом посте мы обсудим, как найти минимальный и максимальный элемент массива в C++.
1. Наивное решение
Наивное решение — написать собственную процедуру для этой простой задачи. Идея состоит в том, чтобы линейно пройти массив, используя простой цикл for или цикл for на основе диапазона. Затем для каждого обнаруженного элемента мы сравниваем его с минимальным или максимальным элементом, найденным до сих пор, и заменяем максимальный элемент, найденный до сих пор, текущим элементом, если он меньше по значению, и минимальный элемент, найденный до сих пор, текущим элементом, если он больше по стоимости.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <climits> #include <algorithm> using namespace std; int main() { int arr[] = { 4, 2, 1, 6, –8, 5 }; int min = INT_MAX, max = INT_MIN; for (int i: arr) { if (i < min) { min = i; } if (i > max) { max = i; } } std::cout << “The min element is “ << min << std::endl; std::cout << “The max element is “ << max << std::endl; return 0; } |
Скачать Выполнить код
результат:
The min element is -8
The max element is 6
2. Использование minmax_element() функция
Рекомендуемое решение — использовать std::minmax_element найти наименьший и наибольший элементы массива. Он возвращает пару итераторов, первое значение которых указывает на минимальный элемент, а второе значение указывает на максимальный элемент. Он определен в <algorithm> заголовок.
|
#include <iostream> #include <algorithm> using namespace std; int main() { int arr[] = { 4, 2, 1, 6, –8, 5 }; std::pair<int*, int*> minmax = std::minmax_element(std::begin(arr), std::end(arr)); std::cout << “The min element is “ << *(minmax.first) << std::endl; std::cout << “The max element is “ << *(minmax.second) << std::endl; return 0; } |
Скачать Выполнить код
результат:
The min element is -8
The max element is 6
3. Использование min_element() с max_element() функция
Стандартная библиотека C++ также предоставляет отдельные функции. min_element() а также max_element() чтобы найти наименьший и наибольший элементы в массиве соответственно.
|
#include <iostream> #include <algorithm> using namespace std; int main() { int arr[] = { 4, 2, 1, 6, –8, 5 }; int *min = std::min_element(std::begin(arr), std::end(arr)); int *max = std::max_element(std::begin(arr), std::end(arr)); std::cout << “The min element is “ << *min << std::endl; std::cout << “The max element is “ << *max << std::endl; return 0; } |
Скачать Выполнить код
результат:
The min element is -8
The max element is 6
Вот и все, что касается нахождения минимального и максимального значений в массиве в C++.
13.1. Поиск максимального (минимального) элемента в массиве
|
Очень часто для решения задачи требуется находить не заданный элемент массива, а максимальный (наибольший) или минимальный (наименьший) элемент. Рассмотрим задачу нахождения максимального элемента. Если в массиве один-единственный элемент, то он и есть максимальный. Если элементов больше одного, то максимальным в массиве из i элементов является максимум из a[i] и максимального среди первых i – 1 элементов. Находить максимум будем последовательно, сравнивая текущий элемент с максимумом, найденным на предыдущем шаге. Если текущий элемент больше, то значение максимума, найденное на предыдущем шаге, нужно обновить (пример 13.1). Данный алгоритм находит значение максимального элемента, но не позволяет определить, на каком месте в массиве расположен этот максимальный элемент. Будем использовать переменную n_max для хранения индекса максимального элемента. Значение переменной n_max будет изменятся тогда, когда изменяется значение максимального элемента (пример 13.2). Если в массиве несколько элементов имеют максимальное значение, то значением переменной n_max будет индекс первого из них. Если использовать условие a[i] >= max, то переменная n_max будет хранить индекс последнего из максимальных элементов. Если известен индекс i элемента массива, то значение этого элемента можно получить, обратившись к элементу по индексу: a[i]. Поэтому при поиске максимального элемента достаточно хранить только его индекс n_max. Значение максимального элемента — a[n_max] (пример 13.3). Поиск минимального элемента осуществляется аналогично. В программе достаточно заменить знак > в условии оператора ветвления на знак < (пример 13.4). Имя переменной для хранения номера минимального элемента — n_min. |
Пример 13.1. V. Программа: #include <iostream> #include <vector> using namespace std; int main() { int n; cout << “n = “; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; //поиск максимального элемента int Max = a[0]; for (int i = 1; i < n; i++) if (a[i] > Max) Max = a[i]; cout << “max = “ << Max; cout << endl; return 0; } VI. Тестирование.
Пример 13.2. V. Программа: #include <iostream> #include <vector> using namespace std; int main() { int n; cout << “n = “; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; //поиск максимального элемента int Max = a[0], n_max = 0; for (int i = 1; i < n; i++) if (a[i] > Max){ Max = a[i]; n_max = i; } cout << “max = “ << Max; cout << ” ego mesto “ << n_max; cout << endl; return 0; } VI. Тестирование.
Пример 13.3. Фрагмент программы: int n_max = 0; for (int i = 1; i < n; i++) if (a[i] > a[n_max]) n_max = i; cout << “max = “ << a[n_max]; cout << ” ego mesto “ << n_max; Пример 13.4. Фрагмент программы: int n_min = 0; for (int i = 1; i < n; i++) if (a[i] < a[n_min]) n_min = i; |
13.2. Решение задач с использованием алгоритма поиска максимального (минимального) элементов
|
Пример 13.5. В массиве хранится информация о результатах спортсменов, участвовавших в лыжной гонке. Определить результат победителя и его номер. Данные прочитать из текстового файла. Этапы выполнения задания I. Исходные данные: массив a — числа, являющиеся временем прохождения трассы, количество спортсменов — n. II. Результат: a[n_min] — минимальное время, n_min — номер победителя. III. Алгоритм решения задачи. 1. Ввод исходных данных. IV. Описание переменных: n, n_min – int, а – vector <double>. Пример 13.6. Определить, сколько раз в линейном массиве встречается элемент, равный минимальному. Этапы выполнения задания I. Исходные данные: массив а, количество чисел n. II. Результат: a[n_min] — минимальный элемент, k — количество минимальных. III. Алгоритм решения задачи. 1. Ввод исходных данных. IV. Описание переменных: n, n_min, k — int, а – vector <int>. Пример 13.7. Задан массив из слов. Найти в нем самое длинное и самое короткое слово. Этапы выполнения задания I. Исходные данные: массив а, количество cлов n. II. Результат: a[n_min] — короткое слово, a[n_max] — длинное слово. III. Алгоритм решения задачи. 1. Ввод исходных данных. IV. Описание переменных: n, n_min, n_max – int, а – vector <string>. [1] Сравнение строк осуществляется лексикографически: s1 < s2, если для первого несовпадающего символа с номером i верно, что s1[i] < s2[i], или все символы строк совпадают, но s1 короче s2. |
Пример 13.5. V. Программа: #include <iostream> #include <fstream> #include <vector> using namespace std; int main() { setlocale(0,“”); ifstream fin(“input.txt”); int n; fin >> n; vector <double> a(n); for (int i = 0; i < n; i++) fin >> a[i]; //поиск минимального элемента int n_min = 0; for (int i = 1; i < n; i++) if (a[i] < a[n_min]) n_min = i; cout << “победитель — лыжник №”; cout << n_min + 1 << endl; cout << “его время – “<< a[n_min]; cout << endl; return 0; } IV. Тестирование.
Пример 13.6. V. Программа: #include <iostream> #include <vector> using namespace std; int main() { int n; cout << “n = “; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; //поиск минимального элемента int n_min = 0; for (int i = 1; i < n; i++) if (a[i] < a[n_min]) n_min = i; //подсчет количества int k = 0; for (int i = 0; i < n; i++) if (a[i] == a[n_min]) k++; cout << “min = “<< a[n_min]; cout << endl << “vstretilsja “; cout << k << ” raz” << endl; return 0; } VI. Тестирование.
Пример 13.7. V. Программа: #include <iostream> #include <vector> #include <string> using namespace std; using namespace std::__cxx11; int main() { int n; cout << “n = “; cin >> n; vector <string> a(n); for (int i = 0; i < n; i++) cin >> a[i]; //поиск минимального слова int n_min = 0; for (int i = 1; i < n; i++) if (a[i].length() < a[n_min].length()) n_min = i; //поиск максимального слова int n_max = 0; for (int i = 1; i < n; i++) if (a[i].length() > a[n_max].length()) n_max = i; cout << “min – “<< a[n_min]; cout << “, max – “<< a[n_max]; cout << endl; return 0; } VI. Тестирование.
|
Вопросы к параграфу
 |
1. Какой элемент массива является максимальным? Какой минимальным? 2. Как найти максимальный элемент в массиве? 3. Как найти минимальный элемент? 4. Каким образом определить номер первого элемента, равного максимальному? 5. Как определить номер последнего элемента, равного минимальному? |
Упражнения
1. Измените программы из примеров 13.1 и 13.2 так, чтобы находился минимальный элемент в массиве.
2. Для примера 13.5 выполните перечисленные задания.
1. Найдите номер спортсмена, пришедшего на финиш последним.
2. Определите, был ли победитель единственным или есть еще лыжник, прошедший трассу с таким же результатом (см. пример 13.6).
3. Добавьте еще один массив и введите в него фамилии спортсменов. Реализуйте пункты 1 и 2 так, чтобы выводилась фамилия, а не номер (см. пример 12.9).
3. Напишите программу, которая заменит в массиве нулями все элементы, равные минимальному.
4. Напишите программу, которая заменит в массиве нулями все элементы, стоящие перед максимальным. Предполагается, что в массиве единственный максимальный элемент.
5. Напишите программу, которая заменит нулями все элементы в массиве, стоящие после минимального. Если минимальных элементов несколько, то заменять нужно элементы, стоящие после последнего минимального.
6. Напишите программу, которая определит, какой из элементов — минимальный или максимальный — встречается в массиве раньше (имеет меньший индекс).
7. Напишите программу, которая определит, какой из элементов — минимальный или максимальный — встречается в массиве чаще.
8. Напишите программу, которая запишет в новый массив те элементы из исходного, которые расположены между минимальным или максимальным (по индексам).
9. В массиве хранится информация о стоимости автомобилей. Определите стоимость самого дорогого автомобиля и его номер в массиве. Если есть несколько таких автомобилей, то выведите все номера.
10. В массиве хранится информация о среднесуточной температуре декабря. Определите, сколько в декабре было дней с самой низкой и с самой высокой температурой.
11. Размеры n прямоугольников хранятся в двух массивах (длина и ширина). Найдите прямоугольник с минимальным периметром. (Вывести номер прямоугольника и значение периметра.)
12. Известны данные о массе (в кг) и объеме (в см3) n предметов, изготовленных из различных материалов. Найдите предметы с минимальной и максимальной плотностями. Вывести номер предмета и значение плотности.
13. Задан массив из слов. Найдите в нем самое длинное слово, заканчивающееся буквой «а».
14. Задан массив из слов. Найдите в нем самое короткое слово, начинающееся с заглавной буквы.
15. Задан массив из слов. Найдите в нем слово, в котором максимальное количество гласных букв. Если таких слов несколько, выведите все.
16. Задан массив из слов. Найдите в нем слово, в котором минимальное количество согласных букв. Если таких слов несколько, то выведите самое длинное из них.
Нахождение максимального или минимального числа в массиве.
Часто в задачах возникает необходимость найти одно самое большее (или самое меньшее) число в множестве (массиве) элементов. Для этого используется простой алгоритм использующий один цикл и одну переменную для хранения этого числа.
Для решения данной задачи, можно описать следующим алгоритмом:
| Запись решения на естественном языке: 1) Начало программы 2) Получаем множество чисел в котором будем искать (максимальное или минимальное ) значение. 3) Получаем длину массива чтобы запустить цикл перебора элементов 4) Объявляем переменную которая будет хранить найденное (максимальное или минимальное) число. 5) Помещаем в данную переменную первый элемент массива. 5) Описываем цикл с первого элемента который будет перемещаться по массиву и выбирать числа. 6) Внутри цикла сравниваем выбранное число из цикла с числом в переменной. а) если мы ищем максимум: 1) если число в буфере меньше числа в переменной то перезаписываем переменную этим числом 2) если число в буфере больше числа в переменной то пропускаем элемент. б) если мы ищем минимум: 1) если число в буфере больше числа в переменной то перезаписываем переменную этим числом. 2) если число в буфере меньше числа в переменной то пропускаем число. 7) выбираем в цикле следующий элемент массива. Если элементы есть то переходим на пункт 6 Если элементов нет значит переменная хранит (Максимальное или Минимальное число). 8) конец работы алгоритма. |
Запись алгоритма в виде блок схем:
|
Разберем задачу по шагам:
Шаг 1
Для решения данной задачи из полученного множества выбирается самый 1 элемент который считается самым меньшим или большим в зависимости от задачи.
 |
Пример кода Допустим у нас массив A={2, 3, 4, 4, 5, 0} Тогда объявляем переменную для буфера и присваиваем ей 1 элемент массива Int Buf=A[0]; |
Шаг 2
Запускаем цикл начиная с 1 элемента и последовательно сравниваем число из буфера с выбранным элементом множества
|
|
Если элемент в буфере меньше выбранного элемента то записываем в буфер это значение
|
Если нет то ничего не делаем |
Далее по аналогии выполняем сравнение со всеми элементами массива
Реализуем данный метод на языке программирования C++
Для этого запустим Embarcadero Rad Studio XE 3
Создаем новый консольный проект для этого выполняем следующие действия.
| Выбираем пункт меню File -> New -> Other…
|
Далее выбираем язык программирования и ярлык консольного приложения
|
| В мастере создания проекта просто нажимаем OK
|
Создается шаблон проекта все что написала среда разработки нужно оставлять так как есть
Шаг 1
Добавляем библиотеки взаимодействия с консолью
Шаг 2
Объявим переменные (глобальные) которые будут видны всем функциями и процедурам описанным ниже.
Шаг 3
Объявим функцию получения минимума и максимума которая будет возвращать минимум или максимум из массива значений.
Функция будет принимать 1 параметр если он будет 0 будем искать минимум если 1 то максимум
Шаг 3
Внутри функции опишем логику работы алгоритма:
Шаг 3.1: Объявим переменную для хранения результата и сразу присвоим ей 0 элемент массива
Шаг 3.2: Объявим цикл который будет перебирать элементы массива c 1 элемента так как 0 мы уже сохранили в буфер
Шаг 3.2: На основе переданного параметра будем решать какое значение мы ищем Min или Max
a) если пользователь передал 0 значит ищем минимум
б) Если число в буфере больше выбранного элемента массива то записываем выбранное число из массива в буфер
в) если пользователь передал 1 значит ищем максимум
г) Если число в буфере меньше выбранного элемента массива то записываем выбранное число из массива в буфер
Шаг 3.3: После завершения цикла значение буфера будет содержать искомое значение (минимальное или максимальное число). Данное значение функция будет возвращать для этого воспользуемся оператором return
Шаг 4: В функции _tmain объявим функцию которая будет хранить результат поиска минимума или максимума.
Шаг 5: Вызываем функцию для нахождения минимума . И присвоим ее результат нашей переменной.
Шаг 6: Выведем результат в консоль, чтобы она не закрывалась сразу вызовем функцию ожидания нажатия клавиши getch().
Посмотрим на массив правда ли – 100 является самым маленьким 
так и есть.
Шаг 7: Вызываем функцию для нахождения максимума. Просто поменяем значение 0 на 1;
Шаг 8: Выведем результат в консоль.
Посмотрим на массив правда ли 478 является самым большим 
так и есть.
Задание для самостоятельной работы Задание
Задачи по нахождению минимального и/или максимального элемента в массиве очень часто встречаются в различных учебных пособиях по программированию и, как правило, вызывают трудности у начинающих программистов или просто студентов, получивших такое задание.
В данной статье вы узнаете, как написать реализацию программы на языке C++, которая находит максимальный и минимальный элемент в массиве и выводит на экран. А узнать множество решений других задач можно в разделе с решениями задач по программированию на языке C++.
Что такое максимальный и минимальный элемент массива
Для начала поймем, что же такое максимальный или минимальный элемент в массиве? Всё просто, максимальный элемент массива — это элемент, который имеет самое большое числовое значение, а минимальный элемент массива — это элемент, имеющий самое маленькое значение.
Пример: в массиве, состоящем из таких элементов: 3, 1, 0, -4, 16, 2 — максимальный элемент равен 16, т.к. это число больше других, а минимальный элемент равен -4, т.к. оно меньше остальных.
Поняв это, можно приступить к решению задачи.
Алгоритм решения задачи
— Инициализация массива, переменных, хранящих минимальное и максимальное значение.
— Заполнение массива случайными числами при помощи цикла и функции, возвращающей случайные числа.
— Вывод массива.
— Сравнение каждого элемента массива: Если элемент больше переменной с максимальным значением, то значение записывается в переменную; Если элемент меньше переменной с минимальным значением, то значение записывается в переменную.
— Вывод переменных с максимальным и минимальным элементом.
Алгоритм решения на языке C++
Для начала нужно подключить заголовок ввода/вывода <iostream>, заголовок стандартных функций <cstdlib> в ней имеется функция rand(), которая позволит заполнить массив случайными числами. Заполнение каждого элемента массива вручную требует времени, его можно сэкономить автоматизировав процесс. Подключаем пространство имён std. Создаём константу N, она будет определять количество элементов в массиве.
#include <iostream>
#include <cstdlib>
using namespace std; //Пространство имён std
const int N = 10;//Количество элементов в массиве
int main()
{
return 0;
}
В теле функции main() инициализируем массив целых чисел из N лементов, целочисленные переменные max и min, они будут хранить значение максимального и минимального элементов массива соответственно.
int mass[N], max, min;
Теперь заполним массив случайными числами. Для этого используем цикл от 0 до N (не включительно), который пройдется по каждому элементу массива и поместит случайное значение от 0 до 98. Это можно сделать, использовав функцию rand(), которая возвращает случайное число. Поделить возвращаемое значение на 99 и внести в ячейку остаток от деления, таким образом значение ячейки будет иметь значение в диапазоне от 0 до 99(не включая 99, т.к. остаток от деления не может быть кратным делителю). При этом выведем значения элементов массива на экран.
cout << "Элементы: |";
for(int r = 0; r<N; r++) // Цикл от 0 до N
{
mass[r] = rand()%99; // Заполнение случайным числом
cout << mass[r] << "|"; // Вывод значения
}
cout << endl;
В результате программа выведет на экран значения элементов массива, разделенное вертикальными чертами:
Элементы: |28|43|72|79|23|70|55|39|69|1|
Обратите внимание! Если вы программируете под Windows и у Вас не отображаются русские символы в консоли, то советую Вам почитать о решении этой проблемы в статье Русские символы(буквы) при вводе/выводе в консоль на C++.
Далее определим максимальный и минимальный элемент в массиве, для этого вновь пройдемся по массиву циклом. При помощи условия определим максимальный и минимальный элемент массива.
Перед циклом нужно будет занести первый элемент массива в переменные min и max, они будут хранить минимальное и максимальное значение изначально, а во время цикла поменяют его, если найдётся значение меньше для min или больше для max.
max = mass[0];//Помещаем значения 1-го элемента
min = mass[0];//массива в переменные
for(int r = 1; r<N; r++)
{
if(max < mass[r]) max = mass[r]; //если значение элемента больше значения переменной max, то записываем это значение в переменную
if(min > mass[r]) min = mass[r]; //аналогично и для min
}
После цикла выведем значения min и max.
cout << "Min: " << min << endl; cout << "Max: " << max << endl;
После компиляции и запуска прогамма выводит следующее
Элементы: |28|43|72|79|23|70|55|39|69|1| Min: 1 Max: 79
Пробегаемся по элементам массива глазами и видим, что минимальное значение — 1, а максимальное — 79. Переменные min и max имеют эти же значения соответственно, следовательно алгоритм работает.
Весь листинг программы на C++
#include <iostream>
#include <cstdlib>
using namespace std;
const int N = 10;
int main()
{
int mass[N], max, min;
cout << "Элементы: |";
for(int r = 0; r<N; r++)
{
mass[r] = rand()%99;
cout << mass[r] << "|";
}
cout << endl;
max = mass[0];
min = mass[0];
for(int r = 1; r<N; r++)
{
if(max < mass[r]) max = mass[r];
if(min > mass[r]) min = mass[r];
}
cout << "Min: " << min << endl;
cout << "Max: " << max << endl;
return 0;
}
