2.1. Поиск максимального (минимального) элемента в массиве

Очень часто для решения задачи требуется находить не заданный элемент массива, а максимальный (наибольший) или минимальный (наименьший).

Рассмотрим задачу нахождения максимального элемента. Если в массиве одинединственный элемент, то он и есть максимальный. Если элементов больше одного, то максимальным в массиве из i элементов является максимум из a[i] и максимального среди первых i–1 элементов. Находить максимум будем последовательно, сравнивая текущий элемент с макси­мумом, найденным на предыдущем шаге. Если текущий элемент больше, то значение максимума, найденное на предыдущем шаге, нужно обновить (пример 6.1).

Данный алгоритм находит значе­ние максимального элемента, но не позволяет определить, на каком ме­сте в массиве расположен этот макси­мальный элемент.

Будем использовать переменную n_max для хранения индекса макси­мального элемента. Значение пере­менной n_max будет изменяться тогда, когда изменяется значение макси­мального элемента (пример 6.2).

Если в массиве несколько элемен­тов имеют максимальное значение, то значением переменной n_max будет индекс первого из них. Если исполь­зовать условие a[i] I max, то перемен­ная n_max будет хранить индекс по­следнего из максимальных элементов.

В случае, когда известен индекс i элемента массива, значение элемента можно получить, обратившись к эле­менту по индексу: a[i]. Поэтому при поиске максимального элемента до­статочно хранить только его индекс n_max. Значение максимального эле­мента — a[n_max] (пример 6.3).

Для поиска минимального элемен­та необходимо заменить знак G в усло­вии оператора ветвления на знак < (пример 6.4).

2.1. Решение задач с использованием алгоритма поиска максимального (минимального) элемента

Пример 6.5. В массиве хранится информация о результатах спортсменов, участвующих в лыжной гонке. Определить результат победителя и его номер.

I. Исходные данные: массив а — числа, являющиеся временем прохождения трассы, количество спортсменов — n.

II. Результат: a[n_min] — минимальное время, n_min — номер победителя.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Для решения задачи воспользуемся алгоритмом поиска минимального элемента в массиве и его номера (пример 6.4).
3. Вывод результата.

IV. Описание переменных: а — array[1..20] of real; n, n_min — integer.

Пример 6.6. Определить, сколько раз в линейном массиве встречается элемент, равный минимальному.

I. Исходные данные: массив а, количество чисел n.

II. Результат: min — минимальный элемент, k — количество минимальных.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Поиск минимального элемента.
3. Линейный поиск элементов, равных минимальному.
4. Вывод результата.

IV. Описание переменных: а — array[1..20] of integer; n, min, k — integer.

Пример 6.7. Задан массив из слов различной длины. Найти в нем самое длинное и самое короткое слово.

I. Исходные данные: массив а, ко­личество слов n.

II. Результат: min_s — самое ко­роткое слово, max_s — самое длинное слово.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Поиск самого короткого сло­ва. Самое короткое слово — сло­во, в котором минимальное коли­чество символов. Для его поиска можно воспользоваться алгорит­мом поиска минимального элемен­та в массиве. Однако, если срав­нивать сами элементы массива, то сравнение будет происходить не по длине. Для сравнения строк по длине нужно использовать функ­цию вычисления длины строки length.
3. Для поиска самого длинного слова можно использовать алго­ритм поиска максимального эле­мента и сравнивать элементы с использованием функции вычис­ления длины строки length.
4. Вывод результата.

IV. Описание переменных: а — array[1..20] of string; n — integer; min_s, max_s: string;

2.1. Построение гистограммы (столбчатой диаграммы)

Пример 6.8. Дан одномерный массив из целых чисел. Построить гистограмму по числовым данным, хранящимся в массиве.

I. Исходные данные: массив а, количество чисел n.

II. Результат: построенная диаграмма.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Гистограмма состоит из n прямоугольников одинаковой ширины. Элементы массива определяют высоту соответствующего прямоугольника. Максимальное значение элементов массива (переменная max) должно по высоте поместиться в окне (WindowHeight). штабный коэффициент). Тогда значению элемента массива a[i] будет соответствовать целая часть от величины a[i] * m.
3. Находим максимальный элемент массива.
4. В цикле строим прямоугольники. Все прямоугольники имеют одинаковую ширину (h), расстояние между ними можно определить равным ширине прямоугольника. Тогда ширина прямоугольника — целая часть от деления ширины окна на (2n+1):
5. При вычислении высоты пря­моугольника нужно учесть то, что ось Y направлена сверху вниз.
6. Цвет прямоугольника будем задавать случайным образом.
7. Местоположение прямоуголь­ника определяется переменной x. Начальное значение x = h. Новое значение получается из предыду­щего увеличением на 2*h.
8. Вывод результата.

