Максимум находят последовательно: max := a[1], затем каждый следующий элемент сравнивают с max и, если элемент больше, обновляют значение максимума.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Поиск максимума
Нажимайте «Один шаг →»: текущий элемент сравнивается с максимумом, найденным на предыдущем шаге, и, если он больше, становится новым максимумом. Введите данные примера 6.1: 1 2 6 3 2 — максимум 6.
Очень часто для решения задачи требуется находить не заданный элемент массива, а максимальный (наибольший) или минимальный (наименьший).
Рассмотрим задачу нахождения максимального элемента. Если в массиве один-единственный элемент, то он и есть максимальный. Если элементов больше одного, то максимальным в массиве из i элементов является максимум из a[i] и максимального среди первых i − 1 элементов. Поэтому максимум находят последовательно, сравнивая текущий элемент с максимумом, найденным на предыдущем шаге. Если текущий элемент больше, значение максимума обновляют.
Пример 6.1. Найти максимальный элемент массива.
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.
Тестирование: для 1 2 6 3 2 программа выведет «Максимум = 6».
Главная мысль: Максимум находят последовательно: max := a[1], затем каждый следующий элемент сравнивают с max и, если элемент больше, обновляют значение максимума.
2
Номер максимального элемента. Поиск минимума
Номер максимума хранят в переменной n_max: условие a[i] > max даёт номер первого из равных максимальных элементов, a[i] ≥ max — последнего; для поиска минимума знак > заменяют на <.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Первый или последний из равных
Введите 2 5 3 5 1 (пример 6.2). При «Первое вхождение» (условие a[i] > max) место максимума — 2, при «Последнее вхождение» (условие a[i] ≥ max) — 4. Выберите «Минимум», чтобы проверить пример 6.4.
Алгоритм примера 6.1 находит значение максимального элемента, но не позволяет определить, на каком месте он расположен. Для хранения индекса максимального элемента используем переменную n_max. Её значение изменяется тогда, когда изменяется значение максимального элемента (пример 6.2).
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('Его место ', n_max);
end.
Тестирование: для 2 5 3 5 1 — «Максимум = 5», «Его место 2». Если в массиве несколько элементов имеют максимальное значение, то n_max будет индексом первого из них. Если использовать условие a[i] ≥ max, то n_max будет хранить индекс последнего из максимальных элементов.
Когда известен индекс i элемента массива, его значение можно получить, обратившись к элементу по индексу: a[i]. Поэтому при поиске максимального элемента достаточно хранить только его индекс n_max, а значение максимального элемента — a[n_max] (пример 6.3).
//пример 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('Его место ', n_max);
Для поиска минимального элемента нужно заменить знак > в условии оператора ветвления на знак < (пример 6.4).
//пример 6.4: поиск минимального элемента
n_min := 1;
for var i := 2 to n do
if a[i] < a[n_min] then
n_min := i;
Условие в цикле
Что хранит индекс
a[i] > a[n_max]
номер первого максимального элемента
a[i] >= a[n_max]
номер последнего максимального элемента
a[i] < a[n_min]
номер первого минимального элемента
a[i] <= a[n_min]
номер последнего минимального элемента
Главная мысль: Номер максимума хранят в переменной n_max: условие a[i] > max даёт номер первого из равных максимальных элементов, a[i] ≥ max — последнего; для поиска минимума знак > заменяют на <.
3
Решение задач с использованием поиска максимума (минимума)
Победителя лыжной гонки находят как минимальное время, количество минимальных элементов — поиском элементов, равных минимуму, а самое короткое и самое длинное слово — сравнением длин функцией length.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Минимум и длина слов
Выберите «Минимум», как в примере 6.5, и введите, например, 12 7 18 9 7: минимум 7 стоит на месте 2 («Первое вхождение») и на месте 5 («Последнее вхождение»). В поле «Данные для сравнения» выберите «Длины слов» и введите Все дороги ведут в Рим (пример 6.7): самое короткое слово — «в» (длина 1, место 4), а при поиске максимума самое длинное — «дороги» (длина 6, место 2).
Пример 6.5. В массиве хранится информация о результатах спортсменов, участвующих в лыжной гонке. Определить результат победителя и его номер. Победитель прошёл трассу за наименьшее время, поэтому воспользуемся алгоритмом поиска минимального элемента и его номера (пример 6.4).
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.
Тестирование: для времени 6.31 6.17 7.32 6.54 7.03 — «Победитель - лыжник номер 2», «Его время - 6.17».
Пример 6.6. Определить, сколько раз в линейном массиве встречается элемент, равный минимальному. Сначала ищем минимальный элемент, затем линейным поиском подсчитываем элементы, равные минимальному.
//пример 6.6: поиск минимального элемента
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, ' раз(-а)');
Пример 6.7. Задан массив из слов различной длины. Найти в нём самое длинное и самое короткое слово. Самое короткое слово — слово с минимальным количеством символов, поэтому используем алгоритм поиска минимального элемента. Но если сравнивать сами элементы массива, сравнение будет происходить не по длине, поэтому для сравнения строк по длине используют функцию вычисления длины строки length. Самое длинное слово ищут алгоритмом поиска максимального элемента, тоже сравнивая длины.
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.
Тестирование: для слов Все, дороги, ведут, в, Рим — «Короткое - в», «Длинное - дороги».
Главная мысль: Победителя лыжной гонки находят как минимальное время, количество минимальных элементов — поиском элементов, равных минимуму, а самое короткое и самое длинное слово — сравнением длин функцией length.
4
Построение гистограммы (столбчатой диаграммы)
Гистограмма состоит из n прямоугольников одинаковой ширины h = trunc(WindowWidth / (2n + 1)); высота столбца — целая часть a[i]·m, где m = WindowHeight / max — масштабный коэффициент.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Столбцы по данным массива
Модель строит столбчатую диаграмму: высота столбца пропорциональна значению элемента, самый высокий столбец — максимальный элемент. Введите 4 8 20 1 17 — это данные примера 6.8 (100 200 500 35 420), уменьшенные в 25 раз и округлённые.
Пример 6.8. Дан одномерный массив из целых чисел. Построить гистограмму по числовым данным, хранящимся в массиве.
Высота столбцов
Элементы массива определяют высоту прямоугольников. Максимальное значение (max) должно по высоте поместиться в окне, поэтому вводят масштабный коэффициент m = WindowHeight / max. Значению a[i] соответствует высота trunc(a[i] * m).
Ширина и положение
Все прямоугольники имеют одинаковую ширину h, расстояние между ними равно ширине. Тогда h = trunc(WindowWidth / (2n + 1)). Начальное значение x = h, следующее получают увеличением на 2*h.
Алгоритм: ввести данные; найти максимальный элемент; в цикле построить прямоугольники. При вычислении высоты учитывают, что ось Y в графическом окне направлена сверху вниз: нижний край y1 = WindowHeight, верхний y2 = y1 − trunc(a[i]*m). Цвет прямоугольника задаётся случайным образом.
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;
end.
Тестирование: для 100 200 500 35 420 строятся пять столбцов, самый высокий — третий (500) — занимает всю высоту окна. Постройте по этим данным диаграмму в Excel и сравните.
Главная мысль: Гистограмма состоит из n прямоугольников одинаковой ширины h = trunc(WindowWidth / (2n + 1)); высота столбца — целая часть a[i]·m, где m = WindowHeight / max — масштабный коэффициент.
Интерактивная практика
Исследуйте и примените
Решите на модели задачу из упражнений: в массиве хранится среднедневная температура декабря. Определите, сколько дней было с самой низкой и с самой высокой температурой.
НАБЛЮДАЙТЕ И ПРОБУЙТЕ
Лаборатория: самые холодные и самые тёплые дни
Введите температуры через пробел, выберите «Минимум» и выполните все шаги: «Равных в просмотренной части» после полного просмотра — количество дней с самой низкой температурой. Затем выберите «Максимум».
Соберём главное
Шесть выводов
01
Максимум находят последовательно: max := a[1], затем каждый следующий элемент сравнивают с max и, если элемент больше, обновляют значение максимума.
02
Номер максимума хранят в переменной n_max: условие a[i] > max даёт номер первого из равных максимальных элементов, a[i] ≥ max — последнего; для поиска минимума знак > заменяют на <.
03
Победителя лыжной гонки находят как минимальное время, количество минимальных элементов — поиском элементов, равных минимуму, а самое короткое и самое длинное слово — сравнением длин функцией length.
04
Гистограмма состоит из n прямоугольников одинаковой ширины h = trunc(WindowWidth / (2n + 1)); высота столбца — целая часть a[i]·m, где m = WindowHeight / max — масштабный коэффициент.
05
Значение максимума можно не хранить отдельно: достаточно индекса n_max, а сам максимальный элемент — a[n_max].
06
Строки по длине сравнивают с помощью функции length, потому что сами строки сравниваются лексикографически.
Самопроверка
Тест: 10 вопросов
Один верный ответ. За ответ — 1 балл. Откройте и проверьте себя.