Модуль: (C++) Алгоритмы обработки массивов


Задача

1/3

Максимальный не из всех. Задача 1

Теория Нажмите, чтобы прочитать/скрыть

Максимальный не из всех

Помните, что обычно есть решение проще и быстрее того, что первым приходит вам в голову.

Дональд Кнут

Задача
Найти в массиве максимальный отрицательный элемент.

Зная стандартный алгоритм поиска максимального элемента в массиве, можно по аналогии написать программу, решающую данную задачу, добавив только проверку на знак у элемента массива.
Фрагмент программы
M = A[0];
for (i=1; i<N; i++)
  if ((A[i]<0) && (A[i]>M))
    M = A[i];
cout << M;
Это решение не всегда будет правильно работать. Прежде чем читать дальше, попробуйте самостоятельно найти тест, при котором данная программа будет работать неверно.

Ответ: Тест, в котором первый элемент массива равен любому неотрицательному числу, приведет к тому, что решение будет неверно.

Неверное решение получается из-за того, что мы "не глядя" записали в переменную M значение первого элемента массива. Так как нам нужны не все элементы массива, а только отрицательные, следовательно, мы должны в переменную M сначала записать первый отрицательный элемент. Исправить программу можно, добавив, например, такой фрагмент
// будем идти по всем элементам массива,  
// пока не встретим отрицательный элемент
int i = 0;
while (i < n && A[i] >= 0)  
    i++;   //переходим к следующему элементу массива  

// если i осталось меньше n, 
// значит мы нашли отрицательный элемент
if (i<n)    
{
  // ищем максимальный отрицательный из остальных элементов
  M = A[0];
  int start = i + 1; 
  for (i = start; i < N; i++) 
    if ((A[i] < 0) && (A[i] > M)) 
      M = A[i]; 
  cout << M;
}
else
  cout << "Таких элементов нет";
Программа получилась достаточно громоздкая. В худшем случае, нам придется практически дважды пройти весь массив от начала до последнего элемента.
На самом деле программу можно сократить до одного цикла.
M = A[0];
for (i=1; i<N; i++)
{
//если встретили отрицательный элемент массива, 
// проверяем следующее условие
  if (A[i]<0)   
    // выделенное жирным условие позволит 
    // записать в переменную M первый встретившийся отрицательный элемент, 
    // если A[0] был неотрицательный
    if ((M >= 0) && (A[i]>M))    
      M = A[i]; 
}              
cout << M;

Для успешного выполнения задания № 25 ЕГЭ не требуется писать эффективную программу. Поэтому, если вы не можете найти краткое решение задачи, записывайте его так как у вас получается. Но помните, что в программировании важна практика. 

Задача

Дан целочисленный массив из 40 элементов. Элементы массива могут принимать целые значения от 1 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести наибольший из элементов массива, восьмеричная запись которого содержит не менее трёх цифр и оканчивается на 5. Если таких чисел нет, нужно вывести ответ 0.