Максимальный элемент, удовлетворяющий условию

01.05.2024 0 Автор : Марина Николаевна
Максимальный элемент, удовлетворяющий условию

Найти максимальное значение не из всех элементов массивов, а только из тех, которые удовлетворяют некоторому условию — это довольно сложная задача.

Максимальный элемент, пример

Рассмотрим пример по поиску максимального элемента. Нужно переходить из комнаты в комнату в которых лежат арбузы. Возвращаться в комнату, которую уже посещали, нельзя.

Вошли в первую комнату и нужно забрать, лежащий там арбуз. С этим арбузом идем во вторую комнату и сравниваем арбуз из первой комнаты с арбузом из второй комнаты. Если новый арбуз больше, то нужно взять его, а первый арбуз оставляете в комнате. В этом случае в руках оказывается амый большой арбуз из двух первых комнат. Точно также действуем во всех остальных комнатах, покавыбор не падет на самый большой арбуз, а комнаты при этом закончатся.

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

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

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

Рассмотрим обычное или очевидное решение.

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]. Оно может быть и неподходящим (положительным). Пусть при переборе мы нашли отрицательный элемент х массива.