Инициализация переменных минимума и максимума в алгоритмах

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

Пример 32
В школе среди учеников 10 – 11-х классов производится набор игроков в школьную баскетбольную команду. Ученики, играющие в баскетбол, должны быть не ниже 185 см, но и не выше 205 см. Определите, какой рост будет у самого низкого игрока в баскетбольной команде.

Решение. Предположим, что все ученики требуемого роста будут играть в баскетбольной команде. Тогда для определения самого низкого игрока необходимо найти минимум среди учеников, чей рост не меньше 185 см, но и не больше 205 см.

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

Однако инициализировать переменную минимума значением роста первого ученика нельзя, так как этот рост может не удовлетворять требованиям игроков баскетбольной команды (например, рост первого ученика – 170 см). Поэтому мы должны инициализировать переменную минимума тем значением, которое будет заведомо не меньше искомого минимального значения. Самое логичное – инициализировать переменную минимума самым высоким ростом, с которым ученик может быть допущен в баскетбольную команду, то есть 205.

Приведем другой пример.
Пример 33
Найти два минимальных по значению элемента массива.
Решение. Запишем алгоритм поиска двух минимумов, однако коснемся инициализации переменных минимума после рассмотрения алгоритма:

1. Пусть минимум первый и минимум второй проинициализированы первым элементом массива: min₁=min₂ = a₁.

2. Установить счетчик равным 1 (i = 1).

3. Если исследованы еще не все элементы (i < n), то перейти к шагу 4, иначе алгоритм окончен (два минимальных элемента равны min₁ и min₂ соответственно).

4. Перейти к следующему элементу (увеличить i на единицу).

5. Если текущий элемент меньше, чем минимум (a_i < min₁), то присвоить min₂ значение min₁, а присвоить min₁ значение a_i, иначе если текущий элемент меньше, чем второй минимум (a_i < min₂), то присвоить min₂ значение a_i.

6. Перейти к шагу 3.

Отметим, что этот алгоритм похож на алгоритм одновременного поиска максимального и минимального элементов массива.

Рассмотрим более подробно инициализацию переменных обоих минимумов. Предположим, что обе эти переменные будут инициализированы значением первого элемента массива. Посмотрим, как отработает данный алгоритм на массиве 1 8 3 6 2 в этом случае. Так как обе переменные мы инициализируем самым маленьким значением среди всех элементов массива, то на пятом шаге алгоритма замены значений переменных обоих минимумов не произойдет, и в результате обе переменные будут равны 1, что не верно: min₁ = 1, min₂ = 2.

Мы получили неверный ответ, так как неверно инициализировали обе переменные минимума самым маленьким значением в массиве.

Возможное решение. Упорядочим первые два элемента массива и инициализируем переменную первого минимума меньшим из двух значений, а вторую переменную – оставшимся значением. Тогда алгоритм можно начинать с третьего элемента массива. Посмотрим, как будут меняться значения переменных min₁ и min₂ на каждом шаге алгоритма для массива 1 8 3 6 2.

В результате работы алгоритма первый минимум равен 1, а второй минимум равен 2, что соответствует истине.