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. Алгоритм решения задачи.
IV. Описание переменных: а — array[1..20] of real; n, n_min — integer. Пример 6.6. Определить, сколько раз в линейном массиве встречается элемент, равный минимальному. I. Исходные данные: массив а, количество чисел n. II. Результат: min — минимальный элемент, k — количество минимальных. III. Алгоритм решения задачи.
IV. Описание переменных: а — array[1..20] of integer; n, min, k — integer. Пример 6.7. Задан массив из слов различной длины. Найти в нем самое длинное и самое короткое слово. I. Исходные данные: массив а, количество слов n. II. Результат: min_s — самое короткое слово, max_s — самое длинное слово. III. Алгоритм решения задачи.
IV. Описание переменных: а — array[1..20] of string; n — integer; min_s, max_s: string; 2.1. Построение гистограммы (столбчатой диаграммы)Пример 6.8. Дан одномерный массив из целых чисел. Построить гистограмму по числовым данным, хранящимся в массиве. I. Исходные данные: массив а, количество чисел n. II. Результат: построенная диаграмма. III. Алгоритм решения задачи.
IV. Описание переменных: а — array[1..20] of integer; n, max, h, x, y1, y2 — integer; m: real. |
Пример 6.1.
V. Программа: 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. 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. 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. 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. 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. Тестирование.
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 и сравните. |
1. Какой элемент массива является максимальным? Какой — минимальным?
2. Как найти максимальный элемент в массиве?
3. Как найти минимальный элемент?
4. Каким образом определить номер первого элемента, равного максимальному?
5. Как определить номер последнего элемента, равного минимальному?
Упражнения
1. Измените программы примеров 6.1 и 6.2 так, чтобы находился минимальный эле-
мент в массиве.
2. Для примера 6.5 выполните перечисленные задания.
- Найдите номер спортсмена, пришедшего на финиш последним.
- Определите, был ли победитель единственным или есть еще лыжник, прошедший трассу с таким же результатом (см. пример 6.6).
- Добавьте еще один массив. Введите в него фамилии спортсменов. Реализуйте пункты 1—3 так, чтобы выводилась фамилия, а не номер (см. пример 5.10).
3. В массиве хранится информация о стоимости автомобилей. Определите стоимость самого дорогого автомобиля и его номер в массиве. Если есть несколько таких автомобилей, то выведите все номера.
4. В массиве хранится информация о среднедневной температуре декабря. Определите, сколько в декабре было дней с самой низкой и с самой высокой температурой.
5. Задан массив из слов. Найдите в нем самое длинное слово, заканчивающееся буквой а.
6.* Задан массив из слов. Найдите в нем самое короткое слово, начинающееся с прописной буквы.