Задача
Дано N чисел. Найти второй по величине максимальный элемент последовательности.
Данная задача допускает два толкования.
Например, если нам дан набор чисел:
\(10\ 15\ 20\ 35\ 14\ 35\ 10\), то каким должен быть ответ?
Под "вторым по величине максимальным элементом" или просто "вторым максимумом", можно понимать:
1) значение, которое стояло бы на предпоследнем месте, если бы мы все значения расставили (отсортировали) по неубыванию (каждый следующий больше или равен предыдущему). Тогда для рассмотренного набора чисел ответом будет значение 35;
2) значение элемента, больше которого только максимальный. Тогда ответ - 20.
Если в наборе чисел только один максимальный элемент (все остальные меньше), то оба толкования совпадают, и ответ будет одинаковый для обоих случаев, иначе - ответ будет разный.
Рассмотрим первый случай (алгоритм будем записывать на
псевдокоде).
Для нахождения ответа будем использовать две переменные:
1)
максимум1 - максимальное значение (первый максимум);
2)
максимум2 - второй максимум (наш ответ).
Если диапазон изменения значений известен, то в качестве начальных значений принимаем число, которое заведомо меньше нижней границы диапазона (например, при диапазоне от
-1000 до
1000 - берем число
-1001)
Если диапазон значений неизвестен, то можно первые два вводимых числа записать в начальные значения переменных
максимум1 и
максимум2, а затем сравнить эти две переменных.
ввод N //количество чисел
ввод a, б
максимум1 = а
максимум2 = б
если б > а, то
максимум1 = б
максимум2 = а
Далее рассматриваем все остальные элементы (первые 2 уже просмотрели, значит начинать будем с 3го)
нц для i от 3 до n
ввод а
если а > максимум1 //встретилось значение большее максимума1
то
максимум2 = максимум1 //бывший первый максимум станет вторым
максимум1 = а //первым максимумом станет новый элемент
иначе
//очередной элемент не больше максимум1
//его необходимо сравнить со значением максимум2
если а > максимум 2
то
максимум2 = а //принимаем его в качестве нового значения максимум2
// максимум1 в этом случае не меняется
все
все
кц
Попробуйте реализовать данный алгоритм самостоятельно.
