Принцип нахождения максимального и минимального элементов массива одинаков. Поэтому рассмотрим его на примере алгоритма поиска максимального элемента.
Нахождение максимального элемента массива выполняется путём последовательных сравнений. Значение наибольшего из сравниваемых элементов станем запоминать в переменной МАХ. В качестве начального значения максимума примем значение первого элемента массива. Значение переменной МАХ будем сравнивать с каждым следующим элементом массива. Если МАХ окажется меньше очередного элемента, то значение этого элемента сохраним в переменной МАХ для сравнения с последующими элементами массива. В противном случае значение переменной МАХ оставим без изменений.
Таким образом, когда все элементы массива будут просмотрены, в переменной МАХ останется копия максимального элемента массива. Сам же массив изменён не будет.
Блок-схема алгоритма нахождения максимума приведена на рисунке 13. Фрагмент программы приведён ниже.
MAX := A[1];
for i:=2 to N do
if MAX<A[i] then
MAX:=A[i];
writeln('МАХ=', MAX);
Рис.13
Ещё раз напомним, что с помощью вышеописанного алгоритма будет сформирована копиязначения максимального элемента одномерного массива.
При этом ничего не будет известно о местоположении максимального элемента в массиве, т.е. об его индексе. Между тем существует большая группа задач, для решения которых необходимо знать номер максимального элемента в массиве. В этот класс задач входят те, в которых требуется преобразовать сам максимальный элемент массива; задачи, в которых требуется обработать часть массива до максимального элемента или после него и т.п.
Алгоритм нахождения номера максимального элемента в одномерном массиве показан на рисунке 14. Понятно, что номер максимального элемента следует находить одновременно со значением максимума.
Суть алгоритма нахождения номера максимального элемента массива состоит в том, что при изменении значения, хранящегося в переменной МАХ, на значение большего элемента массива ещё в одной переменной Imax запоминается индекс элемента, принятого за максимальный. После просмотра всех элементов массива в переменной МАХ останется копия значения максимального элемента массива, а в переменной Imax – номер максимального элемента. Чтобы преобразовать максимальный элемент массива, необходимо обратиться к нему по его найденному номеру. В качестве примера на рисунке 14 приведён алгоритм нахождения номера максимального элемента одномерного массива и замена максимального элемента нулём. Фрагмент программы приведён ниже.
• • •
МАХ:=А[1] ;
Imax:=1;
for i:=2 to N do
if MAX<A[i] then
begin
MAX:=A[i];
Imax:=i;
end;
A[Imax]:=0;
… Рис.14
Как указывалось выше, алгоритм поиска минимального значения
MIN массива похож на алгоритм поиска максимального значения. Аналогично, в качестве начального значения MIN можно принять значение первого элемента массива, а затем MIN поэлементно сравнивать с элементами массива. Если значение MIN окажется больше элемента массива, то значение этого элемента массива необходимо сохранить в переменной MIN. Фрагмент программы поиска минимального значения среди всех элементов массива приводится ниже.
…
MIN := A[1];
for i := 2 to N do
if MIN > A[i] then
MIN := A[i];
writeln (‘MIN= ‘, MIN);
…
В случае, когда требуется найти MIN и MAX не среди всех элементов массива, а лишь среди тех элементов, которые удовлетворяют некоторому условию (положительные, четные и т.п.), тогда в качестве начальных значений MIN и MAX нельзя принимать значение первого элемента массива, так как заранее не известно, удовлетворяют ли они заданным условиям. В этом случае необходимо поступить следующим образом: в качестве начального значения MAX принять заведомо малое число, которое не будет принадлежать данному массиву (например, MAX = -10000, и если необходимо, Imax = 0), а в качестве начального значения MIN – большое число (например, MIN = 10000, Imin = 0). Такой метод выбора значений MAX, MIN является универсальным.
• • •