Максимальный элемент, удовлетворяющий условию
13.03.2024
Найти максимальное значение не из всех элементов массивов, а только из тех, которые удовлетворяют некоторому условию — это довольно сложная задача.
Максимальный элемент, пример
Рассмотрим пример по поиску максимального элемента. Нужно переходить из комнаты в комнату в которых лежат арбузы. Возвращаться в комнату, которую уже посещали, нельзя.
Вошли в первую комнату и нужно забрать, лежащий там арбуз. С этим арбузом идем во вторую комнату и сравниваем арбуз из первой комнаты с арбузом из второй комнаты. Если новый арбуз больше, то нужно взять его, а первый арбуз оставляете в комнате. В этом случае в руках оказывается амый большой арбуз из двух первых комнат. Точно также действуем во всех остальных комнатах, покавыбор не падет на самый большой арбуз, а комнаты при этом закончатся.
Возвращаемся к примеру с поиском арбуза: в некоторых комнатах лежат дыни, а не арбузы. А нужно найти именно самый большой арбуз.
Это значит, что выбирается новый элемент, если он: а) подходит нам по условиям отбора и б) больше, чем максимальный, найденный до этого.
Решим следующую задачу: найти максимальный из отрицательных элементов массива. Самое сложное — определить, каким должно быть начальное значение М.
Рассмотрим обычное или очевидное решение.
M = A[0]
for x in A:
if x < 0 and x > M:
M = x
print (M)Данная программа не всегда работает.
Однако, можно эту программу исправить.
сначала предположим, что значения элементов массива ограничены, т.е. принадлежат некоторому отрезку [a, b]. В этом случае достаточно выбрать любое начальное значение М, меньшее чем а. При этом все элементы массива будут больше этого числа, и когда при переборе встретиться первое подходящее число, значение М будет неизменно. Например, при а= — 1000 можно использовать такой вариант:
M = - 1001 #любое, меньше -1000
for x in A:
if x < 0 and x > M:
M = x
if M == -1000:
print ("Нет отрицательных!")
else:
print (M)Если ни одного отрицательного элемента в массеве нет, то условие в теле цикла не выполниться ни разу. Поэтому в переменной М останется начальное значение -1001.
Эту задачу можно решить иначе, не используя информацию о диапазоне значений элементов массива. Сначала запишем в переменную М значение А[0]. Оно может быть и неподходящим (положительным). Пусть при переборе мы нашли отрицательный элемент х массива.
Будем заменять значение М на х, если выполняется одно из двух условий:
- М>=0 (нашли самый первый подходящий элемент);
- x>M (нашли новый максимум).
Получается такая программа:
M = A(0)
for x in A:
if x < 0 or x > M:
if M >=0 or x > M:
M = x
if M >=0:
print ("Нет отрицательных!")
else:
print (M)Если в переменной М осталось неотрицательное значение, это значит, что отрицательных элементов в массиве нет.
Есть и еще один вариант — использовать счетчик отрицательных элементов (в программе он называется count):
count = 0
for x in A^
if x < 0:
if count == 0 or x > M:
M = x
count += 1
if count == 0:
print ( "Нет отрицательных!")
else:
print (M)Если мы нашли отрицательный элемент и счетчик равен 0 (это первый отрицательный элемент!), выполняется условие во втором условном операторе, и в переменную М записывается начальное значение х.
Цикл for x in A определить индекс найденного максимального отрицательного элемента в массиве.
Приемы, с которыми мы сейчас познакомились, работают практически во всех языках программирования.
Решение «в стиле Python» получается значительно короче: мы сначала отбираем все отрицательные элементы в новый массив, а затем находим в нем максимальное значение.
B = [x for x in A if x < 0]
if B:
print (max (B))
else:
print ("Нет таких!")Здесь условие в операторе if B выполняется тогда, когда массив B непустой, т.е. len(B) > 0. Индекс максимального отрицательного элемента в исходном массиве можно найти с помощью метода index:
M = max (B)
nmax = A.index (M)
Экономист по первому образованию и учитель информатики по второму. Преподаю в школе информатику, программирование, сайтостроение, экономику.