Алгоритмы обработки массивов — исследовательский практикум (5/12)

Минимум, максимум и их индексы

Массив хранит много значений, но задача часто просит найти одно особенное: самое большое, самое маленькое или его позицию. Сегодня важен не готовый ответ, а доказуемо корректный способ поиска.

Цель: за один проход найти min, max и их первые индексы, а затем проверить алгоритм контрпримером.

Сначала прогноз

Для a = [7, 12, 4, 12, 9] максимум равен 12. Но он встречается дважды. При сравнении > программа сохранит первый индекс, при >= — последний.

Корректный кандидат

max := a[1];
imax := 1;
for i := 2 to n do
  if a[i] > max then
  begin
    max := a[i];
    imax := i;
  end;

Первый элемент уже принадлежит массиву, поэтому подходит как начальный кандидат. После каждого шага max — максимум уже просмотренной части.

Почему нельзя начинать с нуля

Для массива [-8, -3, -11, -5] программа с max := 0 вернёт число, которого в массиве нет. Правильный максимум — -3.

Один проход для min и max

min := a[1]; max := a[1];
imin := 1; imax := 1;
for i := 2 to n do
begin
  if a[i] < min then begin min := a[i]; imin := i end;
  if a[i] > max then begin max := a[i]; imax := i end;
end;

Исследовательская лаборатория

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

Поймайте ошибку

if a[i] > max then max := a[i];

Если задача требует индекс, здесь не хватает imax := i. Значение и индекс обновляются вместе.

Самопроверка

Для b = [-4, 8, 8, 1, -7] найдите min, max и их первые индексы.

Ключ: min=-7, индекс 5; max=8, индекс 2.

Источник: учебная программа Республики Беларусь.