2015-06-05
455
Общая формулировка задач этой группы может звучать так: в одномерном массиве найти определённый элемент, или элементы, удовлетворяющие определённому условию. Найденные элементы могут быть сохранены в отдельный массив для дальнейшей обработки.
Для алгоритмов данной группы не характерно использование обычного последовательного перебора всех элементов массива. Последовательный перебор может быть использован, например, для поиска элементов массива, если их особенность не зависит от расположения в массиве, или от других элементов (например, чётность, или кратность 3).
К задачам подобного рода можно отнести: поиск максимального и минимального элементов, поиск локальных экстремумов и т.п.
В качестве примера рассмотрим задачу поиска максимального значения, которая часто выступает в качестве составной части при решении других задач.
Основная идея алгоритма заключается в последовательном парном сравнении всех элементов массива.
Алгоритм решения задачи представлен на рисунке 19.
|
|
|
Переменная max используется для хранения текущего максимального значения. Вначале в качестве текущего максимального значения принимается значение первого элемента массива (блок 5).
Затем организуется перебор элементов массива, начиная со второго (блок 6). В теле цикла текущий максимальный элемент сравнивается с очередным элементом массива, и большее из этих значений сохраняется в качестве нового текущего максимального в переменной max (блоки 7, 8). Таким образом, при первом проходе цикла выбирается максимальное значение из двух первых элементов. На втором проходе полученное значение сравнивается с третьим элементом, и т. д. После окончания цикла в переменной max будет находиться максимальное из всех значений элементов массива.
Рисунок 19 – Блок-схема алгоритма поиска
максимального элемента
В таблице 10 представлена трассировка основной части алгоритма, представленного на рисунке 19.
Таблица 10 – Трассировка алгоритма поиска максимального
элемента
| № блока | i | A[i] | max | A | ||||
| ... | ||||||||
| - | - | |||||||
| ... |
Реализация алгоритма в программу выглядит следующим образом:
|
|
|
program Max;
var
A:array[1..100] of real;
n,i:integer;
max:real;
begin
write('n>');
read(n);
for i:=1 to n do
begin
write('A[',i,']>');
readln(A[i]);
end;
max:=A[1];
for i:=2 to n do
begin
if max<A[i] then
max:=A[i];
end;
writeln('Max=',max:4:2);
end.