IV. Описание переменных: а — array[1..20] of integer; n, max, h, x, y1, y2 — integer; m: real.

var a: array[1..20] of integer;
n, max: integer;
begin
write(ꞌКоличество n = ꞌ);
readln(n);
writeln(ꞌЭлементы массиваꞌ);
for var i := 1 to n do
read(a[i]);
max := a[1];
for var i := 2 to n do if a[i] > max then max := a[i];
writeln(ꞌМаксимум = ꞌ, max);
end.

VI. Тестирование.

Пример 6.2.
V. Программа:

var a: array[1..20] of integer;
 n, max, n_max: integer;
begin
write ('Количество n = ');
 readln(n);
writeln('Элементы массива'); 
for var i := 1 to n do read(a[i]);
max := a[1]; 
n_max := 1;
for var i := 2 to n do
if a[i] > max then
 begin
max := a[i]; 
n_max :=i; 
end;
writeln('Максимум = ', max); writeln('Ero место ', n_max); 
end.

VI. Тестирование.

Пример 6.3. Фрагмент программы:

 n_max := 1;
for var i := 2 to n do
if a[i] > a[n_max] then n_max := i;
writeln( 'Максимум = ',a[n_max]); 
writeln('Ero место ', n_max);

Пример 6.4. Фрагмент программы:

n_min := 1;
for var i := 2 to n do
if a[i] < a[n_min] then
n_min := i;

Пример 6.5.
V.  Программа:

var a: array [1..20] of real;
       n, n_min: integer;
begin
writeln( 'Количество спортсменов') ;
readln(n);
 writeln( 'Время');
for var i := 1 to n do
read(a[i]);
//поиск минимального элемента
n_min := 1;
for var i := 2 to n do
if a[i] < a[n_min] then  n_min := i;
writeln('Победитель — лыжник номер ', n_min) ;
writeln('Его время - ', a[n_min]);
end.

VI. Тестирование.

Пример 6.6.
V. Программа:

var a: array [1..20] of integer;
       n, min, k : integer;
begin
write ('Количество n = ');
readln(n);
writeln ('Числа');
for var i := 1 to n do
read(a[i]);
//поиск минимального элемента
min := a[1];
for var i := 2 to n do if a[i] < min then min := a[i];
//подсчет количества
k := 0;
for var i := 1 to n do
if a[i] = min then k := k + 1;
writeln('Минимальный ', min);
writeln('Встретился ',k,' раз (-а)');
end.

VI. Тестирование.

Пример 6.7.
V. Программа:

var a: array [1..20] of string; 
n: integer;
min_s, max_s: string;
begin
write ('Количество n = '); 
readln(n); 
writeln('Слова');
for var i := 1 to n do readln(a[i]);
//поиск короткого слова 
min_s := a[1];
for var i := 2 to n do if length(a[i]) < length(min_s) then min_s := a[i];
//поиск длинного слова
max_s := a[1];
for var i := 2 to n do if length(a[i]) > length(max_s) then max_s := a[i];
writeln('Короткое - ',min_s);
 writeln('Длинное - ',max_s); 
end.

VI.   Тестирование.

Пример 6.8.

V. Программа:

uses graphABC;
var a: array[1..20] of integer;
n, max, h, x, y1, y2: integer;
m: real;
begin
write ('Количество n = ');
readln(n);
writeln(n);
writeln('Элементы массива');
for var i := 1 to n do
begin
read(a[i]);
write (a[i],'  ');
end;
max := a[1];
for var i := 2 to n do
if a[i] > max then
max := a[i];
h := trunc(WindowWidth/(2*n+1));
m := WindowHeight/max;
x := h;
for var i := 1 to n do
begin
SetBrushColor(clrandom);
y1 := WindowHeight;
y2 := y1 - trunc(a[i]*m);
Rectangle(x, y1, x+h, y2);
x := x + 2*h;
end;

VI. Тестирование.

VII. Постройте по этим данным диа­грамму в Excel и сравните.